Задача на Prolog разберите пожалуйста
Формулировка задачи:
Задание № 29: На одном участке земли размечено 36 кругов, в каждом из кругов стоит мешок, содержащий столько долларов ,сколько указано на схеме. Разрешается брать любое число мешков, лишь бы не проходить дважды по одной и той же прямой. Соберите наибольшую сумму.
Код программы:
Листинг программы
- domains
- list = integer*
- predicates
- nondeterm линия (integer, list) % линия графа
- nondeterm ребро (symbol, integer, integer) % ребро графа
- nondeterm ребро2 (symbol, integer, integer) % обратное ребро (т.к. граф неориентированный)
- nondeterm конкатенация (list, list, list) % конкатенация
- nondeterm принадлежит (integer, list) % предикат принадлежности вершины списку
- nondeterm принадлежит1 (integer, integer, list) % принадлежность ребра линии
- nondeterm поиск (integer, integer, list, list, integer, integer, list, list) % предикат решение (определяет пути и их длины)
- nondeterm максэлем (list, integer) % поиск максимального элемента списка
- nondeterm определение (integer, integer, integer) % определение максимального элемента
- nondeterm макспуть (integer, integer, list, integer) % определение пути максимального веса
- clauses
- ребро (ребро1, 11, 26).
- ребро (ребро2, 12, 25).
- ребро (ребро3, 12, 21).
- ребро (ребро4, 13, 26).
- ребро (ребро5, 13, 23).
- ребро (ребро6, 14, 21).
- ребро (ребро7, 14, 24).
- ребро (ребро8, 15, 23).
- ребро (ребро9, 15, 22).
- ребро (ребро10, 16, 24).
- ребро (ребро11, 25, 33).
- ребро (ребро12, 26, 34).
- ребро (ребро13, 26, 32).
- ребро (ребро14, 21, 33).
- ребро (ребро15, 21, 35).
- ребро (ребро16, 23, 32).
- ребро (ребро17, 23, 36).
- ребро (ребро18, 24, 35).
- ребро (ребро19, 24, 31).
- ребро (ребро20, 22, 36).
- ребро (ребро21, 34, 44).
- ребро (ребро22, 33, 42).
- ребро (ребро23, 33, 45).
- ребро (ребро24, 32, 44).
- ребро (ребро25, 32, 46).
- ребро (ребро26, 35, 45).
- ребро (ребро27, 35, 41).
- ребро (ребро28, 36, 46).
- ребро (ребро29, 36, 43).
- ребро (ребро30, 31, 41).
- ребро (ребро31, 42, 51).
- ребро (ребро32, 44, 56).
- ребро (ребро33, 44, 54).
- ребро (ребро34, 45, 51).
- ребро (ребро35, 45, 52).
- ребро (ребро36, 46, 54).
- ребро (ребро37, 46, 53).
- ребро (ребро38, 41, 52).
- ребро (ребро39, 41, 55).
- ребро (ребро40, 43, 53).
- ребро (ребро41, 56, 65).
- ребро (ребро42, 51, 63).
- ребро (ребро43, 51, 66).
- ребро (ребро44, 54, 65).
- ребро (ребро45, 54, 61).
- ребро (ребро46, 52, 66).
- ребро (ребро47, 52, 62).
- ребро (ребро48, 53, 61).
- ребро (ребро49, 53, 64).
- ребро (ребро50, 55, 62).
- линия (1, [ 11,26,32,46,53,64 ]).
- линия (2, [ 12,21,35,41,55 ]).
- линия (3, [ 13,23,36,43 ]).
- линия (4, [ 14,24,31 ]).
- линия (5, [ 15,22 ]).
- линия (6, [ 56,65 ]).
- линия (7, [ 42,51,66 ]).
- линия (8, [ 34,44,54,61 ]).
- линия (9, [ 25,33,45,52,62 ]).
- линия (10, [ 16,24,35,45,51,63 ]).
- линия (11, [ 15,23,32,44,56 ]).
- линия (12, [ 14,21,33,42 ]).
- линия (13, [ 13,26,34 ]).
- линия (14, [ 12,25 ]).
- линия (15, [ 22,36,46,54,65 ]).
- линия (16, [ 31,41,52,66 ]).
- линия (17, [ 43,53,61 ]).
- линия (18, [ 55,62 ]).
- ребро2 (X, Y, Z) :- ребро (X, Y, Z); ребро (X, Z, Y).
- определение (X, Y, Макс):- X >= Y, Макс = X, !.
- определение (X, Y, Макс):- Y > X, Макс = Y.
- максэлем ([X], X) :- !.
- максэлем (X, M) :- X = [H|T], максэлем (T, M2), определение (H, M2, M).
- конкатенация ([], Список, Список).
- конкатенация ([M|Список1], Список2, [M|N]):- конкатенация (Список1, Список2, N).
- принадлежит (X, [X|_]) :- !.
- принадлежит (X, [_|T]) :- принадлежит (X, T).
- принадлежит1(X,Y,L):- ребро2(_,X,Y),
- линия(_,L),
- принадлежит(X,L),
- принадлежит(Y,L).
- % при отсутствии промежуточных вершин:
- поиск (Начальнаявершина, Конечнаявершина, Список, Пройденпуть, Длина, Первая, Линии, Линии2) :-
- ребро2 (_, Начальнаявершина, Конечнаявершина),
- принадлежит1(Начальнаявершина, Конечнаявершина, Линия),
- линия(Название,Линия),
- not(принадлежит(Название,Линии)),
- конкатенация ([Начальнаявершина], [Конечнаявершина], Путь),
- конкатенация ([Название], [], Линии2),
- Пройденпуть = Путь,
- Длина = (Конечнаявершина)mod(10) + (Первая)mod(10).
- % с учетом промежуточных вершин:
- поиск (Начальнаявершина, Конечнаявершина, Список, Пройденпуть, Длина, Первая, Линии, Линии2) :-
- ребро2 (_, Начальнаявершина, Промежуточная),
- not(принадлежит(Промежуточная, Список)),
- принадлежит1(Начальнаявершина, Промежуточная, Линия),
- линия(Название,Линия),
- not(принадлежит(Название,Линии)),
- конкатенация([Название], Линии, Линии3),
- конкатенация ([Начальнаявершина], Список, Список1),
- конкатенация ([Конечнаявершина], Список1, Список2),
- поиск (Промежуточная, Конечнаявершина, Список2, Пройденпуть2, Длина2, Первая, Линии3, Линии4),
- конкатенация ([Начальнаявершина], Пройденпуть2, Пройденпуть),
- конкатенация (Линии3, Линии4, Линии2),
- Длина = Длина2 + (Промежуточная)mod(10).
- макспуть(Начальнаявершина, Конечнаявершина, Пройденпуть, Максдлина):-
- findall (Длина, поиск(Начальнаявершина, Конечнаявершина, [], _, Длина, Начальнаявершина, [], _), Длинасписка),
- максэлем (Длинасписка, Максдлина),
- поиск (Начальнаявершина, Конечнаявершина, [], Пройденпуть, Максдлина, Начальнаявершина, [], _).
Программа работает правильно, обьясните пожалуйста как работает
Решение задачи: «Задача на Prolog разберите пожалуйста»
textual
Листинг программы
- domains
- list = integer*
- predicates
- nondeterm линия (integer, list) % линия графа
- nondeterm ребро (symbol, integer, integer) % ребро графа
- nondeterm ребро2 (symbol, integer, integer) % обратное ребро (т.к. граф неориентированный)
- nondeterm конкатенация (list, list, list) % конкатенация
- nondeterm принадлежит (integer, list) % предикат принадлежности вершины списку
- nondeterm принадлежит1 (integer, integer, list) % принадлежность ребра линии
- nondeterm поиск (integer, integer, list, list, integer, integer, list, list) % предикат решение (определяет пути и их длины)
- nondeterm максэлем (list, integer) % поиск максимального элемента списка
- nondeterm определение (integer, integer, integer) % определение максимального элемента
- nondeterm макспуть (integer, integer, list, integer) % определение пути максимального веса
- clauses
- ребро (ребро1, 11, 26).
- ребро (ребро2, 12, 25).
- ребро (ребро3, 12, 21).
- ребро (ребро4, 13, 26).
- ребро (ребро5, 13, 23).
- ребро (ребро6, 14, 21).
- ребро (ребро7, 14, 24).
- ребро (ребро8, 15, 23).
- ребро (ребро9, 15, 22).
- ребро (ребро10, 16, 24).
- ребро (ребро11, 25, 33).
- ребро (ребро12, 26, 34).
- ребро (ребро13, 26, 32).
- ребро (ребро14, 21, 33).
- ребро (ребро15, 21, 35).
- ребро (ребро16, 23, 32).
- ребро (ребро17, 23, 36).
- ребро (ребро18, 24, 35).
- ребро (ребро19, 24, 31).
- ребро (ребро20, 22, 36).
- ребро (ребро21, 34, 44).
- ребро (ребро22, 33, 42).
- ребро (ребро23, 33, 45).
- ребро (ребро24, 32, 44).
- ребро (ребро25, 32, 46).
- ребро (ребро26, 35, 45).
- ребро (ребро27, 35, 41).
- ребро (ребро28, 36, 46).
- ребро (ребро29, 36, 43).
- ребро (ребро30, 31, 41).
- ребро (ребро31, 42, 51).
- ребро (ребро32, 44, 56).
- ребро (ребро33, 44, 54).
- ребро (ребро34, 45, 51).
- ребро (ребро35, 45, 52).
- ребро (ребро36, 46, 54).
- ребро (ребро37, 46, 53).
- ребро (ребро38, 41, 52).
- ребро (ребро39, 41, 55).
- ребро (ребро40, 43, 53).
- ребро (ребро41, 56, 65).
- ребро (ребро42, 51, 63).
- ребро (ребро43, 51, 66).
- ребро (ребро44, 54, 65).
- ребро (ребро45, 54, 61).
- ребро (ребро46, 52, 66).
- ребро (ребро47, 52, 62).
- ребро (ребро48, 53, 61).
- ребро (ребро49, 53, 64).
- ребро (ребро50, 55, 62).
- линия (1, [ 11,26,32,46,53,64 ]).
- линия (2, [ 12,21,35,41,55 ]).
- линия (3, [ 13,23,36,43 ]).
- линия (4, [ 14,24,31 ]).
- линия (5, [ 15,22 ]).
- линия (6, [ 56,65 ]).
- линия (7, [ 42,51,66 ]).
- линия (8, [ 34,44,54,61 ]).
- линия (9, [ 25,33,45,52,62 ]).
- линия (10, [ 16,24,35,45,51,63 ]).
- линия (11, [ 15,23,32,44,56 ]).
- линия (12, [ 14,21,33,42 ]).
- линия (13, [ 13,26,34 ]).
- линия (14, [ 12,25 ]).
- линия (15, [ 22,36,46,54,65 ]).
- линия (16, [ 31,41,52,66 ]).
- линия (17, [ 43,53,61 ]).
- линия (18, [ 55,62 ]).
- ребро2 (X, Y, Z) :- ребро (X, Y, Z); ребро (X, Z, Y).
- определение (X, Y, Макс):- X >= Y, Макс = X, !.
- определение (X, Y, Макс):- Y > X, Макс = Y.
- максэлем ([X], X) :- !.
- максэлем (X, M) :- X = [H|T], максэлем (T, M2), определение (H, M2, M).
- конкатенация ([], Список, Список).
- конкатенация ([M|Список1], Список2, [M|N]):- конкатенация (Список1, Список2, N).
- принадлежит (X, [X|_]) :- !.
- принадлежит (X, [_|T]) :- принадлежит (X, T).
- принадлежит1(X,Y,L):- ребро2(_,X,Y),
- линия(_,L),
- принадлежит(X,L),
- принадлежит(Y,L).
- % при отсутствии промежуточных вершин:
- поиск (Начальнаявершина, Конечнаявершина, Список, Пройденпуть, Длина, Первая, Линии, Линии2) :-
- ребро2 (_, Начальнаявершина, Конечнаявершина),
- принадлежит1(Начальнаявершина, Конечнаявершина, Линия),
- линия(Название,Линия),
- not(принадлежит(Название,Линии)),
- конкатенация ([Начальнаявершина], [Конечнаявершина], Путь),
- конкатенация ([Название], [], Линии2),
- Пройденпуть = Путь,
- Длина = (Конечнаявершина)mod(10) + (Первая)mod(10).
- % с учетом промежуточных вершин:
- поиск (Начальнаявершина, Конечнаявершина, Список, Пройденпуть, Длина, Первая, Линии, Линии2) :-
- ребро2 (_, Начальнаявершина, Промежуточная),
- not(принадлежит(Промежуточная, Список)),
- принадлежит1(Начальнаявершина, Промежуточная, Линия),
- линия(Название,Линия),
- not(принадлежит(Название,Линии)),
- конкатенация([Название], Линии, Линии3),
- конкатенация ([Начальнаявершина], Список, Список1),
- конкатенация ([Конечнаявершина], Список1, Список2),
- поиск (Промежуточная, Конечнаявершина, Список2, Пройденпуть2, Длина2, Первая, Линии3, Линии4),
- конкатенация ([Начальнаявершина], Пройденпуть2, Пройденпуть),
- конкатенация (Линии3, Линии4, Линии2),
- Длина = Длина2 + (Промежуточная)mod(10).
- макспуть(Начальнаявершина, Конечнаявершина, Пройденпуть, Максдлина):-
- findall (Длина, поиск(Начальнаявершина, Конечнаявершина, [], _, Длина, Начальнаявершина, [], _), Длинасписка),
- максэлем (Длинасписка, Максдлина),
- поиск (Начальнаявершина, Конечнаявершина, [], Пройденпуть, Максдлина, Начальнаявершина, [], _).
- goal
- макспуть(11, 65, Пройденпуть, Длина).
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д