堆栈溢出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调用from B将不可避免地试图看看如果他的第一步是要回去的路径将会有多长到A.因此,在所有其他可能尝试的移动中,您将计算循环的"长度" A-B-A-B-A-B...,即无限循环.

有几种方法可以避免这个问题(这与OCaml编程本身无关,它是程序逻辑中的错误,可以在任何语言中显示):

• 使用广度优先搜索而不是深度优先搜索,以便您逐步探索给定长度的所有路径,停在您找到的最小获胜路径上; 如果你愿意,这对应于并行探索所有路径,所以只要你在尝试搜索整个无限路径之前停止(因为你找到了另一个解决方案),就不会有无限路径的问题

• 标记您已经访问过的地方,以免"返回"(这绝不是到达目的地的最短路径)

  • 如果你使用深度优先搜索,这很微妙,因为这些标记必须是搜索的本地标记(你不能简单地改变布尔矩阵); 例如,您可以int list向find_shortest_path函数添加一个参数,该参数将是当前探索路径的一部分列表; 在尝试计算可能的邻居的最短路径之前,请检查它是否在此列表中.对于更高效的东西,您可以使用set(module IntSet = Set.Make(struct type t = int let compare = Pervasives.compare))(对数,而不是线性,成员资格测试),或使用可变布尔矩阵,在选择不同路径时,您需要小心回溯状态更改.

  • 如果你使用广度优先搜索,你可以使用"你已经访问过的地方"的全局布尔矩阵,因为你同时探索到达给定长度的所有路径; 因此,如果你遇到一个已被标记为已访问过的地方,你知道另一条路径在较早的时间内访问过它,所以它已经超前于你,并且没有必要尝试从那里获得最短的路径.

所以简短的回答是:你应该学习广度优先搜索.