Поиск в пространстве состояний (продолжение)

на каждом шаге происходит:

1) Проверка «Новое состояние - целевое?» Если «Да» то конец;

2)Определение потомков, раскрытие вершин;

3)Выбор направления перехода и его выполнение.

На этом примере очевидно:

1)При неуправляемом переборе возможно зацикливание(S₀ -> S₃ -> S₂ -> S₁ -> S₃);

2)Есть тупиковые ветви и тупиковые вершины (S₆), она - терминальная и нецелевая;

3)Существуют различные варианты достижения целей.

Стратегия поиска - функция от имеющейся информации, стоимости поиска и т.д.

Из неинформированных процедур, наиболее известный - поиск вглубь и поиск вширь.

   При поиске вглубь, вершины раскрываются в порядке их порождения.

Часто используют ограничения на глубину поиска, т.е. задают предельное количество шагов, после которых возвращаются.

   При поиске вширь, вершины раскрываются в порядке удаления от центра поиска (исходной вершины).

СМ. РИС.1421

Преимущества поиска вширь: быстро находятся решения, если они сравнительно близко

Недостатки: Необходимо запоминать все множество путей на дереве.

В кружочках на рисунке - порядок поиска при использовании поиска вглубь.

Трудоемкость поиска решений принято оценивать количеством раскрытых вершин.

Объем раскрытых вершин возрастает по мере удаления от исходной:

СМ. РИС.1422

При разработке был предложен встречный поиск.

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

В противном случае, применяется методы поиска с возвратом (бэктрекинг).Существуют простейшие варианты с возвратом на один шаг (хронологический бэктрекинг) и более сложные методы возврата. При их использовании (бэктрекинг управляемой зависимостью) возврат по дереву поиска идет сразу на несколько шагов до точки, с которой начиналась дорога к неуспеху, запоминаются неудачные ходы, зацикливания, и далее эти пути уже исключаются.

- Если исходное состояние одно , а целевых много, то лучше применять прямые методы поиска.

- Если исходных состояний несколько, а целевое - одно, то лучше применять обратные методы.

При одинаковом числе состояний, прямые и обратные методы эквивалентны.