10.2. Методы поиска в пространстве состояний

Методы поиска в пространстве состояний фактически являются методами поиска на графе, у которого начальная вершина – начальное состояние, и задан оператор, который строит все вершины, следующие непосредственно за данной (осуществляет раскрытие вершины). Для отслеживания пути назад у каждого «сына» ставится указатель на «отца». Для всех «сыновей» делается проверка: это цель? Если не цель, то продолжается процесс раскрытия вершин. Если цель, то по указателям отслеживается путь назад. В результате получается решающая последовательность, т.е. операторы над состояниями, связанные с дугами пути.

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

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

Метод полного перебора

1. Начальную вершину поместить в список «ОТКРЫТ».

2. Если «ОТКРЫТ» = , то «неудача».

3. Взять первую вершину из списка «ОТКРЫТ» и перенести в список «ЗАКРЫТ». Обозначим эту вершину n.

4. Раскрыть вершину n, образовав всех ее «сыновей». Если «сыновей» нет, то перейти на шаг 2. Поместив всех «сыновей» в конец списка «ОТКРЫТ», построить указатели, идущие назад от них к вершине n.

5. Если какой-то «сын» – цель, то выдать решение, отследив обратный путь по указателям. Иначе – перейти на шаг 2.

Метод равных цен

На дугах заданы цены С(n_i, n_j).

1. Поместить начальную вершину в список «ОТКРЫТ» и положить g(s)=0.

2. Если «ОТКРЫТ» = , то «неудача».

3. Из списка «ОТКРЫТ» взять вершину с минимальной стоимостью (n) и поместить ее в список «ЗАКРЫТ».

4. Если n – цель, то выход с отслеживанием пути.

5. Раскрыть n. Если «сыновей» нет, то перейти на шаг 2. Для каждого «сына» вычислить g(n_i) = g(n) + С(n_i, n_j). Поместить эти вершины со значениями g в список «ОТКРЫТ» и построить указатели. Перейти к шагу 2.

Метод перебора в глубину

1. Начальную вершину поместить в список «ОТКРЫТ».

2. Если «ОТКРЫТ» = , то «неудача».

3. Взять первую вершину из списка «ОТКРЫТ» и перенести в список «ЗАКРЫТ». Обозначим эту вершину n.

4. Если глубина вершины n равна граничной глубине, то перейти к шагу 2, иначе перейти к шагу 5.

5. Раскрыть n. Поместить ее в начало списка «ОТКРЫТ» и построить указатели.

6. Если «сын» – цель, то успех, иначе – перейти на шаг 2.

10.3. Контрольные вопросы и упражнения

1. Дайте определения состояния и пространства состояний.

2. Перечислите задачи поиска в пространстве состояний.

3. Постройте фрагмент пространства состояний в задаче управления.

4. Какие существуют методы поиска в пространстве состояний?