Решение задач методом поиска в пространстве состояний

Представление задач в пространстве состояний предпо-лагает задание ряда описаний: состояний, множества опе-раторов и их воздействий на переходы между состояния-ми, целевых состояний. Описания состояний могут пред-ставлять собой строки символов, векторы, двухмерные массивы, деревья, списки и т.п. Операторы переводят одно состояние в другое. Иногда они представляются в виде продукций A=>B, означающих, что состояние А преобра-зуется в состояние В.

Пространство состояний можно представить как граф, вершины которого помечены состояниями, а дуги – операторами.

Таким образом, проблема поиска решения задачи <А,В> при планировании по состояниям представляется как про-блема поиска на графе пути из А в В. Обычно графы не задаются, а генерируются по мере надобности.

Есть слепые и направленные методы поиска пути. Слепой метод имеет два вида: поиск вглубь и поиск вширь. При поиске вглубь каждая альтернатива исследу-ется до конца, без учёта остальных альтернатив. Метод плох для "высоких" деревьев, т.к. легко можно просколь-знуть мимо нужной ветви и затратить много усилий на ис-следование "пустых" альтернатив. При поиске вширь на фиксированном уровне исследуются все альтернативы и только после этого переходят на следующий уровень.

Метод может оказаться хуже метода поиска вглубь, если в графе все пути, ведущие к целевой вершине, расположены примерно на одной и той же глубине. Оба слепых метода требуют большой затраты времени и поэтому необходимы направленные методы поиска.

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

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

Примерами других алгоритмов методов поиска в прост-ранстве состояний являются: Алгоритм кратчайших путей Мура; Алгоритм Дейкстры (обобщение алгоритма Мура); Алгоритм Дорана и Мичи поиска с низкой стоимостью; Алгоритм Харта, Нильсона и Рафаэля.