| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Prolog > Поиск пути макс. веса в графе (Visual Prolog 5.2) |
| Автор: prognovichok 9.1.2011, 18:53 |
| Помогите решить задачку на Прологе: В графе, ребрам которого приписаны веса, написать программу поиска пути максимального веса, соединяющий заданную пару вершин. Вес пути равен сумме весов ребер, входящих в этот путь. Граф задается с помощью предиката ребро(Имя_ребра, Вершина_начало_ребра, Вершина_конец_ребра, Вес_ребра). Заранее спасибо! |
| Автор: Грымзик 9.1.2011, 19:21 |
| Книга Сошникова "Парадигма логического программирования". В ней есть реализация поиска для весового графа. Там минимальный путь, но это очень легко изменяется на максимальный, путем замены знака в предикате placeone. |
| Автор: prognovichok 10.1.2011, 08:43 |
| С другом сделали... даже работает) если кому пригодится, буду рад) domains list = integer* predicates nondeterm ребро (symbol, integer, integer, integer) % ребро графа nondeterm ребро2 (symbol, integer, integer, integer) % обратное ребро (т.к. граф неориентированный) nondeterm concatenation (list, list, list) % конкатенация nondeterm belongs (integer, list) % предикат принадлежности вершины списку nondeterm solution (integer, integer, list, list, integer) % предикат решение (определяет пути и их длины) nondeterm maxElementOfList (list, integer) % поиск максимального элемента списка nondeterm max (integer, integer, integer) % определение максимального элемента nondeterm maxSolve (integer, integer, list, integer) % определение пути максимального веса clauses ребро (a, 1, 2, 6). ребро (b, 2, 3, 3). ребро (c, 3, 4, 7). ребро (d, 4, 5, 2). ребро (e, 5, 1, 4). ребро (f, 5, 6, 3). ребро (h, 4, 7, 1). ребро (g, 6, 7, 5). ребро2 (X, Y, Z, V) :- ребро (X, Y, Z, V); ребро (X, Z, Y, V). max (X, Y, MAX):- X >= Y, MAX = X, !. max (X, Y, MAX):- Y > X, MAX = Y. maxElementOfList ([X], X) :- !. maxElementOfList (X, M) :- X = [H|T], maxElementOfList (T, M2), max (H, M2, M). concatenation ([], List, List). concatenation ([M|NewList], NewList2, [M|N]):- concatenation (NewList, NewList2, N). belongs (X, [X|_]) :- !. belongs (X, [H|T]) :- belongs (X, T). % при отсутствии промежуточных вершин: solution (InitialVertex, TerminalVertex, PassedList, Path, Length) :- ребро2 (_, InitialVertex, TerminalVertex, Weight), concatenation ([InitialVertex], [TerminalVertex], Way), Path = Way, Length = Weight. % с учетом промежуточных вершин: solution (InitialVertex, TerminalVertex, PassedList, Path, Length) :- ребро2 (_, InitialVertex, IntermediateVertex, Weight), not(belongs(IntermediateVertex, PassedList)), concatenation ([InitialVertex], PassedList, PassedList1), concatenation ([TerminalVertex], PassedList1, PassedList2), solution (IntermediateVertex, TerminalVertex, PassedList2, Path2, Length2), concatenation ([InitialVertex], Path2, Path), Length = Length2 + Weight. maxSolve(InitialVertex, TerminalVertex, Path, MaxLength):- findall (Length, solution(InitialVertex, TerminalVertex, [], _, Length), ListLenght), maxElementOfList (ListLenght, MaxLength), solution (InitialVertex, TerminalVertex, [], Path, MaxLength). goal maxSolve(7, 3, Path, Length). Кстати, программа работает и на минимальный вес, нужно только в предикате max поменять знак с ">" на "<". Ну и для наглядности переименовать max в min)) |