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

Министерство Общего и Профессионального Образования

НГТУ

Лабораторная работа №2

по дисциплине «Системы искусственного интеллекта»

вариант 4

Факультет:         ПМИ

Группа:               ПМ-83

Студенты:           Большакова А

Миркин Е.

Журавлев В.

Моисеев Д.

Преподаватели: Фроловский Д. В.

Целебровская М. Ю.

г. Новосибирск 2001

Цель работы:

Изучение основных стратегий решения задач. Приобретение  навыков  выбора  адекватных  стратегий в зависимости от типа задач. Выбор инструмента для реализации этих стратегий.

Задание:

Реализовать решение задачи о Ханойской башне.

Решение:

Рассмотрим задачу о Ханойской башне.

Даны 3 колышка и N дисков, расположенных на первом колышке. Требуется переместить все диски с первого на второй, причём на перемещение накладываются следующие ограничения:

·  диски перемещаются по одному

·  нельзя класть один диск на другой, меньшего размера.

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

Гораздо более простым будет решение, основанное на разбиении задачи на подзадачи. Пусть требуется перенести N дисков с колышка «A» на колышек «B». Нетрудно заметить, что  наиболее сложной задачей, является перемещение N-го диска на колышек «В», т.к. он является самым большим. Эта задача является тривиальной(т.е. выполняется в одно действие) только при условии, что над N-ым диске нет других дисков. Таким образом, решение задачи сводится к следующим действиям:

1.  Переместить N-1 диск с колышка «А» на колышек «С»

2.  Переместить N-й диск с колышка «А» на колышек «В»

3.  Переместить N-1 диск с колышка «С» на колышек «А»

Как видно, действия 1 и 3 также являются задачами о Ханойской башне, но уже меньшей размерности, а действие 2 является тривиальным.

И-ИЛИ дерево для этой задачи будет иметь вид:

          

Переместить N дисков с колышка «А»  на «В»

 

               Переместить N-1 диск                                                                                      Переместить N-1 диск с колышка «А» на «С»                                                                                      с колышка «С» на «В»

                                                                           Переместить  N-й диск

                                                                           с колышка «А» на «В»

Все вершины этого дерева – И-вершины. Решение будет найдено за 2^N-1 перемещений, где N – количество дисков.

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

DOMAINS

move=m(symbol,symbol)

moves=move*

где m(A,B) – означает перемещение диска с колышка «А» на «В».

Нахождение решения будет описываться следующими правилами:

CLAUSES

hanoy(1,A,B,C,[m(A,B)]):-!.

hanoy(N,A,B,C,Moves):- N>1,

N1=N-1,

hanoy(N1,A,C,B,M1),

hanoy(N1,C,B,A,M2),

append(M1,[m(A,B)|M2],Moves), !.

Тесты:

Цель:              hanoy(3,a,b,c,X)

Решение:        X=[m("a","b"),m("a","c"),m("b","c"),m("a","b"),m("c","a"),

m("c","b"),m("a","b")]

1 Solution

Цель:              hanoy(5,a,b,c,X)

Решение:        X=[m("a","b"),m("a","c"),m("b","c"),m("a","b"),m("c","a"),

m("c","b"),m("a","b"),m("a","c"),m("b","c"),m("b","a"),m("c","a"),

m("b","c"),m("a","b"),m(“a","c"),m("b","c"),m("a","b"),m("c","a"),

m("c","b"),m("a","b"),m("c","a"),m("b","c"),m("b","a"),m("c","a"),

m("c","b"),m("a","b"),m("a","c"),m("b","c"),m("a","b"),m("c","a"),

m("c","b"),m("a","b")]

1 Solution

Текст программы:

domains

move=m(symbol,symbol)

moves=move*

sterjen=integer*

predicates

%Поиск решения

hanoy(integer,symbol,symbol,symbol,moves).

%Визуализацгия

run.

draw_disk(integer).

draw_sterj(sterjen,integer,integer).

iter(sterjen,sterjen,sterjen,sterjen,sterjen,sterjen,move).

draw_solve(sterjen, sterjen, sterjen, moves).

%Операции со списками

append(moves,moves,moves).

lastelm(sterjen,integer,sterjen).

genlist(sterjen,integer).

reverce(sterjen,sterjen).

reverce(sterjen,sterjen,sterjen).

goal

run. 

clauses

%Решение задачи

hanoy(1,A,B,C,[m(A,B)]):-!.

hanoy(N,A,B,C,Moves):- N>1,

N1=N-1,

hanoy(N1,A,C,B,M1),

hanoy(N1,C,B,A,M2),

append(M1,[m(A,B)|M2],Moves), !.

%Без коментариев

run:- makewindow(1,31,31,"'Ханойская башня'",0,0,25,80),

write("Введите количество дисков:"),readln(S),str_int(S,N),

write("N=",N), N<16, hanoy(N,a,b,c,Moves), genlist(An,N),

reverce(An,Na), draw_solve(Na,[],[],Moves).

%Рисование одного диска величины N

draw_disk(0):-!.

draw_disk(N):-N>0, K=N-1, write("-"), draw_disk(K), !.    

%Рисование колышка с дисками

draw_sterj([],_,_):-!.

draw_sterj(L,X,Y):-lastelm(L,I,L1), cursor(Y,X), Y1=Y-1, draw_disk(I),

draw_sterj(L1,X,Y1),!.

%Изменение расположения дисков в зависимости от их перемещения

iter([N|Na], Nb, Nc, Na, [N|Nb], Nc, m(a,b)):-!. 

iter([N|Na], Nb, Nc, Na, Nb, [N|Nc], m(a,c)):-!. 

iter(Na, [N|Nb], Nc, [N|Na], Nb, Nc, m(b,a)):-!. 

iter(Na, [N|Nb], Nc, Na, Nb, [N|Nc], m(b,c)):-!. 

iter(Na, Nb, [N|Nc], Na, [N|Nb], Nc, m(c,b)):-!. 

iter(Na, Nb, [N|Nc], [N|Na], Nb, Nc, m(c,a)):-!. 

%Рисование одного хода решения

draw_solve(Na,Nb,Nc,[]):-         clearwindow,

draw_sterj(Na, 1, 20),

draw_sterj(Nb, 15, 20),

draw_sterj(Nc, 35, 20),

cursor(21,2), write("A"),

cursor(21,16), write("B"),

cursor(21,36), write("C"),

cursor(22,1), write("Press Enter->"),

readln(_).

draw_solve(Na,Nb,Nc,[m(A,B)|Moves]):-clearwindow,

draw_sterj(Na, 1, 20),

draw_sterj(Nb, 15, 20),

draw_sterj(Nc, 35, 20),

cursor(21,2), write("A"),

cursor(21,16), write("B"),

cursor(21,36), write("C"),

cursor(22,1), write("Press Enter->"),

readln(_),

iter(Na,Nb,Nc,Na1,Nb1,Nc1,m(A,B)),

draw_solve(Na1,Nb1,Nc1,Moves).

%Конкатенация списков

append([],X,X).

append([X|X1],Y,[X|Y1]):-append(X1,Y,Y1).

%Получение последнего элемента в списке целых чисел

lastelm([],_,[]):-!, fail.

lastelm([X],X,[]).

lastelm([X|L],Y,[X|L2]):-lastelm(L,Y,L2).

%Генерация списка целых чисел от N до 1

genlist([],0).

genlist([N|L],N):-K=N-1, genlist(L,K), !.

%Обращение списка целых чисел

reverce(X,Y):-reverce(X,[],Y).

reverce([X|Xs],Acc,Ys):- reverce(Xs,[X|Acc],Ys).

reverce([],Y,Y).