.
Создаем искусственный интеллект. Урок 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;

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):

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

Ну, и последний штрих, обработчик нажатия на кнопочку, который запускает наш алгоритм случайного поиска и выводит результат:

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;

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

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

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

Исходники к уроку можно скачать здесь.
Последнее обновление ( 22.10.2012 г. )