Пазл Переполнение стека в рекурсивном решении OCaml для кратчайшего пути коня на шахматной доске

Question

Вопрос, как описано здесь: Шахматный вопрос по кратчайшему пути рыцаря .Я попытался решить ее, используя интуитивно-рекурсивный метод, следующим образом:

let is_in_list x s = List.exists (fun y -> if y = x  then true else false) s;; (* find out if an element belongs to a list *)

let next_step n = [n+10;n-6;n+6;n-10;n+17;n-17;n+15;n-15];;

let rec legal_next_step = function
  |[]->[]
  |x::s-> 
    if x<0 or x>63 then legal_next_step s
    else x::legal_next_step s;;

let find_next_step n = legal_next_step (next_step n);; (* here is to find all the valid next moves and put them into a list*)

let rec min s = 
  let rec loop result = function
    |[]->result;
    |x::s-> 
      if x < result then loop x s
      else loop result s in
  loop (List.hd s) s;;

let rec find_shortest_path n m =
  if is_in_list m (next_step n) then 1
  else
    1 + min (List.map (fun x -> find_shortest_path x m) (find_next_step n)) ;;

Это вызывает проблему «переполнения стека».Это почему?Моя программа создает слишком много слоев рекурсивного вызова в стеке?Или что-то не так с моим кодом.

Answer 1

Вы должны понимать, что когда вы пишете

List.map (fun x -> find_shortest_path x m) (find_next_step n))

Вы будете буквально вычислять все «кратчайшие пути отсюда» из всех возможных соседей, а затем вычислять минимум всех этих результатов.

Таким образом, в вашем коде есть бесконечный цикл: если вы начинаете с позиции A и пытаетесь вычислить кратчайший путь от одного из его соседей B, то find_shortest_path, вызванный из B, неизбежно попытается Посмотрите, как долго будет длиться путь, если его первым ходом будет возврат к A. Таким образом, среди всех других возможных ходов, которые также будут опробованы, вы вычислите «длину» цикла A-B-A-B-A-B..., то есть бесконечный цикл.

Есть несколько способов избежать этой проблемы (которая не связана с программированием OCaml как таковым, это ошибка в логике вашей программы, которая будет проявляться на любом языке):

• используйте поиск в ширину вместо поиска в глубину, чтобы вы постепенно исследовали все пути заданной длины, останавливаясь на наименьшем выигрышном пути, который вы найдете; если вы хотите, это соответствует параллельному исследованию всех путей, поэтому не проблема иметь бесконечные пути до тех пор, пока вы останавливаетесь (потому что вы нашли другое решение) перед попыткой поиска по всему бесконечному пути

• отметьте места, которые вы уже посетили, чтобы не «возвращаться» (это никогда не будет кратчайшим способом добраться до места назначения)

  • если вы используете поиск в глубину, это деликатно, потому что эти метки должны быть локальными для поиска (вы не можете просто изменить матрицу логических значений); Например, вы можете добавить параметр int list к вашим find_shortest_path функциям, который будет списком мест, которые являются частью текущего исследуемого пути; прежде чем пытаться вычислить кратчайший путь из возможных соседей, убедитесь, что его нет в этом списке. Для чего-то более эффективного вы можете использовать набор (module IntSet = Set.Make(struct type t = int let compare = Pervasives.compare)) (логарифмический, а не линейный, тест членства) или использовать изменяющуюся логическую матрицу, в которой вы осторожны, чтобы отслеживать изменения состояния при выборе другого пути.

  • если вы используете поиск в ширину, вы можете использовать глобальную логическую матрицу «мест, которые вы уже посетили», потому что вы одновременно исследуете все пути до заданной длины; поэтому, если вы встречаете место, которое уже помечено как посещенное, вы знаете, что другой путь посещал его раньше, так что оно уже впереди вас, и нет смысла пытаться получить от него кратчайший путь.

Итак, краткий ответ: вы должны узнать о поиске в ширину.

Answer 2

Ну, следующий законный ход мне кажется неправильным.Если я в правом нижнем углу (скажем, в квадрате 7), я не могу перейти к квадрату 1. Однако это не должно вызывать зацикливание, просто должно быть получен неправильный ответ.

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