[Закрыть]
 
popoff.donetsk.ua
На бои гладиаторов, на показные избиения, убийства всегда сбегалось гораздо больше плебса, чем на проникновенные проповеди о любви к ближнему своему.
Начало | Новости | Статьи | Форум | Опросы | Карта сайта | Обо мне
popoff.donetsk.ua - Форум - Функциональное и логическое программирование - Задача по графам

Задача по графам

форумы popoff.donetsk.ua
Страницы: [1]
<< Новый  |  Старый >>  |  Ответ не возможен

Внимание! Этот топик устарел. Пожалуйста, создайте новый топик, чтобы задать интересующий Вас вопрос.

Автор Сообщение
target
Таня
Дек, 2005
Сообщений: 7
target url://forum.message:963
Задача по графам

Задан граф.Для пары его вершин определить:
  а)Кратчайший путь между ними
  б)Сколько между ними существует путей менее заданного n
  в)Сколько между ними существует простых путей(т.е. проходящих дважды через какую-либо вершину)

Вот как делала,но пункты б И в не работают
belong(r(X,Y),[Head|Tail]):- r(X,Y)=Head; belong(r(X,Y),Tail).
belongList(X,[Head|Tail]):- X=Head.
belongList(X,[Head|Tail]):- not X=Head,belongList(X,Tail).

adjacent(X,Y,1,graf(Vertex,Rib)):- belong(r(X,Y),Rib); belong(r(Y,X),Rib).

path(A,Z,graf(Vertex,Rib),Path,Cost):- path1(A,[Z],0,graf(Vertex,Rib),Path,Cost).
path1(A,[A|Path1],Cost1,graf(Vertex,Rib),[A|Path1],Cost1).
path1(A,[Y|Path1],Cost1,graf(Vertex,Rib),Path,Cost):- adjacent(X,Y,1,graf(Vertex,Rib)),
                                                      not belongList(X,Path1),
                                                      Cost2 is Cost1+1,
                                          path1(A,[X,Y|Path1],Cost2,graf(Vertex,Rib),Path,Cost).

minPath(V,V1,graf(Vertex,Rib),MinCost,Path):- path(V,V1,graf(Vertex,Rib),Path,MinCost),
            not (path(V,V1,graf(Vertex,Rib),_,VXCost),VXCost<MinCost).


                             

include(Path,L,[Path|L]).
belongPath(Path,[Head|Tail]):- Path=Head; belongPath(Path,Tail).

count(V,V1,graf(Vertex,Rib),N,Kolvo,SetPaths):- path(V,V1,graf(Vertex,Rib),Path,MinCost),
     not belongPath(Path,SetPaths),MinCost<N,include(Path,SetPaths,S1),Kolvo1 is Kolvo+1,
     count(V,V1,graf(Vertex,Rib),N,Kolvo1,S1).


% countCircles(a,d,graf([a,b,c,d],[r(a,b),r(b,d),r(b,c),r(c,d)]),0,K,[])


countCircles(V1,V2,graf(Vertex,Rib),Kolvo,Kolvo2,SetPaths):- path(V1,V2,graf(Vertex,Rib),Path,_),
not belongPath(Path,SetPaths),include(Path,SetPaths,S1),Kolvo2 is Kolvo+1,
     countCircles(V1,V2,graf(Vertex,Rib),Kolvo2,K,S1).

popoff
Yuri
Июл, 2004
Сообщений: 923
popoff url://forum.message:964

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

Если Вы используете сложные объекты и альтернативные домены, то не могли бы вы приводить примеры вместе с разделом доменов?

Как задается Ваш граф?

________________________________
Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить.
target
Таня
Дек, 2005
Сообщений: 7
target url://forum.message:965

Граф задается меожеством  вершин и множеством ребер
graf([a,b,c,d],[r(a,b),r(b,d),r(b,c),r(c,d)])
домены не использовала.

popoff
Yuri
Июл, 2004
Сообщений: 923
popoff url://forum.message:966

Посмотрите в сторону предиката findall и сведите Вашу задачу к обработке списков.

домены не использовала.

targetфорумы popoff.donetsk.ua

Совсем-совсем не использовали?

~~~~~ 31 Дек 2005, 17:19 ~~~~~

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

________________________________
Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить.
target
Таня
Дек, 2005
Сообщений: 7
target url://forum.message:1003

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

popoff
Yuri
Июл, 2004
Сообщений: 923
popoff url://forum.message:1004

Прошу помочь написать предикат для нахождения путей(как простых так и циклических) между двумя вершинами в неориентированном графе.
Мой предикат path находит только простые пути.А у самой не получается.(

targetфорумы popoff.donetsk.ua


Что именно у Вас не получается?

Или Вы, говоря «не получается», имеете в виду «напишите за меня»?

У Вас очень интересная задача, и мне было бы интересно ее решить. Но на этом форуме я не решаю задачи. Я могу помочь Вам решить Вашу задачу, но не решить ее за Вас.

________________________________
Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить.
target
Таня
Дек, 2005
Сообщений: 7
target url://forum.message:1005

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

target
Таня
Дек, 2005
Сообщений: 7
target url://forum.message:1006

А вот и само решение с тестами:

%-------------------------------------------------------- % проверка принадлежности ребра списку(sути) %-------------------------------------------------------- belong(r(X,Y),[Head|Tail]):- r(X,Y)=Head; belong(r(X,Y),Tail). %-------------------------------------------------------- % sринадлежность элемента списку %-------------------------------------------------------- belongList(X,[Head|Tail]):- X=Head. belongList(X,[Head|Tail]):- not X=Head,belongList(X,Tail). %-------------------------------------------------------- % &#9472;войство смежности вершин(X и Y) % возвращает yes,если дл¤ двух заданных вершин существует ребро,которое их соедин¤ет %-------------------------------------------------------- adjacent(X,Y,1,graf(Vertex,Rib)):- belong(r(X,Y),Rib); belong(r(Y,X),Rib). %-------------------------------------------------------- % ?бьединение 2х списков в один %-------------------------------------------------------- include(Path,L,[Path|L]). %-------------------------------------------------------- % ?ахождение ациклического пути в графе % входные параметры: % graf(Vertex,Rib)   - граф % A,Z                - две вершины графа % % выходной параметр: % Path  -  ациклический путь между A и Z %-------------------------------------------------------- path(A,Z,graf(Vertex,Rib),Path):- path1(A,[Z],graf(Vertex,Rib),Path). path(A,Z,graf(Vertex,Rib),[]). % (чтобы было [] в конце) path1(A,[A|Path1],graf(Vertex,Rib),[A|Path1]). path1(A,[Y|Path1],graf(Vertex,Rib),Path):- adjacent(X,Y,1,graf(Vertex,Rib)),                                                       not belongList(X,Path1),                                           path1(A,[X,Y|Path1],graf(Vertex,Rib),Path). %-------------------------------------------------------- % принадлежность пути множеству пуей %--------------------------------------------------------                                           belongPath(Path,[Head|Tail]):-Path=Head. belongPath(Path,[Head|Tail]):- not(Path=Head), belongPath(Path,Tail). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %  pathList(a,b, graf([a,b,c,d],[r(a,d),r(a,c),r(b,c),r(b,d)]), [], L) %  countSimple(a,b, graf([a,b,c,d],[r(a,d),r(a,c),r(b,c),r(b,d),r(a,b)]), C, L) %  count2(a,b, graf([a,b,c,d],[r(a,d),r(a,c),r(b,c),r(b,d),r(a,b)]), 3, C, L) % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %-------------------------------------------------------- % количество элементов в списке % входные параметры: % L - список % % в?ходные параметры: % &#9472;1 - количество элементов %-------------------------------------------------------- length([],0). length([H|L],C1):-length(L,C),C1 is C+1. %-------------------------------------------------------- % количество элементов в списке, длина которых менее N % входные параметры: % L - список % % в?ходные параметры: % &#9472;1 - количество элементов %-------------------------------------------------------- cntLess([],N,0). cntLess([H|L],N,C1):-cntLess(L,N,C),length(H,LH),((LH<N)->(C1 is C+1);(C1 is C)). %-------------------------------------------------------- % список уникальных(простых) путей % входные параметры: % V,V1     - вершины,между которыми производитс¤ поиск % graf(Vertex,Rib) - граф(?ершины,&#9472;ебра) % PrevList - начальное условие (должно быть = []) % % в?ходные параметры: % XList    - список ?&#9472;?' простых путей графа %-------------------------------------------------------- pathList(V,V1,graf(Vertex,Rib),PrevList, XList):- path(V,V1,graf(Vertex,Rib),Path), % выборка простых путей length(Path,Len), % длина текущего пути (Len=0-> % проверка длины на 0 (XList = PrevList,!) % если длина=0, то заканчиваем поиск (значит все пути закончились) ; % в противном случае (not(belongPath(Path,PrevList)),include(Path,PrevList,List), % добавление элемента в список pathList(V,V1,graf(Vertex,Rib),List,XList) % рекурси¤ ),! % если мы здесь, значит список кончилс¤ ). % бектрекинг не требуетс¤, т.к. безсмысленно. %-------------------------------------------------------- % ?аходит количество простых путей в графе % входные параметры: % V,V1     - вершины,между которыми производитс¤ поиск % graf(Vertex,Rib) - граф(?ершины,&#9472;ебра) % % в?ходные параметры: % Kolvo    - количество простых путей в графе % PathList - список простых путей %-------------------------------------------------------- countSimple(V,V1,graf(Vertex,Rib),Kolvo,PathList):- pathList(V,V1,graf(Vertex,Rib), [], PathList), % заполнение PathList, всеми простыми пут¤ми из графа length(PathList, Kolvo). % подсчет количества простых путей %-------------------------------------------------------- % ?аходит количество простых путей в графе, длина которых менее N % входные параметры: % V,V1     - вершины,между которыми производитс¤ поиск % graf(Vertex,Rib) - граф(?ершины,&#9472;ебра) % N - целое число % % в?ходные параметры: % Kolvo    - количество простых путей в графе меньших N % PathList - список ?&#9472;?' простых путей %-------------------------------------------------------- count2(V,V1,graf(Vertex,Rib),N,Kolvo,PathList):- pathList(V,V1,graf(Vertex,Rib), [], PathList), % заполнение PathList, всеми простыми пут¤ми из графа cntLess(PathList, N, Kolvo). % подсчет количества таких путей
popoff
Yuri
Июл, 2004
Сообщений: 923
popoff url://forum.message:1007

Вы забыли сделать это:

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

popoffфорумы popoff.donetsk.ua

Без этого в Вашей программе и черт ногу сломит, не только Вы или Я.
Я могу помочь Вам на примере, остальное Вам придется сделать самостоятельно. Ничего нового Вам писать тут не нужно. Просто улучшите вид уже имеющегося.

belong(r(X,Y),[Head|Tail]):- r(X,Y)=Head; belong(r(X,Y),Tail).

targetфорумы popoff.donetsk.ua

Пишем в два предиката и убираем все сравнения.

<?code belong(r(X,Y),[r(X,Y)|Tail]). belong(r(X,Y),[_|Tail]):- belong(r(X,Y),Tail). ?>

belongList(X,[Head|Tail]):- X=Head.
belongList(X,[Head|Tail]):- not X=Head,belongList(X,Tail).

targetфорумы popoff.donetsk.ua

Отрицание здесь излишне: в предыдущем предикате Вы его не ставили, зачем поставили здесь? Но даже если Вам так хочется обезопаситься, Вы можете это сделать, введя отсечение:

<?code belongList(X,[X|Tail]):-!. belongList(X,[_|Tail]):-belongList(X,Tail). ?>

adjacent(X,Y,1,graf(Vertex,Rib)):- belong(r(X,Y),Rib); belong(r(Y,X),Rib).

targetфорумы popoff.donetsk.ua

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

Тем не менее, я могу предположить, что в этой строчке на этапе компиляции должно выводиться предупреждение: переменная используется только один раз. Я не знаю, что насчет Вашей версии Пролога, но в турбопрологе это предупреждение можно отключить. От отключения предупреждения, однако, ошибка в тексте программы не исчезает примерно по той же причине, по которой не исчезает опасность, если бы страус прятал голову в песок.

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

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

Я написал бы как-нибудь так:

<?code adjacent(X,Y,graf(_,Rib)):-belong(r(X,Y),Rib). adjacent(X,Y,graf(_,Rib)):-belong(r(Y,X),Rib). ?>

%-------------------------------------------------------- % ?бьединение 2х списков в один %-------------------------------------------------------- include(Path,L,[Path|L]).

targetфорумы popoff.donetsk.ua

Нет, без доменов и без версии Пролога я не понимаю.

В классическом прологе, если мне не изменяет память, список как раз тем и отличается от структуры, что все элементы списка имеют один тип. А это означает, что Ваш комментарий «обьединение 2х списков в один» никак не вяжется с include(Path,L,[Path|L])., разве что только L - это список списков элементов такого же типа, как список Path. Фактически получается, что L - это дерево, которое можно описать только используюя альтернативные домены.

Если L - это дерево, то этот предикат не выполняет объединение двух списокв в один, а добавляет в дерево новую вершину, самым левым ребенком корневой вершины.

Вы уверены, что Вы запускали эту программу?


С остальным, думаю, Вы можете разобраться самостоятельно.

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

Если не секрет, для чего Вы решаете эту задачу?

________________________________
Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить.
target
Таня
Дек, 2005
Сообщений: 7
target url://forum.message:1008

Спасибо огромное!!!!!!
Предикат написала-все работает
Версия-Amzi! Prolog.
Пишу для себя-у меня сегодня экзамен был по искусственному интеллекту.нужно было графы досдать.

popoff
Yuri
Июл, 2004
Сообщений: 923
popoff url://forum.message:1009

Ну, выложили бы решение, чтобы люди пользовались

________________________________
Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить.
target
Таня
Дек, 2005
Сообщений: 7
target url://forum.message:1010

Предикат,вычисляющий все пути на графе(циклические и простые):


path_all1(F,T,graf(Vertex,Rib),[F,T]):- adjacent(F,T,graf(Vertex,Rib)).

path_all1(F,T,graf(Vertex,Rib),[F|A]):-
                        belongList(Z,Vertex),
                        adjacent(F,Z,graf(Vertex,Rib)),                        
                        (del_el(r(F,Z),Rib,Rib1);del_el(r(Z,F),Rib,Rib1)),
                        path_all1(Z,T,graf(Vertex,Rib1),A).


вспомогательные предикаты:
del_el(El,[El|A],A).
del_el(El,[Y|L],[Y|L1]):-del_el(El,L,L1).

belong(r(X,Y),[Head|Tail]):- r(X,Y)=Head; belong(r(X,Y),Tail).

belongList(X,[X|Tail]).
belongList(X,[Y|Tail]):- belongList(X,Tail).


ЗЫ: остальные см выше

Внимание! Этот топик устарел. Пожалуйста, создайте новый топик, чтобы задать интересующий Вас вопрос.

Страницы: [1]
<< Новый  |  Старый >>  |  Ответ не возможен
Вход
Поиск[?]:
Гинеколог, стоматолог, психотерапевт в Донецке