问题如下所述：Knight'；s最短路径国际象棋问题。我尝试使用直观的递归方法来解决它，如下所示：
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)) ;;
这会导致"堆栈溢出"问题。为什么？我的程序是否在堆栈中创建了太多递归调用层？或者我的代码出现了严重错误。
您必须明白，当您编写时
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编程本身无关，这是程序逻辑中的一个错误，在任何语言中都会表现出来）：
使用广度优先搜索而不是深度优先搜索，这样你就可以逐步探索给定长度的所有路径，停在你找到的最小获胜路径上；如果你愿意，这对应于并行探索所有路径，所以只要你在尝试搜索整个无限路径之前停下来（因为你找到了另一个解决方案），拥有无限路径就不是问题
标记你已经去过的地方，以免"回去"（这永远不会是到达目的地的最短途径）
如果你使用深度优先搜索，这是很微妙的，因为这些标记必须是搜索的本地标记（你不能简单地改变布尔矩阵）；例如，您可以将
int list参数添加到find_shortest_path函数中，这将是当前探索路径的一部分的位置列表；在尝试从可能的邻居计算最短路径之前，请检查它是否不在此列表中。为了更高效，您可以使用集合（module IntSet = Set.Make(struct type t = int let compare = Pervasives.compare)）（对数，而不是线性，隶属度测试），或者使用可变布尔矩阵，在选择不同路径时，您可以小心地回溯状态更改。如果你使用广度优先搜索，你可以使用"你已经去过的地方"的全局布尔矩阵，因为你可以同时探索给定长度的所有路径；因此，如果你遇到一个已经标记为已访问的地方，你知道另一条路径在更早的时候访问过它，所以它已经在你前面了，从那里寻找最短的路径是没有意义的。
所以简单的答案是：你应该学习广度优先搜索。
好吧，下一个合法的移动计算对我来说是错误的。如果我在右下角（比如正方形7），我就不能移动到正方形1。这不应该导致循环，但是，它应该得到错误的答案。
我的猜测是，你只是在走一些非常漫长、失败的道路。我认为你需要做广度优先的搜索，而不是深度优先。本质上，你保留了一组可到达的正方形，每一步将每个当前可到达的点推进一步。您的代码总是试图从每个新位置到达目的地，因此（可能）遵循许多长路径。