Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 2005.11.06;
Скачать: [xml.tar.bz2];

Вниз

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

 
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]
>В твоем случае надо будет как-то исключать уже пройденные дороги.

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


 
MBo ©   (2005-10-14 06:49) [12]

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


 
Loginov Dmitry ©   (2005-10-14 09:19) [13]

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


 
Mystic ©   (2005-10-14 11:15) [14]

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

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).



Страницы: 1 вся ветка

Форум: "Потрепаться";
Текущий архив: 2005.11.06;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.48 MB
Время: 0.036 c
2-1129024501
Rolf
2005-10-11 13:55
2005.11.06
Ошибка при создании ComboBox.


4-1125491487
Black Krok
2005-08-31 16:31
2005.11.06
Исчерпание ресурсов Windows


9-1119442278
Lostcoder
2005-06-22 16:11
2005.11.06
Зеркальное отражение


1-1129657429
Galiaf
2005-10-18 21:43
2005.11.06
Повернуть картинку.


14-1129571602
Sergey_Masloff
2005-10-17 21:53
2005.11.06
Поковырялся сегодня в исходниках Indy... мама родная





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский