 |
|
Пример на использование предиката звука.
9.1. Комбинаторные задачи, реализация задачи "Ханойская башня".
Рассмотрим задачу «Ханойская башня» которую, как говорят, придумал в 1883 г. французский математик Люка. Имеются три стержня, на одном из которых помещены N колец разного диаметра, при этом, чем меньше диаметр кольца, тем выше оно
лежит. Требуется переместить диски с первого на третий стержень за некоторую последовательность ходов, каждый из которых заключается в перекладывания верхнего диска с одного из стержней на другой стержень. При этом больший диск никогда нельзя ставить на меньший диск. Если ввести обозначения:
<a,b> элементарная операция-перемещение диска со стержня с номером a на стержень b,
(m,a,b) программа перемещения m дисков с a на b.
(1,a,b) → <a,b> перемещение одного диска – элементарная операция.
Очевидно можно записать:
(m,a,b) → (m-1,a,c) <a,b> (m-1,c,b)
Т. е. для перемещения m-дисков с a на b нужно:
1) Переместить m-1 – диск с a на c (с – вспомогательный стержень).
2) Переместить нижний диск с номером m с a на b.
3) Переместить m-1 – диск с c на b (с – вспомогательный стержень).
Здесь возникает рекурсия – целевое действие определяется через промежуточные действия того же вида.
Например, пусть m = 3, т. е. имеется три кольца. Тогда:
(3,1,3)→(2,1,2)<1,3>(2,2,3)
Можно переписать в виде
(3,1,3)→ (2,1,2) <1,3> (2,2,3)
→ (1,1,3)<1,2>(1,3,2) <1,3> (1,2,1)<2,3>(1,1,3)
Окончательно:
<1,3><1,2><3,2><1,3><2,1><2,3><1,3>
Программа 12 решает задачу «Ханойская башня» на ПРОЛОГе:
DOMAINS
loc =right;middle;left
PREDICATES
hanoi(integer)
move(integer,loc,loc,loc)
inform(loc,loc)
GOAL
hanoi(5).
CLAUSES
hanoi(N):- move(N,left,middle,right).
move(1,A,_,C):- inform(A,C),!.
move(N,A,B,C):- N1=N-1, move(N1,A,C,B), inform(A,C),
move(N1,B,A,C).
inform(Loc1, Loc2):- nl,write(“Диск с”, Loc1, “ на “, Loc2).
9.2Другие примеры комбинаторики.
Классическим примером использования алгоритма поиска с возвратом является задача о восьми ферзях. Её формулировка такова: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Сперва на доску ставят одного ферзя, а потом пытаются поставить каждого следующего ферзя так, чтобы его не били уже установленные ферзи. Если на очередном шаге такую установку сделать нельзя — возвращаются на шаг назад и пытаются поставить ранее установленного ферзя на другое место.