Простенькая задачка на прологе.

← →
spotter (2005-10-13 21:39) [0]

Имеем:
описание графа в виде ориентированных ребер:

дорога(2,1).
дорога(3,2).
дорога(2,3).
дорога(2,4).
и т.д.

Требуется:
определить есть ли в графе циклы.

Единственный напрашивающийся вариант решения - обходить поочередно все вершины и при поподании в вершину из которой был начад обход останавливать рекурсию. Так как критическая масса познаний в этом чудо языке еше не набрана, прошу помочь с реализацией данного варианта или предложить лучший (используется visual prolog). Так же хотелось бы узнать о наличии задачников на прологе (желательно с разбором решений) и если возможжно ссылки на них в сети. Уже изучены избранные главы Братко/Кристофидеса, соответствующие тематике, но просветления они не дают.

Спасибо.

← →
Kerk © (2005-10-13 21:43) [1]

Ты не с нашей кафедры случаем? :)))

← →
spotter (2005-10-13 21:48) [2]

Kerk © (13.10.05 21:43) [1]

да, даже из группы

← →
jack128 © (2005-10-13 22:15) [3]

spotter (13.10.05 21:39)
определить есть ли в графе циклы.
что такое есть "циклы" ?? Если имеются в виду, есть ли возможность, выйдя из узла А, вернутся в него, то тогда твой алгоритм не верен. он скажет, что например такой граф (1, 2) (2, 4) (1, 3) (3, 4) имеет циклы, то время как реально циклов нету...

← →
spotter (2005-10-13 22:19) [4]

jack128 © (13.10.05 22:15) [3]

Каким образом?

В данном примере это и так невозможно.

← →
jack128 © (2005-10-13 22:35) [5]

spotter (13.10.05 22:19) [4]
В данном примере это и так невозможно.
гм. да, на приведенном примере даст верный результат. а вот на таком (1, 2) (2, 3) (3, 4) (4, 2) ? в исходный узел ты не вернешся, но цикл есть...

← →
fedotawa (2005-10-13 22:38) [6]

jack128 © (13.10.05 22:35) [5]

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

← →
Kerk © (2005-10-13 22:41) [7]

fedotawa (13.10.05 22:38) [6]

Я сейчас на вскидку лучше вариантов не вижу. Обходим, отмечая вершины где уже были в течении текущего обхода. И так для каждой вершины.

← →
spotter (2005-10-13 22:43) [8]

Kerk © (13.10.05 22:41) [7]

Проблема не в алгоритме, а в реализации, как это сделать на прологе?

← →
YurikGL © (2005-10-13 22:56) [9]

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

predicates предмуж(symbol, symbol) муж (symbol) родитель (symbol,symbol) clauses родитель (masha, tanya). родитель (john, tanya). родитель (tom, pit). родитель (liese, pit). родитель (vera, sem). родитель (misha, sem). родитель (alex, larisa). родитель (lena, larisa). родитель (tanya, pam). родитель (pit, pam). родитель (sem, bob). родитель (larisa,bob). родитель (bob,ann). родитель (pam,ann). родитель (pasha, bob). родитель (vika,misha). муж (bob). муж (tom). муж (john). муж (pit). муж (sem). муж (misha). муж (alex). муж (pasha). предмуж(A,B):-родитель(A,B). предмуж(A,B):-родитель(A,C),муж(C),предмуж(C,B).

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

← →
YurikGL © (2005-10-13 23:01) [10]

Забыл сказать, что это - турбопролог :)

← →
spotter (2005-10-13 23:02) [11]

YurikGL © (13.10.05 22:56) [9]
>В твоем случае надо будет как-то исключать уже пройденные дороги.

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

здесь спецы по Прологу есть:
http://www.progz.ru/forum/index.php?sid=8a1e4208b7915057a1136c7e7dbf72e0

Вот напомнили про Пролог ((. Терпеть его не могу. Как-то дали задачку: выполнить сортировку букв заданного текста, так никто из группы не смог такой подвиг свершить. В итоге все сдавали одну и ту же работу :)

Можно так попытаться... Давно я книжку Братко читал, всего не упомнишь...

pathexists(x,x) :- !. pathexists(x,y) :- дорога(x,y). pathexists(x,y) :- дорога(y,x). pathexists(x,y) :- pathexist(x,z), дорога(z,y). cicle :- pathexists(x,y), pathexists(y,z), pathexists(z,x).

Простенькая задачка на прологе. Найти похожие ветки