1

我试图找到一条路径的最小成本，同时保留变量而Min不是回溯。下面的代码不起作用，但是它对我想要的东西有一个小小的了解。

Min 是保持当前最小值的变量，与新的值相比，Total如果Total较小，则NewMin应该是 Total。这有可能我发送NewMinas Min forward。但是，因为我依赖回溯，所以之前的子句强制失败，因此所有存储的值都丢失了。

calculate_cost(Start, [], CostList, Min, NewMin):-
  sum_list(CostList, Total),
  Total < Min,
  NewMin is Total.

calculate_cost(Start, Rest, CostList, Min, NewMin):-
  flatten(Rest, Places),
  [Next|Left] = Places,
  route(Start, Next, Cost),
  calculate_cost(Next, Left, [Cost|CostList], Min, NewMin),
  fail.

现在我想基本上保留Min变量直到程序结束，同时进行几次比较。

注意：谓词 calculate_cost 被多次调用（远远超过 100 万次），因此列表不可行，因为我已经尝试过并且会导致Out of global stack异常。

也尝试过断言选项，但它会导致同样的问题。

唯一的选择是搜索并保持最小值。

4

1 回答 1

1

当 calculate_cost 完成时保持更新 Path & MinCost：

:- dynamic current_min/2. % Path, Cost

calculate_cost(Start, [], CostList, Min, NewMin):-
  sum_list(CostList, Total),
  Total < Min,
  NewMin is Total,
  (  current_min(CPath, CMin), CMin =< NewMin
  -> true
  ;  retract(current_min(_,_)), assert(current_min(NewPath, NewMin))).

我知道 NewPath 现在不可用：看看您是否可以更改程序流程以使 NewPath 可用于 calculate_cost

顺便说一句，有可用的 Dijkstra 算法：你为什么不使用它？

于 2013-07-18T13:58:09.223 回答