Эвристический поиск

процедуру пошуку до найкоротшого шляху. Це позбавляє алгоритм від зациклення.

Підведемо підсумок.

1. Операції над станами дозволяють генерувати нащадків поточного стану.

2. Кожен новий стан перевіряється на предмет того, чи зустрічалося воно раніше (тобто, чи знаходиться воно в списках open або closed). Таким чином запобігають цикли.

3. Кожному стану n відповідає значення f, рівне сумі його глибини в просторі пошуку g(n) і деякої евристичної оцінки відстані від нього до цілі h(n). Іншими словами, h веде алгоритм пошуку до евристично найбільш перспективних станів, тоді як значення g утримує алгоритм від наполегливого проходження по невірному шляху.

4. Полягання в списку open сортуються відповідно до значень f. Зберігаючи всі полягання в списку open, алгоритм зможе уберегти себе від невдалого завершення.

5. Ефективність алгоритму може бути збільшена за рахунок представлення списків open і closed у вигляді купи (heap) або лівобічного дерева (leftist trees).

"Жадібний" алгоритм пошуку — це загальний алгоритм для евристичного пошуку на будь-якому графові простору станів (як і алгоритми пошуку завширшки або в глибину, розглянуті раніше).

1 2 3 4 5 6 7

Похожие работы