Использование прецедентов для редуцирования дерева решений

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

Вернемся к приведенному в параграфе 2.1 примеру с игрой «23 спички». При внимательном рассмотрении фрагмента дерева поиска этой игры можно увидеть, что дерево состоит из множества повторяющихся фрагментов (рис. 3.3).

Рис. 3.3. Повторяющиеся фрагменты дерева решений игры «23 спички».

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

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

% допустимые ходы.

move (1). move (2). move (3) .

% правило хорошего хода.

good_move (X, М) precedent (X, М), ! .

good_move (X, М) move (М), X—$ 5 =1.

good_move (X, М) move (М) ,.

XI is Х-М,.

not (good_move (Xl,_)), assert (precedent (X, М)) .

Полное дерево поиска для начального состояния «23 спички» содержит 900 140 вершин, а поиск до первого решения — 20 009 вершин; в этом случае запоминание промежуточных результатов сократит обход до 57 вершин, или в 351 раз.

Разумеется, пример задачи «23 спички» является исключительно удачным для реализации прецедентного подхода к редуцированию дерева решений при первом его проходе. В других задачах большинство состояний будут уникальными, что не позволит с такой легкостью находить повторяющиеся фрагменты. Однако достаточно часто состояния являются уникальными только из-за неудачного кодирования вершин дерева решения, и во многих случаях помогает правильный выбор системы координат, в частности переход от абсолютных к относительным координатам.

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