Понятие пространства состояния

Основные стратегии решения задач. Поиск решения в пространстве состояний

Пространство состояний – это граф, вершины которого соответствуют ситуациям, встречающимся в задаче («проблемные ситуации»), а решение задачи сводится к поиску путей на этом графе. На самом деле, задача поиска пути на графе и задача о N ферзях - это задачи, использующие одну из стратегий перебора альтернатив в пространстве состояний, а именно – стратегию поиска в глубину.

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

К таким задачам относятся следующие задачи:

· задача о восьми ферзях;

· переупорядочение кубиков, поставленных друг на друга в виде столбиков;

· головоломка «игра в восемь»;

· головоломка о «ханойской башне»;

· задача о перевозке через реку волка, козы и капусты;

· задача о двух кувшинах;

· задача о коммивояжере;

· другие оптимизационные задачи.

Со всеми задачами такого рода связано два типа понятий:

· проблемные ситуации;

· разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.

Проблемные ситуации вместе с возможными ходами образуют направленный граф, называемый пространством состояний.

Пространство состояний некоторой задачи определяет «правила игры»: вершины пространства состояний соответствуют ситуациям, а дуги – разрешенным ходам или действиям, или шагам решения задачи. Конкретная задача определяется:

· пространством состояний;

· стартовой вершиной;

· целевым условием или целевой вершиной.

Каждому разрешенному ходу или действию можно приписать его стоимость. Например, в задаче о коммивояжере ходы соответствуют переездам из города в город, ясно, что стоимость хода в данном случае – это расстояние между соответствующими городами.

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

В представленной в примере 77 программе о N ферзях проблемная ситуация (вершина в пространстве состояний) описывается в виде списка из N X-координат ферзей, а переход из одной вершины в другую генерирует предикат queens, причем начальная ситуация генерируется предикатом range, а целевая ситуация определяется при помощи предиката attack.