Здравствуйте!

Есть БД на прологе, описывающая улицы города (задание в конце письма).
Что-то типа этого:

object('улица','Жуковского',
[
    ['налево','проспект','Литейный',53,'назад'],
    ['направо','проспект','Литейный',55,'вперед'],
    [1,3,5,7,9,11,13],
    [2,4,6,8,10],
    ['налево','улица','Чехова',1,'вперед'],
    [15,17,19,21,23,25],
    [12,14],
    ['налево','улица','Маяковского',9,'вперед'],
    ['направо','улица','Маяковского',7,'назад'],
    [27,29,31,33,35,37,39,41,43,45,47,49,51],
    [16,18,20,22,24,26,28],
    ['налево','улица','Восстания',21,'вперед'],
    ['направо','улица','Восстания',19,'назад'],
    [53,55,57],
    [30,32,34],
    ['налево','улица','Радищева',1,'вперед'],
    [59,61,63,65],
    [36,38],
    ['налево','проспект','Лиговский',19,'назад'],
    ['направо','проспект','Лиговский',21,'вперед']
]).

object('набережная','Кутузова',
[
    ['начало','набережная','Робеспьера'],
    ['налево','проспект','Литейный',1,'вперед'],
    ['направо','Мост','Литейный',-1,'назад'],
    [],
    [2],
    ['налево','переулок','Кричевский',1,'вперед'],
    [],
    [4,6,8,10,12,14,16,18,20,22],
    ['налево','улица','Гагаринская',1,'вперед'],
    [],
    [24,26,28,30,32,34,36],
    ['налево','набережная','реки Фонтанки',-1,'вперед'],
    ['налево','набережная','Лебяжьего канала',-1,'вперед'],
    ['конец','набережная','Дворцовая']
]).

Соответственно, каждый поворот представляет собой такой же объект.

Так вот, что нужно сделать:

Составить отношение
path(Source,Target,M).

Аргумент Source — список — содержит указание на конкретный объект
из созданной на первом этапе базе данных в формате [Type,Name,Building],
где
Type — тип объекта (улица, площадь, проезд, переулок и т.п.),
Name — имя объекта,
Building — номер конкретного дома.


Аргумент Target — список — содержит указание на конкретный объект
из созданной на первом этапе базе данных в формате [Type,Name,Building],
где
Type — тип объекта (улица, площадь, проезд, переулок и т.п.),
Name — имя объекта,
Building — номер конкретного дома.

Аргумент M — список — содержит описание маршрута от первого объекта
до второго объекта в формате, совпадающем с форматом описания улиц
(при этом от проходимых улиц содержится только тот участок, по которому
проходит маршрут).

Просьба подкинуть пару мыслей, ибо решение тупым перебором, мне кажется, просто скушает стек. А проверить реализацией... Ну, пролог для меня довольно сложен, нежели какой-нибудь императивный язык, поэтому хочется сразу знать, что кодируемое мной решение чисто алгоритмически верно.

Вот по каким правилам описывались улицы:

для заданного набора улиц построить
базу данных, состоящую из правил, имеющих вид:
object (Type, Name, List).
Type — тип объекта (улица, площадь, проезд, переулок и т.п.),
Name — имя объекта,
List — описание самого объекта в виде списка.
Например object ("улица","Московская",[1,3,5],[2,4,6],
["налево","улица","Аграрная",11,"назад"],
["направо","проезд","Поперечный",3,"вперед"],
[7,11,13],[10,12,14]]
Элементами списка являются подсписки следующего вида: часть подсписков
перечисляет номера домов, расположенных в порядке возрастания в пределах
одного квартала, при этом сначала идёт подсписок с нечётными номерами,
затем — с чётными номерами. Между списками, соответствующими кварталам,
находятся списки, определяющие возможные повороты в пересекающие улицы,
имеющие вид:
в первом подсписке указано слово "налево", затем — тип улицы, название
улицы, номер первого нечётного дома (на углу улицы, куда происходит
поворот), а также направление движения ("вперед", либо "назад");

во втором подсписке указано слово "направо", затем — тип улицы,
название улицы, номер первого нечётного дома (на углу улицы, куда
происходит поворот), а также направление движения ("вперед", либо
"назад").
Предполагается, что движение вперед идёт от меньшего номера дома к большему
вдоль улицы. Если поворот только в одну сторону, то записывается один
соответствующий подсписок.
Замечание.
Если начало улицы приходится на пересечение с некоторой другой улицей, то
список описания предваряется описанием поворотов, аналогично и для конца улицы.
Если начало улицы является продолжением некоторой другой улицы, то предваряем
описание списком, состоящим из подсписка, первым атомом которого является
слово "начало" либо "конец", а следующими — тип и имя объекта, откуда
происходит вытекание описанной улицы. Аналогично и для конца улицы.

изучай алгоритмы работы с князьями и графами: http://dsp-book.narod.ru/Algorithms.pdf

Здравствуйте, Аноним, Вы писали:

А>изучай алгоритмы работы с князьями и графами: http://dsp-book.narod.ru/Algorithms.pdf

Реализовывать графы на прологе???
Кстати, искать надо не кратчайший путь, а просто путь.

Может такое прокатит:
рекурсивно(а больше никак, вроде, и нельзя ) проходить на каждый поворот на текущей улице, сохраняя при этом список уже пройденных улиц. Если очередной поворот ведет на пройденный участок, заканчиваем искать путь в этой "ветке". Если мы нашли искомую улицу, то раскручиваем стек и выводим путь.

Только как бы такое запрограммировать...

Стоит пытаться или такое решение изначально не сможет улижиться в ресурсы?..

Здравствуйте, Аноним, Вы писали:

А>Просьба подкинуть пару мыслей, ибо решение тупым перебором, мне кажется, просто скушает стек.
Если не зациклится, то не скушает. Стеки у Пролога обычно большие.
Другое дело, что найденный таким образом путь от Балтийского до Варшавского вокзала будет проходить по Гражданскому.

Здравствуйте, Трурль, Вы писали:

А>>Просьба подкинуть пару мыслей, ибо решение тупым перебором, мне кажется, просто скушает стек.
Т>Если не зациклится, то не скушает. Стеки у Пролога обычно большие.
Т>Другое дело, что найденный таким образом путь от Балтийского до Варшавского вокзала будет проходить по Гражданскому.

Спасибо за ответ. Тогда проблем никаких нет. А путь может быть каким угодно, лишь бы вел в нужное место.
Но сдача проходит на Arity Prolog под ДОС. К примеру, я писал для своей БД ~50 Кб:

conc([],L,L).
conc([X|L1],L2,[X|L3]):- conc(L1,L2,L3).

rev([],[]).
rev([H|T],List2):- rev(T,List_), conc(List_,[H],List2).

change_elem([],[]).
change_elem(['налево',V1,V2,V3,'вперед'],['направо',V1,V2,V3,'назад']).
change_elem(['налево',V1,V2,V3,'назад'],['направо',V1,V2,V3,'вперед']).
change_elem(['направо',V1,V2,V3,'вперед'],['налево',V1,V2,V3,'назад']).
change_elem(['направо',V1,V2,V3,'назад'],['налево',V1,V2,V3,'вперед']).
change_elem(['конец'|T],['начало'|T]).
change_elem(['начало'|T],['конец'|T]).
change_elem([H|T],L):- number(H), rev([H|T],L).

reverse([[],[H2|T2]|T],List):-
    number(H2), reverse(T,L), change_elem([H2|T2],Elem2), conc([[]],[Elem2],R), conc(L,R,List), !.
reverse([[H1|T1],[]|T],List):-
    number(H1), reverse(T,L), change_elem([H1|T1],Elem1), conc([Elem1],[[]],R), conc(L,R,List), !.
reverse([[H1|T1],[H2|T2]|T],List):-
    number(H1), number(H2), reverse(T,L), change_elem([H1|T1],Elem1), change_elem([H2|T2],Elem2), conc([Elem1],[Elem2],R), conc(L,R,List), !.
reverse([H|T],List):-
    reverse(T,L), change_elem(H,Elem), conc(L,[Elem],List).
reverse([],[]).

rev_all:-
    telling(Std), told, tell('new_base__'),
    findall(object(X,Y,Z), object(X,Y,Z), L),
    write_all(L),
    told, tell(Std).

change_list(object(X,Y,Z), object(X,Y,Z_)):- reverse(Z, Z_).

write_all([]).
write_all([H|T]):- change_list(H, H_), writeq(H_), write('.'), nl, nl, write_all(T).

Так вот, rev_all не переворачивал на Arity всю базу из-за нехватки стека! А на SWI-Prolog все хорошо срабатывало...