Page 105 - 6109

11.3 Методи "сліпого" пошуку

11.3.1 Випадковий пошук

Випадковий пошук реалізується простим алгоритмом. Інформованість
при випадковому пошуку обмежується топологією графа простору станів.
Стратегія пошуку полягає в тому, що, починаючи з початкового стану,
випадково вибирають оператор, що здійснює перехід до наступного стану
задачі. Пошук продовжується до тих пір, поки не буде виконаний перехід в
цільовий стан.
Нижче приведена процедура випадкового пошуку на псевдомові:

Procedure Random_Search;
Begin
n:='початкова вершина';
While n<> 'цільова вершина' Do
Begin
Вибрати випадково оператор, застосовний до 'n'; Застосувати
даний оператор до 'n' і одержати нову вершину 'n_New';
N:=n_New;
End.
Випадковий вибір оператора не гарантує збіжність алгоритму. Проте,
такий метод пошуку забезпечує рішення простих задач, з обмеженим
простором пошуку, за наявності шляху між початковою і цільовою вершиною.
Оскільки граф станів обстежується випадковим чином, без
запам'ятовування пройденого маршруту, можливий багатократний вибір одних
і тих же станів. Поліпшити процедуру пошуку можна введенням певної
систематичності вибору переходів стану.

11.3.2. Пошук "в глибину і ширину"

Дані методи виключають даремний повторний вибір одних і тих же
вершин. Для цього за допомогою списків OPEN і CLOSED ведеться відповідно
облік вже розкритих вершин і вершин, що підлягають розкриттю. Окрім цього,
задається певний порядок (систематичність) обстеження графа стану, що
дозволяє послідовно пройти всі маршрути по одному разу, без пропусків і
повторень. Розглянемо процедуру пошуку в глибину:
Ргоcedure Depth_First;
Begin
Помістити початкову вершину в список Open;
Сlosed:='порожній список';
While ОРЕN <>'порожній список' Dо;
Begin
n:=first(Оpen);
If n='цільова вершина' then Вихід(УСПІХ);
Перемістити n із списку Open в Сlosed;
Розкрити вершину n і помістити всі її дочірні вершини,
відсутні в списках Open і Closed , в початок списку Оpen,
зв’язавши з кожною дочірньою вершиною покажчик на n;
Еnd;
Вихід(НЕВДАЧА);

105