Итеративный поиск в глубину

@zXaoCz · Регистрация: 29.11.2011

Author24 — интернет-сервис помощи студентам

Доброго времени суток.
Нуждаюсь в вашей помощи!
Реализовать в программе amzi_6-2-10 пространство состояний задачи о перемещении кубиков. Количество кубиков — 4.Начальное состояние: кубики стоят один на другом в следующем порядке (сверху вниз): a,b,c,d. Конечное состояние — 3 кубика стоят один на другом в порядке a,b,c; а кубик d отдельно лежит на столе. В качестве аргументов структуры 'состояние' использовать состояния отдельных кубиков (определяющие, на чём кубик лежит). В качестве решателя использовать итеративный поиск в глубину. Найти решение в виде алгоритма (последовательности действий игрока).

Вот написал по faq но не работает. Что я сделал не так?

Prolog

move(A,B):-append(Begin,[a,b,c,d,"_"|End],A),append(Begin,[b,c,d,"_",a|End],B).
move(A,B):-append(Begin,[b,c,d,"_",a|End],A),append(Begin,[c,d,"_",b,a|End],B).
move(A,B):-append(Begin,[c,d,"_",b,a|End],A),append(Begin,[c,"_",d,"_",b,a|End],B).
move(A,B):-append(Begin,[c,"_",d,"_",b,a|End],A),append(Begin,[c,b,"_",d,"_",a|End],B).
move(A,B):-append(Begin,[c,b,"_",d,"_",a|End],A),append(Begin,[c,b,a,"_",d|End],B).
 
search_dpth(Start,Finish):-dpth([Start],Finish,Way),show_answer(Way).
member(H,[H|_]).
member(H,[_|Tail]):-member(H,Tail).
append([],B,B).
append([H|Tail],B,[H|NewTail]):-append(Tail,B,NewTail).
prolong([Temp|Tail],[New,Temp|Tail]):-
        move(Temp,New),not(member(New,[Temp|Tail])).
dpth([Finish|Tail],Finish,[Finish|Tail]).
dpth(TempWay,Finish,Way):-
        prolong(TempWay,NewWay),dpth(NewWay,Finish,Way).
show_answer([_]):-!.
show_answer([A,B|Tail]):-
        show_answer([B|Tail]),nl,write(B," -> ",A).
%goal
%search_dpth([a,b,c,d,"_"],[c,b,a,"_",d]).

@Грымзик · 04.12.2011, 01:40

Почему Вы код взяли для Визуал пролога? Вам для SWI больше подойдет. Но главная проблема в неправильном написании предиката move, а именно определении состояния. Как из этого [a,b,c,d,"_"] можно понять, что это столбик из 4х кубиков, а не 4е кубика на столе? Тут лучше как-нибудь так хранить [a/b,b/c,c/d,d/table] и например снять самый верхний кубик и положить на стол будет
move(A,B):-select(X/_, A,Temp),not(member(_/X,Temp)),ins(X/table,Temp,B).
Надо еще написать предикат положить кубик, на котором ничего не лежит, на другой кубик.

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

Prolog

1
2
3

ins(X/Y,[XH/YH|Tail],[X/Y,XH/YH|Tail]):-X<XH,!.
ins(X/Y,[XH/YH|Tail],[XH/YH|Tail1]):-ins(X/Y,Tail,Tail1).
ins(A,[],A).

search_dpth([a/b,b/c,c/d,d/table],[a/b,b/c,d/table]).

@zXaoCz · 06.12.2011, 00:58 **[ТС]**

Я очень плохо знаком с данным языком программирования. Это 4 программа на нём.

Prolog

move(A,B):-select(A/_, A,Temp),not(member(_/A,Temp)),ins(A/table,Temp,B).
move(A,B):-select(B/A, A,Temp),not(member(A/B,Temp)),ins(B/A,Temp,B).
move(A,B):-select(C/_, A,Temp),not(member(_/C,Temp)),ins(C/table,Temp,B).
move(A,B):-select(B/C, A,Temp),not(member(C/B,Temp)),ins(B/C,Temp,B).
move(A,B):-select(A/B, A,Temp),not(member(B/A,Temp)),ins(A/B,Temp,B).
 
'vzyat'('sost'([a/b],[a/table]),move,'peredvinyr kyb'(a)):-esli(a/b),
move='sost'((A/_, A,Temp),(_/A,Temp),(A/table,Temp,B)),esli(svobod/table).
'vzyat'('sost'([B/C],[B/A]),move,'peredvinyr kyb'(B)):-esli(B/C),
move='sost'((B/A, A,Temp),(A/B,Temp),(B/A,Temp,B)),esli(svobod/A)).
 
ins(X/Y,[XH/YH|Tail],[X/Y,XH/YH|Tail]):-X<XH,!.
ins(X/Y,[XH/YH|Tail],[XH/YH|Tail1]):-ins(X/Y,Tail,Tail1).
ins(A,[],A).
 
search_dpth(Start,Finish):-dpth([Start],Finish,Way),show_answer(Way).
 
prolong([Temp|Tail],[New,Temp|Tail]):-
        move(Temp,New),not(member(New,[Temp|Tail])).
 
dpth([Finish|Tail],Finish,[Finish|Tail]).
dpth(TempWay,Finish,Way):-
        prolong(TempWay,NewWay),dpth(NewWay,Finish,Way).
 
show_answer([_]):-!.
show_answer([A,B|Tail]):-
        show_answer([B|Tail]),nl,write(B),write(' -> '),write(A).
 
%search_dpth([a/b,b/c,c/d,d/table],[a/b,b/c,d/table]).

C предикатом положить кубик, на котором ничего не лежит, на другой кубик. Не могу осилить...

@Грымзик · 06.12.2011, 02:56

Prolog

move(A,B):-select(X/_, A,Temp),not(member(_/X,Temp)),ins(X/table,Temp,B).
move(A,B):-select(X/Y, A,Temp),not(member(_/X,Temp)),
    select(Z/_,Temp,Temp1), Y\=Z,not(member(_/Z,Temp1)),
    ins(X/Z,Temp,B).
 
ins(X/Y,[XH/YH|Tail],[X/Y,XH/YH|Tail]):-compare(<,X,XH),!.
ins(X/Y,[XH/YH|Tail],[XH/YH|Tail1]):-ins(X/Y,Tail,Tail1).
ins(A,[],A).
 
prolong([Temp|Tail],[New,Temp|Tail]):-
        move(Temp,New),not(member(New,[Temp|Tail])).
 
int(1).
int(N):-int(M),N is M+1.
 
search_id(Start,Finish):-
        int(Level),(Level>10,!,fail;id([Start],Finish,Way,Level),show_answer(Way)).
 
id([Finish|Tail],Finish,[Finish|Tail],0).
id(TempWay,Finish,Way,N):-N>0,
        prolong(TempWay,NewWay),N1 is N-1,
        id(NewWay,Finish,Way,N1).
 
show_answer([_]):-!.
show_answer([A,B|Tail]):-
        show_answer([B|Tail]),nl,write(B),write(' -> '),write(A).

@tana-_- · 14.12.2011, 23:44

Задача состоит в формировании плана сооружения из кубиков, т. е. описании последовательности перестановки кубиков, приводящей из начального состояния в конечное состояние.
Например: имеются 3 кубика a,b,c и три места p,q,r.
Разрешёнными являются два действия: перемещение верхнего в конструкции кубика на другой кубик.
Написать на языке Visual Prolog программу планирования для данной задачи.

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

Подскажите, пожалуйста, как код этой программы будет выглядеть на Visual Prolog 5.2??? Я сама ничего не понимаю в этом языке, поэтому не могу найти готовое решение

@Грымзик · 14.12.2011, 23:49

Основная часть на 5.2 уже есть Поиск в пространстве состояний (поиск по графам тоже сюда!) Вам надо только предикат move перевести, уж это сделайте самостоятельно.

@NadyaDres · 07.05.2012, 10:24

Здравствуйте! Помогите ответить на вопрос "Почему в задаче о кубиках можно утверждать,что путь будет кратчайшим? и вообще будет ли он таковым? "

Задача о кубиках. Имеются три места и три кубика, расставленных
по местам или друг на друга. Необходимо найти план
переупорядочивания кубиков. Разрешенными являются два действия:
перемещение верхнего в столбике кубика на свободное место или на
другой кубик со свободной верхней гранью.

Prolog

% цель (возможные финальные состояния)
 
final_state([[a],[c,b],[]]).
 
 
% функция перехода
 
next_state([Column1, Column2, [Head3|Tail3]], [[Head3|Column1], 
Column2, Tail3]).
 
next_state([Column1, Column2, [Head3|Tail3]], [Column1, 
[Head3|Column2], Tail3]).
 
next_state([Column1, [Head2|Tail2], Column3], [[Head2|Column1], 
Tail2, Column3]).
 
next_state([Column1, [Head2|Tail2], Column3], [Column1, Tail2, 
[Head2|Column3]]).
 
next_state([[Head1|Tail1], Column2, Column3], [Tail1, 
[Head1|Column2], Column3]).
 
next_state([[Head1|Tail1], Column2, Column3], [Tail1, Column2, 
[Head1|Column3]]).
 
% поиск решения
 
search(InitialState, Solution) :- solve_dfs(InitialState, 
[InitialState], Solution).
 
% поиск в глубину
 
solve_dfs(State, Visited, [State]) :- final_state(State).
 
solve_dfs(State, Visited, [State|Solution]) :-
 
  next_state(State, NextState),                       % найти 
следующее состояние
 
  \+ member(NextState, Visited),                      % проверка 
на старый путь
 
  solve_dfs(NextState, [NextState|Visited], Solution).% переход в 
следующее состояние
 
% вывод решения на консоль
 
write_list([Element|Rest]) :- write(Element), nl, 
write_list(Rest).
 
write_list([]).

Пример работы программы

?- search([[c,a,b],[],[]], Solution), write_list(Solution).

@Грымзик · 07.05.2012, 14:06

Ага, прям короче не придумаешь

Prolog

?- search([[c,a],[b],[]],_).
[[c,a],[b],[]]
[[b,c,a],[],[]]
[[c,a],[],[b]]
[[a],[c],[b]]
[[b,a],[c],[]]
[[c,b,a],[],[]]
[[b,a],[],[c]]
[[a],[b],[c]]
[[a],[c,b],[]]

Смотрите указанную мной тему.

@tana-_- 2 / 2 / 0 Регистрация: 14.12.2011 Сообщений: 37
	14.12.2011, 23:44	5
	Задача состоит в формировании плана сооружения из кубиков, т. е. описании последовательности перестановки кубиков, приводящей из начального состояния в конечное состояние. Например: имеются 3 кубика a,b,c и три места p,q,r. Разрешёнными являются два действия: перемещение верхнего в конструкции кубика на другой кубик. Написать на языке Visual Prolog программу планирования для данной задачи. Для нахождения оптимального плана действий по перемещению кубиков предлагается составить планировщик, основанный, например, на принципе анализа целей и средств. Подскажите, пожалуйста, как код этой программы будет выглядеть на Visual Prolog 5.2??? Я сама ничего не понимаю в этом языке, поэтому не могу найти готовое решение 0

@Грымзик 2505 / 1480 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	14.12.2011, 23:49	6
	Основная часть на 5.2 уже есть Поиск в пространстве состояний (поиск по графам тоже сюда!) Вам надо только предикат move перевести, уж это сделайте самостоятельно. 1

	07.05.2012, 14:06