Помогите решить задачку на Прологе:

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

Заранее спасибо!

Книга Сошникова "Парадигма логического программирования". В ней есть реализация поиска для весового графа. Там минимальный путь, но это очень легко изменяется на максимальный, путем замены знака в предикате placeone.

С другом сделали... даже работает) если кому пригодится, буду рад)

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

Это сообщение отредактировал(а) prognovichok - 10.1.2011, 18:07