Методы поиска решений в одном пространстве обычно делятся на поиск в пространстве состояний, поиск методом редукции, эвристический поиск и поиск генерация-проверка [39].
В сущности, любая структура величин может быть использована для описания состояний. Это могут быть строки символов, векторы, двухмерные массивы, деревья и списки. Часто выбираемая форма описания имеет сходство с некоторым физическим свойством решаемой задачи. Так, в игре в пятнадцать естественной формой описания состояний может быть массив 4х4. Выбирая форму описания состояний, нужно позаботиться и о том, чтобы применение оператора, преобразующего одно описание в другое, оказалось бы достаточно легким.
По-видимому, самый прямолинейный подход при поиске решения для игры в пятнадцать состоит в попытке перепробовать различные ходы, пока не удастся получить целевую конфигурацию. Такого рода попытка по существу связана с поиском при помощи проб и ошибок. Отправляясь от начальной конфигурации, можно построить все конфигурации, возникающие в результате выполнения каждого из возможных ходов, затем построить следующее множество конфигураций после применения следующего хода и т.д., пока не будет достигнута целевая конфигурация.
Для обсуждения такого сорта методов поиска решения введем понятие состояний и операторов для данной задачи. Для игры в пятнадцать состояние задачи - это просто некоторое конкретное расположение фишек. Начальная и целевая конфигурации представляют собой соответственно начальное и целевое состояния. Пространство состояний, достижимых из начального состояния, состоит из всех тех конфигураций фишек, которые могут быть образованны в результате допустимых правилами перемещений фишек. Многие задач имеют чрезвычайно большие (если не бесконечные) пространства состояний.
Оператор преобразует одно состояние в другое. Игру в пятнадцать естественно всего интерпретировать как игру, имеющую четыре оператора, соответствующие следующим позициям: передвинуть пустую клетку (пробел) влево, вверх, вправо, вниз. В некоторых случаях оператор может оказаться неприложимым к какому- то состоянию. На языке состояний и операторов решение некоторой проблемы есть последовательность операторов, которая преобразует начальное состояние в целевое.
Пространство состояний, достижимых из данного начального состояния, полезно представлять себе в виде графа, вершины которого соответствуют этим состояниям. Вершины такого графа связаны между собой дугами, отвечающими операторам.
Операторы приводят одно состояние в другое. Таким образом, их можно рассматривать как функции, определенные на множестве состояний и принимающие значения из этого множества. Так как процессы решения задач основаны на работе с описанием состояний, то будем предполагать, что операторы- функций этих описаний, а их значения- новые описания. В общем случае будем предполагать, что операторы- это вычисления, преобразующие одни описания состояний в другие.
В некоторых задачах оптимизации недостаточно найти любой путь, ведущий к цели, а необходимо найти путь, оптимизирующий некоторый критерий (например, минимизирующий число применений операторов). С такими задачами проще всего работать, сделав так, чтобы поиск не оканчивался до сих пор, пока не будет найдено некоторое оптимальное решение.
Таким образом, для полного представления задачи в пространстве состояний необходимо задать:
а) форму описания состояний и, в частности, описание начального состояния;
б) множество операторов и их воздействий на описания состояний;
в) свойства описания целевого состояния.
Пространство состояний полезно представлять себе в виде направленного графа (Рисунок 4.2).
Граф состоит из множества (не обязательно конечного) вершин. Некоторые пары вершин соединены с помощью дуг, и эти дуги направлены от одного члена этой пары к другому. Такие графы носят название направленных графов. Если некоторая дуга направлена от вершины ni к вершине nj, то говорят, что вершина nj является дочерней для вершины ni, а вершина ni является родительской вершиной для nj. Может оказаться, что наши две вершины будут дочерними друг для друга; в этом случае пара направленных дуг называется иногда ребром графа. В случае, когда граф используется для представления пространства состояний, с его вершинами связывают описание состояний, а с его дугами- операторы.
Последовательность вершин ni1,ni2,...,nik., в которой каждая вершина nij дочерняя для ni,j-1, j=2,k, называется путем длины k от вершины ni1, к вершине nik. Если существует путь, ведущий от вершины ni к вершине nj, то вершину nj называют достижимой из вершины ni или потомком вершины ni . В этом случае вершина ni называется также предком для вершины nj. Видно, что проблема нахождения последовательности операторов, преобразующих одно состояние в другое, эквивалентна задаче поиска пути на графе, что и есть поиск методом редукции.
