1

I am trying to find the minimum cost of a path while retaining the variable Min over backtracking. The code below does not work, however it gives a slight idea over what I want.

The Min is variable which holds the current minimum value, when compared with the new Total if the Total is smaller then the NewMin should be Total. This is possible I send the NewMin as Min foreward. However, because I am relying on backtracking, the clause before forcefully fails, and hence all the values stored are lost.

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.

Now I want to essentially retain the Min variable till the programs ends, while making several comparisons.

Note: The predicate calculate_cost is called several times (a lot more than 1 million), so lists is not feasible as i've tried and I leads to Out of global stack exception.

Assert option has also been tried, but it leads to the same problem.

The only option is to search through and keep the minimum.

false
  • 10,264
  • 13
  • 101
  • 209
Namit
  • 1,314
  • 8
  • 20
  • 36

1 Answers1

1

keep updated Path & MinCost when calculate_cost complete:

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

I know NewPath isn't available now: see if you can change your program flow to make NewPath available to calculate_cost

BTW there is Dijkstra algorithm available: why don't you use it ?

Community
  • 1
  • 1
CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • Hey, I do not want to opt for the assert option as I want to optimise the program as much as possible. Assert and retract as far as i know are a slow processes when it comes to millions of calls it. – Namit Jul 18 '13 at 16:46
  • use [nb_setval/nb_getval](http://www.swi-prolog.org/pldoc/man?section=gvar) then. Just beware you need to initialize, or the first nb_getval will throw an error. – CapelliC Jul 18 '13 at 16:54
  • So, can this global variable be overwritten, lets say at one point the global variable `FinalMin` is 9, after a while a smaller value is discovered lets say 2. Can `FinalMin` be set to 2 then? – Namit Jul 18 '13 at 17:19