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)) ;;

这会导致“堆栈溢出”问题。为什么呢？是因为我的程序在堆栈中创建了太多层递归调用吗？还是我的代码出了严重的问题。

- lkahtz

Answer 1

你必须明白，当你编写代码时

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

你需要计算所有可能邻居的“最短路径”，然后计算所有结果的最小值。

因此，你的代码中存在一个无限循环：如果你从位置A开始，并尝试计算其中一个邻居B的最短路径，那么从B调用的find_shortest_path将不可避免地尝试查看如果他的第一步是返回A，路径会有多长。因此，在尝试的所有其他可能移动中，你将计算循环“A-B-A-B-A-B...”的“长度”，即无限循环。

有几种方法可以避免这个问题（这与OCaml编程本身无关，它是程序逻辑错误，在任何语言中都会显现出来）。

• 使用广度优先搜索而不是深度优先搜索，这样你就可以逐步探索所有给定长度的路径，停在找到最小的获胜路径时；如果你想，这相当于并行地探索所有路径，因此只要在尝试搜索整个无限路径之前停止（因为你已经找到另一条解决方案），就不会有问题存在无限路径。

• 标记你已经访问过的地方，以免“回头”（这永远不会是到达目的地的最短方式）

  • 如果你使用深度优先搜索，这很棘手，因为这些标记必须局限于搜索的范围内（你不能简单地改变一个布尔矩阵）;例如，你可以向你的find_shortest_path函数添加一个int list参数，该参数将是当前探索路径的一部分的位置列表；在尝试计算可能的邻居的最短路径之前，请检查它是否在此列表中。对于更高效的方法，你可以使用一个集合（module IntSet = Set.Make(struct type t = int let compare = Pervasives.compare)）（对数而不是线性成员测试），或者使用可变布尔矩阵，在选择不同路径时小心回溯状态更改。

  • 如果你使用广度优先搜索，你可以使用全局布尔矩阵“你已经访问过的地方”，因为你同时探索所有路径直到给定长度；所以如果你遇到一个被标记为已访问的地方，你知道另一条路径在早期时间已经访问了它，所以它已经超过了你，没有必要从那里尝试获得最短路径。

所以简短的答案是：你应该学习广度优先搜索。

- gasche

Answer 2

嗯，下一个合法的移动计算看起来有些问题。比如说，如果我在右下角（比如方格7），我就不能移动到方格1。这不应该导致死循环，但是答案会是错误的。

我猜测你只是在跟随一些非常长而失败的路径。我认为你需要进行广度优先搜索，而不是深度优先搜索。简单来说，你需要保持一组可达的方格，并在每一步中将当前可达的位置向前推进一个移动。你的代码总是试图从每个新位置到达目标，因此（可能）会遵循许多长路径。

- Jeffrey Scofield