使用list.map和/或list.length筛选列表列表

Question

我有一个包含列表的列表，如下所示：

[[(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)]]

该列表显示了机器人从源到目标的最短路径。在这种情况下，我们的源网格点是(3，3(，目标网格点为(1，1(。

我现在添加了代码，这样机器人就可以对角移动(而不仅仅是垂直/水平移动(。到目前为止，代码的条件是只采取使其更接近目标的步骤。然而，在将对角线维度添加到代码中之后，我得到了STACKOVERFLOW。

因此，我只想要一个将机器人带到目标的列表(机器人移动(。

我认为List.map和List.length在这里可能会有所帮助；仅返回最小长度"；以便获得到达目标的最短路线。

到目前为止我的代码(参见代码底部的stackoverflow问题(：

type pos = int*int
let p1 = (1, 1) // source grid point
let p2 = (3, 3) // target grid point
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) // stackoverflow

Answer 1

candidates2函数中存在一个问题。在筛选可能的解决方案时，可以查找与当前位置更接近或相等的位置(使用dist x tg <= dist src tg(。这意味着你可以创建你的机器人在两个位置之间来回跳跃的路线：

(1, 2) -> (2, 1) -> (1, 2) -> (2, 1) -> ...

您可以通过将条件更改为仅小于<来解决此问题。在调试代码时，我还做了一些更改，使其可读性更强：

let candidates2 ((x, y): pos) (tg: pos) : pos list =
[1,0; -1,0; 0,1; 0,-1; 1,1; 1,-1; -1,1; -1,-1]
|> List.map (fun (dx, dy) -> (x+dx, y+dy))
|> List.filter (fun pos -> dist pos tg <= dist (x, y) tg)
let rec routes2 (src: pos) (tg: pos) : pos list list =  
if src = tg then [[tg]] 
else  
candidates2 src tg
|> List.map (fun j -> List.map (fun i -> src :: i) (routes2 j tg))
|> List.concat