Сохранить переменную при возврате пролога

Я пытаюсь найти минимальную стоимость пути, сохраняя переменную Min при отслеживании с возвратом. Приведенный ниже код не работает, однако он дает некоторое представление о том, что я хочу.

Min - это переменная, которая содержит текущее минимальное значение по сравнению с новым Total, если Total меньше, то NewMin должно быть Total. Возможно, я отправлю NewMin как Min вперед. Однако, поскольку я полагаюсь на отслеживание с возвратом, предложение before принудительно не выполняется, и, следовательно, все сохраненные значения теряются.

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 вызывается несколько раз (намного больше 1 миллиона), поэтому списки неосуществимы, как я пытался, и это приводит к Out of global stack исключению.

Опция Assert также была опробована, но она приводит к той же проблеме.

Единственный вариант - поиск по минимуму.


backtracking prolog
person Namit    schedule 18.07.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

обновлять Path и MinCost после завершения calculate_cost:

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

Кстати, существует алгоритм Дейкстры: почему ты не используешь это?

person CapelliC    schedule 18.07.2013
comment
Эй, я не хочу выбирать опцию assert, так как хочу максимально оптимизировать программу. Насколько я знаю, утверждение и отзыв - медленные процессы, когда дело касается миллионов вызовов. - person Namit; 18.07.2013
comment
затем используйте nb_setval / nb_getval. Просто будьте осторожны, вам нужно инициализировать, иначе первый nb_getval выдаст ошибку. - person CapelliC; 18.07.2013
comment
Итак, можно ли перезаписать эту глобальную переменную, допустим, в какой-то момент глобальная переменная FinalMin равна 9, через некоторое время обнаруживается меньшее значение, допустим, 2. Можно ли тогда FinalMin установить на 2? - person Namit; 18.07.2013