Задача коммивояжёра с возвратом в "магазин" - Prolog

Узнай цену своей работы

Формулировка задачи:

Вроде и тема раскрытая (код можно найти, для этой задачи), но что-то я застрял на
Листинг программы 
  1. retract(oil(To,Y)),
По условию задачи продавец развозит топливо по городам. Если у него топливо закончилось - ему надо возвратиться в магазин (store). Города пройти по одному разу. Нашёл код, добавил обработку значений для запаса топлива продавца: если=0, то сразу в город; если меньше необходимого городу то уменьшаем данные у города, и оправляем продавца в магазин, если больше, уменьшаем запасы продавца и идём в следующий город.
Листинг программы 
  1. :- dynamic way/3.
  2. :- dynamic way/2.
  3. :- dynamic oil/2.
  4. :- dynamic capacity/1.
  5. % ***************************************************************************
  6. % Distance between trees.
  7. way(town,town2,50).
  8. way(town3,town4,50).
  9. way(town5,town4,35).
  10. way(town2,town6,55).
  11. way(town5,town6,35).
  12. way(town,town7,40).
  13. way(town7,town3,35).
  14.  
  15. % Distance between the well and the trees.
  16. way(town,13).
  17. way(town2,19).
  18. way(town3,22).
  19. way(town4,34).
  20. way(town5,19).
  21. way(town6,22).
  22. way(town7,34).
  23.  
  24. % 
  25. oil(town,3).
  26. oil(town2,9).
  27. oil(town3,2).
  28. oil(town4,4).
  29. oil(town5,9).
  30. oil(town6,2).
  31. oil(town7,4).
  32.  
  33. % Bucket capacity.
  34. capacity(5).
  35.  
  36. % ***************************************************************************
  37. node(Node):-
  38.   way(Node, _Destination,_);
  39.   way(_Source, Node,_).
  40.  
  41. % Определим предикат, возвращающий вершину – либо начало, либо конец дуги, 
  42. % получим все вершины при помощи findall, а затем – преобразуем список во множество. 
  43. get_nodes(SetOfNodes):-
  44.     findall(Node, node(Node), Nodes),
  45.     list_to_set(Nodes, SetOfNodes).
  46.     
  47. % ***************************************************************************  
  48. % Правило, проверяющее существование ребра (без учета направления):
  49. exist_edge(From, To, Lengh):-
  50.     way(From, To, Lengh);   
  51.     way(To, From, Lengh).
  52.   
  53. dfs(From, To, _, [From, To],_, _):- 
  54.     exist_edge(From, To, _).
  55. dfs(From, To, Buffer, [From|Path], AllLengh, Well):-
  56.  
  57.     exist_edge(From, X, Lengh),
  58.     not(member(X, Buffer)),
  59.  
  60.     oil(X,Y),
  61.     
  62.     % первоначальный вариант, комивояжёр в городе без топлива
  63.     (Well=0, capacity(NewWell), 
  64.         way(From,Z), 
  65.         % изменяем путь
  66.         NewLenth is AllLengh + Z, 
  67.         % добавляем путь в магазин и из магазина
  68.         dfs(X, To, [From|[store|Buffer]], Path, NewLenth, NewWell);
  69.     
  70.         % вариант, топлива хватит для потребностей города
  71.         (Well>Y,  NewLenth is AllLengh + Lengh,
  72.             NewWell is (Well-Y),  
  73.             % идём дальше с остаткаим топлива
  74.             dfs(X, To, [From|Buffer], Path, NewLenth, NewWell);
  75.             
  76.             % вариант, топлива не хватит для потребностей города
  77.             Well<Y, way(From,Z), capacity(W), 
  78.             % изменяем путь
  79.             NewLenth is AllLengh + Z, 
  80.                 % новая потребность города
  81.                 NewWell is (Well-Y),    
  82.                     % удаляю старое, необходимое ко-во топлива 
  83.                     retract(oil(To,Y)),
  84.                         % добавляю новое, необходимое ко-во топлива 
  85.                         assertz(oil(From, NewWell)), 
  86.                             dfs(From, To, Buffer, [From|[store|Path]], Path, NewLenth, W))).
  87.  
  88. hamiltonian_graph(Path, Well):- 
  89.     % получаем все вершины (в Nodes) 
  90.     get_nodes(Nodes), 
  91.     length(Nodes, NodesCount),
  92.     % набираем топливо
  93.     capacity(V),
  94.     dfs(Node, Node, [store], Path, V, Well), 
  95.     list_to_set(Path, PathNodesSet), 
  96.     length(PathNodesSet, NodesCount), !.
За одно и путь считаю.

Решение задачи: «Задача коммивояжёра с возвратом в "магазин"»

textual
Листинг программы 
  1. :- dynamic way/3.
  2. :- dynamic way/2.
  3. :- dynamic oil/2.
  4. :- dynamic capacity/1.
  5. % ***************************************************************************
  6. % Distance between towns.
  7. way(town1,town2,50).
  8. way(town3,town4,50).
  9. way(town5,town4,35).
  10. way(town2,town6,55).
  11. way(town5,town6,35).
  12. way(town1,town7,40).
  13. way(town7,town3,35).
  14.  
  15. % Distance between the well and the towns.
  16. way(town1,13).
  17. way(town2,19).
  18. way(town3,22).
  19. way(town4,34).
  20. way(town5,19).
  21. way(town6,22).
  22. way(town7,34).
  23.  
  24. % 
  25. oil(town1,3).
  26. oil(town2,9).
  27. oil(town3,2).
  28. oil(town4,4).
  29. oil(town5,9).
  30. oil(town6,2).
  31. oil(town7,4).
  32.  
  33. % Bucket capacity.
  34. capacity(5).
  35.  
  36. % ***************************************************************************
  37. % учёт двунаправленности каждой дороги между городами
  38. way_new(X,Y,Z):- way(X,Y,Z); way(Y,X,Z).
  39.  
  40. % учёт двунаправленности каждой дороги между городом и магазином
  41. way_new(X,Y):- way(X,Y); way(Y,X).
  42.  
  43. % отновной предикат наждения пути робота
  44. % Start - город, который уже обслужил коммивояжёр
  45. % Way - список городов, путь коммивояжёра
  46. % WayCost - длина этого пути
  47. com_way(Start, Way, WayCost):-
  48.     % собираем список-множество всех городов
  49.     setof(X,Y^Z^way_new(X,Y,Z), Tree_set),
  50.     % находим любое соседний город (Finish)
  51.     way_new(Finish, Start, Cost),
  52.     % Удаляем Finish из множества городов
  53.     delete_first(Finish, Tree_set, Tree_set1),
  54.  
  55.     capacity(V),
  56.     oil(Start,W),
  57.     
  58.     get_oil(V, W, Start, 0, [well]), 
  59.     write(V), write(' '), write(W), write(' '), writeln(Start),
  60.  
  61.     % находим путь без циклов между Start и Finish, проходящий через все города
  62.     path_com(Finish, Start, Way1, WayCost1, Tree_set1),
  63.     % пересчитываем путь и его длину
  64.     WayCost is WayCost1 + Cost, Way=[Start|Way1].
  65.     
  66. % Вспомогательный предикат: удаление элемента списка
  67. delete_first(X,[X|T],T):- !.
  68.     delete_first(X,[Y|T],[Y|TY]):- delete_first(X,T,TY).
  69.     
  70. % предикат поиска пути Way без циклов, длина пути WayCost, между городами Start и Finish,
  71. % проходящий через все города из множества City_set
  72.     path_com(Start,Finish,Way,WayCost,City_set):-
  73.         path(Start,Finish,Way,WayCost,City_set,[Finish],0).
  74.         
  75. % базовый вспомогательный предикат поиска пути, 
  76. % предпоследние два аргумента - накапливающие параметры для пути и его стоимости
  77.    % когда все деревья уже посещены
  78.    path(Finish,Finish,Way,WayCost,[],Way,WayCost).
  79.     % иначе, идем путь из X в Finish через X
  80.     path(Finish,Finish,Way,WayCost,[],Way,WayCost).
  81.     % иначе, идем путь из X в Finish через X
  82.     path(X,Finish,Way,WayCost,City_set,PartWay,PartCost):- 
  83.     % двигаемся к следующему дереву
  84.             way_new(X,Y,Cost),   % есть дорога к дереву
  85.             member(Y,City_set),  % Y ещё не посещён
  86.             % удаляем Y из множества непосещённых деревьев
  87.             delete_first(Y,City_set,City_set1), 
  88.             % пересчёт длины пройденного пути
  89.             PartCost1 is PartCost+Cost,
  90.             % рекурсивно ищем путь из Y в Finish
  91.             path(Y,Finish,Way,WayCost,City_set1,[X|PartWay],PartCost1).
  92.  
  93.             
  94. % предикат нахождения самого короткого пути
  95.     best_com_way(Start,Way):-
  96.         % находим все пути с их именами
  97.         findall(WayCost1/Way1,
  98.         com_way(Start,Way1,WayCost1), AllWays),
  99.         % находим минимальную длину пути
  100.         min_cost(AllWays,MinCost),
  101.         % выбор любого пути минимальной длины
  102.         member(MinCost/Way,AllWays).
  103.         
  104. % вспомогательный предикат вычисления минимальной длины пути:
  105. % если путь один, то его длина минимальная,
  106. % иначе выбор минимума из длины первого пути и длины минимального пути хвоста списка
  107.     min_cost([WayCost/_],WayCost):- !.
  108.     min_cost([WayCost1/_|Tail],MinCost):- 
  109.         min_cost(Tail,MinCost1),
  110.         MinCost is min(WayCost1,MinCost1).
  111. % **************************************************************
  112.  
  113. % get_oil(5,9, 'town5', 0, ['town5']).
  114. get_oil(V, 0, Tree, Length, WellPath):- writeln('1'),!.
  115.          
  116. get_oil(V, W, Tree, Length, WellPath):- writeln('2'),
  117.     W<V,    
  118.     V2 is V-W,
  119.     get_oil(V2, 0, Tree, Length, WellPath). 
  120.  
  121. get_oil(V, W, Tree, Length, WellPath):- writeln('3'),
  122.     W>=V,
  123.     W2 is W-V, 
  124.     capacity(V2),
  125.     way(Tree,L),
  126.     NewLength is Length+L*2,
  127.     get_oil(V2, W2, Tree, NewLength, [Tree|[well|WellPath]]).
  128.  
  129. % **************************************************************

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 4.2 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут