unit AIObj
Создаем искусственный интеллект. Урок 12.
Программированием метод случайного поиска.
Исходники к уроку можно скачать
здесь.
Сегодня мы начнем изучать методы "слепого" поиска. Вот эти методы:
-
Метод случайного поиска. Суть данного метода
заключается в том, что на каждом разветвлении мы выбираем путь по рандому. В
конце концов, после нескольких блужданий, мы достигнем цели. Разумеется, такой
метод годиться лишь для маленьких лабиринтов, иначе "блуждать" можно довольно
долга. В рамках данного урока мы рассмотрим реализацию такого метода программно.
-
Поиск "в глубину" и в "ширину". Это более оптимальный
метод, по сравнению с методом случайного поиска. Его суть состоит в том, что
используя списки OPEN и CLOSED
ведется учет вершин графа, дабы не проходить второй раз уже пройденные
вершины. Разница между методом поиска "в глубину" и "в ширину" заключается в
том, что в первом случае мы добавляем вершины в список OPEN
по методу LIFO, а во втором по методу
FIFO. Этот метод поиска мы так же будем рассматривать
в будущих уроках.
-
Алгоритм равных цен. По сути, это тоже поиск "в
глубину" или "в ширину", но при этом для каждого отрезка пути определяется некая
величина, называемая стоимость. В списке OPEN
вершины сортируются в порядке возрастания стоимости, таким образом, сначала
берутся самые дешевые варианты, и в результате получается наиболее оптимальный
путь.
А теперь начнем программировать. Как я уже сказал в
заголовке, сегодня мы закодируем метод случайного поиска. И так, открываем
исходники
прошлого урока. Нам нужно создать класс TAIStateItemsList, в нем у нас будет
храниться результат работы алгоритма случайно поиска, вот как объявляется этот
класс:
TAIStateItemsList=class(TObject)
protected
FItems:TList;
function
GetItem(index:integer):TAIStateItem;
function
GetCount:integer;
public
property
Items[index:integer]:TAIStateItem
read
GetItem;
default;
property
Count:integer
read
GetCount;
constructor
Create;
procedure
Add(Item:TAIStateItem);
procedure
Clear;
virtual;
end; |
И вот так реализуется:
// *********************** TAIStateItemsList ******************
constructor
TAIStateItemsList.Create;
begin
inherited
Create;
FItems:=TList.Create;
end;
function
TAIStateItemsList.GetCount:integer;
begin
Result:=FItems.Count;
end;
procedure
TAIStateItemsList.Add(Item:
TAIStateItem);
begin
FItems.Add(Item);
end;
function
TAIStateItemsList.GetItem(index:integer):TAIStateItem;
begin
Result:=FItems[index];
end;
procedure
TAIStateItemsList.Clear;
begin
FItems.Clear;
end; |
Как видите, ничего сложно нет, простая оболочка для TList.
Теперь к классу TAIProblemSpace добавим метод RandomSearch, который и будет у
нас реализовывать алгоритм случайного поиска:
TAIProblemSpace=class(TAIStateItemsList)
protected
FEnter:integer;
FExit:integer;
FCurrentItem:TAIStateItem;
FDistance:integer;
FLeft:integer;
FTop:integer;
FTopWidth:integer;
FTopHeight:integer;
public
property
Enter:integer
read
FEnter
write
FEnter;
property
Exit:integer
read
FExit
write
FExit;
property
CurrentItem:TAIStateItem
read
FCurrentItem;
constructor
Create;
destructor
Destory;
procedure
Clear;
override;
procedure
DrawTop(AImage:TImage;
index:integer;
AName:string);
procedure
DrawArc(AImage:TImage;index1,index2:integer);
procedure
Draw(AImage:TImage);
function
RandomSearch:TAIStateItemsList;
end; |
И вот таким вот образом мы его реализуем:
function
TAIProblemSpace.RandomSearch:TAIStateItemsList;
var
target:TAIStateItem;
i,cn:integer;
a:integer;
begin
Result:=TAIStateItemsList.Create;
FCurrentItem:=Items[FEnter];
target:=Items[FExit];
Randomize;
while
FCurrentItem<>target
do
begin
Result.Add(FCurrentItem);
cn:=FCurrentItem.ExitsCount;
i:=random(cn);
FCurrentItem:=FCurrentItem.Exits[i];
end;
end; |
Теперь нам нужно из обработчика события OnCreate
формы убрать переменную PS и сделать ее членом класса
формы (выделено серым маркером):
TfrmAI
=
class(TForm)
ImageTest:
TImage;
lbResult:
TListBox;
btnStart:
TButton;
procedure
FormCreate(Sender:
TObject);
procedure
btnStartClick(Sender:
TObject);
private
{ Private declarations }
PS:TAIProblemSpace;
public
{ Public declarations }
end; |
К самой форме добавим список ListBox (назовем
lbResult) и кнопочку (назовем
ее btnStart):
Ну, и последний штрих, обработчик нажатия на кнопочку, который запускает наш
алгоритм случайного поиска и выводит результат:
procedure
TfrmAI.btnStartClick(Sender:
TObject);
var
res:TAIStateItemsList;
i,cn:integer;
begin
res:=PS.RandomSearch;
cn:=res.Count-1;
lbResult.Items.Clear;
for
I
:=
0
to
cn
do
begin
lbResult.Items.Add(res[i].Name);
end;
end; |
Все, программу можно тестировать:
Как видим, программа будет случайно блуждать до тех пор, пока не достигнет
вершины 5.
Исходники к уроку можно скачать
здесь.
|