Программирование - это просто - Создаем искусственный интеллект. Урок 12. Программированием метод случайного поиска.

Создаем искусственный интеллект. Урок 12. Программированием метод случайного поиска.

Автор megabax

22.10.2012 г.

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;

Теперь нам нужно из обработчика события 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;

Все, программу можно тестировать:

Как видим, программа будет случайно блуждать до тех пор, пока не достигнет вершины 5.

Исходники к уроку можно скачать здесь.

Последнее обновление ( 22.10.2012 г. )

Пред. »

Вернуться