添加对角线移动后F#代码栈溢出，求筛选机器人最短路径方案

原最短路径列表 #

以下是机器人从起点(3, 3)到终点(1, 1)，仅支持上下左右移动时的所有最短路径：

[[(3, 3); (2, 3); (1, 3); (1, 2); (1, 1)];
[(3, 3); (2, 3); (2, 2); (1, 2); (1, 1)];
[(3, 3); (2, 3); (2, 2); (2, 1); (1, 1)];
[(3, 3); (3, 2); (2, 2); (1, 2); (1, 1)];
[(3, 3); (3, 2); (2, 2); (2, 1); (1, 1)];
[(3, 3); (3, 2); (3, 1); (2, 1); (1, 1)]]

问题背景 #

为机器人添加对角线移动功能后，虽已通过距离判断限制仅向靠近终点的方向移动，但运行routes2函数时出现STACKOVERFLOW问题。现需借助List.map和List.length，筛选出仅能到达终点的最短路径列表。

相关代码 #

type pos = int*int

let p1 = (1, 1) // 起点网格点
let p2 = (3, 3) // 终点网格点

let dist (p1: pos) (p2: pos) : int =
 (((pown ((fst p2)-(fst p1)) 2) + (pown ((snd p2)-(snd p1)) 2)))

dist p1 p2
// printfn "%A" (dist p1 p2)

///////////////////////////////////////////////////////////////////////
let src = p1
let tg = p2
let candidates (src: pos) (tg: pos) : pos list =
 let candi = [((fst src)+1), (snd src); ((fst src)-1), (snd src); (fst src), ((snd src)+1); (fst src), ((snd src)-1)]
 let candilist = candi |> List.filter (fun x -> dist x tg <= dist src tg)
 candilist
//printfn "%A" (candidates src tg)

///////////////////////////////////////////////////////////////////////

let source = (3, 3)
let target = (1, 1)
let rec routes (src: pos) (tg: pos) : pos list list =
 match src with
  p when p = tg -> [[tg]]
  |_ -> List.concat (List.map (fun j -> List.map (fun i -> src :: i) (routes j tg))(candidates src tg))

// printfn "%A" (routes source target)

///////////////////////////////////////////////////////////////////////

let candidates2 (src: pos) (tg: pos) : pos list =
 let candi = [((fst src)+1), (snd src); ((fst src)-1), (snd src); (fst src), ((snd src)+1); (fst src), ((snd src)-1); ((fst src)+1), ((snd src)+1); ((fst src)+1), ((snd src)-1); ((fst src)-1), ((snd src)+1); ((fst src)-1), ((snd src)-1)]
 let candilist = candi |> List.filter (fun x -> dist x tg <= dist src tg)
 candilist

// printfn "%A" (candidates2 src tg)

let rec routes2 (src: pos) (tg: pos) : pos list list =
 match src with
  p when p = tg -> [[tg]]
  |_ -> List.concat (List.map (fun j -> List.map (fun i -> src :: i) (routes2 j tg))(candidates2 src tg))

printfn "%A" (routes2 source target) // 此处出现栈溢出

内容的提问来源于stack exchange，提问作者Hoodwinked