Эвристический поиск в лабиринте

[Аnn111]

Помогите плиз!!Срочно надо)
лабиринт представляет собой систему комнат,соединенных между собой переходами.В лабиринте имеется вход и выход,а также комната с золотым кладом.Кроме того,имеются комнаты,запрещенные для посещений:комната монстров и комната разбойников.
1)Найди путь в лабиринте от входа до входа,не посещая дважды одной и той же комнаты.
2)Найти путь с посещением золотой комнаты.
3)Найти путь,избегающий запрещенных к посещению комнат.
4)Подсчет количество пройденных комнат.

[rrrFer]

на прологе, наверное?

[Аnn111]

Сообщение от rrrFer

на прологе, наверное?

Да,на прологе,помогите с кодом)

[rrrFer]

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

Что именно не получается?
И на каком прологе?

[Аnn111]

я вообще не могу понять,с чего начинать,P# Prolog,вы говорите,что нужно использовать граф-это и есть мой лабиринт в виде графа,я правильно поняла?

[Аnn111]

Сообщение от rrrFer

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

Что именно не получается?
И на каком прологе?

я вообще не могу понять,с чего начинать,P# Prolog,вы говорите,что нужно использовать граф-это и есть мой лабиринт в виде графа,я правильно поняла?

[rrrFer]

это и есть мой лабиринт в виде графа,я правильно поняла?

правильно, вцелом.

Нужен граф состояний игры, но в вашем случае состояние - это положение в лабиринте, поэтому граф-лабиринт сойдет.

[Аnn111]

это эвристический поиск,можете проверить на ошибки,очень надо!
route(room1,room2,4).
route(room2,gold,3).
route(room2,monsters,5).
route(room2,monsters,4).
route(gold,razb,2).
route(razb,room3,7).
route(monsters,room3,2).
route(gold,room3,4).
move(room1,room2,monsters):-route(room1,room2,monsters);route(r oom2,room1,monsters).


member(H,[H|_]).
member(H,[_|Tail]):-member(H,Tail).

place([],SortedWays,SortedWays).
place([Way|Tail],PrevWays,SortedWays):-placeone(Way,PrevWays,PrevWays1),pl ace(Tail,PrevWays1,SortedWays).

placeone(Length:Way,[LengthH:WayH|Tail],[Length:Way,LengthH:WayH|Tail]):-Length=<LengthH,!.
placeone(LengthWay,[LengthHWayH|Tail],[LengthHWayH|NewTail]):-placeone(LengthWay,Tail,NewTail).
placeone(LengthWay,[],[LengthWay]).

search_bst(Start,Finish):-
bst([0:[Start]],Finish,Length:Way),
show_answer(Way),nl,write('Length of way: '),write(Length).

bst([Length:[Finish|Tail]|_],Finish,Length:[Finish|Tail]).
bst([TempWay|OtherWays],Finish,Way):-
findall(W,prolong(TempWay,W),Ways),
place(Ways,OtherWays,NewWays),bst(N ewWays,Finish,Way).

show_answer([_]):-!.
show_answer([room1,room2|Tail]):-
show_answer([room2|Tail]),nl,write(room2),write(' -> '),write(room1).




count([],0).
count([1|Tail],Y1):-count(Tail,Y), Y1 is Y+1.

[rrrFer]

твоя задача решена тут с подробными комментариями: http://pro-prof.com/archives/1299
на SWI Prolog. Вместо спасибо можешь жамкнуть кнопку гугл+ или оценить сайт в web of trust, например.

"Эвристический" поиск подразумевает использование какой-то догадки (которая, в общем случае, не гарантирует результат). Для твоей задачи я такой догадки придумать не могу.

[Аnn111]

спасибо большое!А на турбо прологе пойдет?