|
Страницы: [1] | << Новый | Старый >> | Ответ не возможен |
Внимание! Этот топик устарел. Пожалуйста, создайте новый топик, чтобы задать интересующий Вас вопрос.
Автор | Сообщение | |||||
target Таня Дек, 2005 Сообщений: 7 | target url://forum.message:963 Задача по графам Задан граф.Для пары его вершин определить: Вот как делала,но пункты б И в не работают 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). minPath(V,V1,graf(Vertex,Rib),MinCost,Path):- path(V,V1,graf(Vertex,Rib),Path,MinCost), include(Path,L,[Path|L]). count(V,V1,graf(Vertex,Rib),N,Kolvo,SetPaths):- path(V,V1,graf(Vertex,Rib),Path,MinCost), % 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,_), | |||||
30.12.05 22:55 | URL сообщения | Приват | Инфо об авторе | |||||
popoff Yuri ![]() Июл, 2004 Сообщений: 923 | popoff url://forum.message:964 Я не люблю разбираться в больших кусках чужих программ. Надеюсь, Вы меня понимаете - представьте себе, что Вам требуется разобраться в чужой программе. Если Вы используете сложные объекты и альтернативные домены, то не могли бы вы приводить примеры вместе с разделом доменов? Как задается Ваш граф? ________________________________ Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить. | |||||
31.12.05 01:10 | URL сообщения | Приват | Инфо об авторе | |||||
target Таня Дек, 2005 Сообщений: 7 | target url://forum.message:965 Граф задается меожеством вершин и множеством ребер | |||||
31.12.05 17:16 | URL сообщения | Приват | Инфо об авторе | |||||
popoff Yuri ![]() Июл, 2004 Сообщений: 923 | popoff url://forum.message:966 Посмотрите в сторону предиката findall и сведите Вашу задачу к обработке списков.
Совсем-совсем не использовали? ~~~~~ 31 Дек 2005, 17:19 ~~~~~ А вообще я Вам посоветовал бы для начала просто упростить то, что у Вас уже есть. Уберите все операторы сравнения, когда Вы просто одну переменную сравниваете с другой, уберите все операторы сравнения на неравенство - в большинстве случаев это решается введением отсечений, уберите все точки с запятой - пишите лучше несколько утверждений. После таких изменений программа станет яснее и в нее проще будет добавить нужную Вам функциональность. ________________________________ Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить. | |||||
31.12.05 19:15 | URL сообщения | Приват | Инфо об авторе | |||||
target Таня Дек, 2005 Сообщений: 7 | target url://forum.message:1003 Спасибо за совет. | |||||
14.01.06 23:38 | URL сообщения | Приват | Инфо об авторе | |||||
popoff Yuri ![]() Июл, 2004 Сообщений: 923 | popoff url://forum.message:1004
Что именно у Вас не получается? Или Вы, говоря «не получается», имеете в виду «напишите за меня»? У Вас очень интересная задача, и мне было бы интересно ее решить. Но на этом форуме я не решаю задачи. Я могу помочь Вам решить Вашу задачу, но не решить ее за Вас. ________________________________ Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить. | |||||
15.01.06 00:15 | URL сообщения | Приват | Инфо об авторе | |||||
target Таня Дек, 2005 Сообщений: 7 | target url://forum.message:1005 Задача для ациклических путей мной решена полностью,(все 3 процедуры) | |||||
15.01.06 00:24 | URL сообщения | Приват | Инфо об авторе | |||||
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).
%--------------------------------------------------------
% ─войство смежности вершин(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 - список
%
% в?ходные параметры:
% ─1 - количество элементов
%--------------------------------------------------------
length([],0).
length([H|L],C1):-length(L,C),C1 is C+1.
%--------------------------------------------------------
% количество элементов в списке, длина которых менее N
% входные параметры:
% L - список
%
% в?ходные параметры:
% ─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) - граф(?ершины,─ебра)
% PrevList - начальное условие (должно быть = [])
%
% в?ходные параметры:
% XList - список ?─?' простых путей графа
%--------------------------------------------------------
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) - граф(?ершины,─ебра)
%
% в?ходные параметры:
% 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) - граф(?ершины,─ебра)
% N - целое число
%
% в?ходные параметры:
% Kolvo - количество простых путей в графе меньших N
% PathList - список ?─?' простых путей
%--------------------------------------------------------
count2(V,V1,graf(Vertex,Rib),N,Kolvo,PathList):-
pathList(V,V1,graf(Vertex,Rib), [], PathList), % заполнение PathList, всеми простыми пут¤ми из графа
cntLess(PathList, N, Kolvo). % подсчет количества таких путей
| |||||
15.01.06 00:32 | URL сообщения | Приват | Инфо об авторе | |||||
popoff Yuri ![]() Июл, 2004 Сообщений: 923 | popoff url://forum.message:1007 Вы забыли сделать это:
Без этого в Вашей программе и черт ногу сломит, не только Вы или Я.
Пишем в два предиката и убираем все сравнения. <?code belong(r(X,Y),[r(X,Y)|Tail]).
belong(r(X,Y),[_|Tail]):- belong(r(X,Y),Tail).
?>
Отрицание здесь излишне: в предыдущем предикате Вы его не ставили, зачем поставили здесь? Но даже если Вам так хочется обезопаситься, Вы можете это сделать, введя отсечение: <?code belongList(X,[X|Tail]):-!.
belongList(X,[_|Tail]):-belongList(X,Tail).
?>
Я не знаю, с какой версией Пролога Вы работаете. Я привык к простенькому турбопрологу. Это строготипизированный язык. В нем существует раздел доменов, в котором описываются типы. В Вашей программе используются сложные объекты, не зная, как эти объекты устроены, мне сложно понять, что делает этот предикат. Тем не менее, я могу предположить, что в этой строчке на этапе компиляции должно выводиться предупреждение: переменная используется только один раз. Я не знаю, что насчет Вашей версии Пролога, но в турбопрологе это предупреждение можно отключить. От отключения предупреждения, однако, ошибка в тексте программы не исчезает примерно по той же причине, по которой не исчезает опасность, если бы страус прятал голову в песок. И константная единица в аргументах правила почти всегда является излишней. Если Вам нужно помнить данные, то для этого обычно используют факты, а не правила. А зачем нужно помнить единицу, если честно, я себе с трудом представляю. И еще - точки с запятой - это как неправильное выравнивание. От того, что в программе не соблюдены отступы, она не перестает работать, но разобраться в ней становится очень тяжело. Я написал бы как-нибудь так: <?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]).”, разве что только L - это список списков элементов такого же типа, как список Path. Фактически получается, что L - это дерево, которое можно описать только используюя альтернативные домены. Если L - это дерево, то этот предикат не выполняет объединение двух списокв в один, а добавляет в дерево новую вершину, самым левым ребенком корневой вершины. Вы уверены, что Вы запускали эту программу? С остальным, думаю, Вы можете разобраться самостоятельно. Я не разбирался в Вашем очень длинном коде, но если бы эту задачу решал я, то могу предположить, что в предикате, который занимается непосредственным поиском путей, нужно вести дополнительный список пройденных вершин. Когда мы проходим по очередной дуге, то мы сначала смотрим, попадаем ли мы в вершину, в которой уже были или мы попадаем в новую вершину. Если попадаем в новую вершину, то переходим по дуге - делаем, скорее всего, так, как у вас сделано сейчас плюс добавляем эту вершину в список пройденных вершин. Если мы попадаем в вершину второй раз, то не переходим по дуге. При этом я исхожу из того, что Вы ищете все пути обходом графа в гулубину. Если не секрет, для чего Вы решаете эту задачу? ________________________________ Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить. | |||||
15.01.06 01:35 | URL сообщения | Приват | Инфо об авторе | |||||
target Таня Дек, 2005 Сообщений: 7 | target url://forum.message:1008 Спасибо огромное!!!!!! | |||||
15.01.06 02:49 | URL сообщения | Приват | Инфо об авторе | |||||
popoff Yuri ![]() Июл, 2004 Сообщений: 923 | popoff url://forum.message:1009 Ну, выложили бы решение, чтобы люди пользовались ________________________________ Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить. | |||||
15.01.06 04:32 | URL сообщения | Приват | Инфо об авторе | |||||
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]):- вспомогательные предикаты: belong(r(X,Y),[Head|Tail]):- r(X,Y)=Head; belong(r(X,Y),Tail). belongList(X,[X|Tail]). ЗЫ: остальные см выше | |||||
15.01.06 15:23 | URL сообщения | Приват | Инфо об авторе | |||||
Внимание! Этот топик устарел. Пожалуйста, создайте новый топик, чтобы задать интересующий Вас вопрос.
Страницы: [1] | << Новый | Старый >> | Ответ не возможен |
Вход |
Цитирование материалов моего сайта приветствуется! при условии видимой действующей! гиперссылки на мой сайт. [Ссылки] Если Вы нашли опечатку на этой странице, пожалуйста, выделите ее мышью и нажмите Ctrl+Enter. Сделаем язык чище! (c) Yuri Popoff, 2004 - 2008, popoff.donetsk.ua, style.donetsk.ua |
![]() |