去除不良坐标 - 最短路径算法

Question

我有一个问题。如果我有两列 X、Y。它们的坐标为 x = 3、y = 8。

有时会有多个坐标值相同，例如

X = 4, Y = 7
X = 5, Y = 8 <- Remove this 
X = 6, Y = 9 <- Remove this 
X = 4, Y = 7 <- Dead end. Remove this
X = 3, Y = 2
X = 2, Y = 2
X = 1, Y = 2

如何删除导致截止日期结束的不良坐标？它们的 X 和 Y 列表是 C int 数组。

我已经制作了A*算法，现在我需要确保路径是最优的。

首先。我首先需要知道我需要删除哪些坐标。也有方法吗？

一个想法是删除两个相同坐标之间的所有内容。这是明智的策略吗？

编辑：

其中一些坐标没有用。其中一些是重复的。

x = 8, y = 13 <- Starting
x = 8, y = 12
x = 8, y = 11
x = 8, y = 10
x = 8, y = 11
x = 7, y = 11
x = 6, y = 11
x = 6, y = 10
x = 5, y = 10
x = 5, y = 11
x = 5, y = 12
x = 6, y = 12
x = 7, y = 12
x = 7, y = 11
x = 6, y = 11
x = 6, y = 10
x = 5, y = 10
x = 5, y = 11
x = 5, y = 12
x = 5, y = 13
x = 4, y = 13
x = 3, y = 13
x = 3, y = 12
x = 3, y = 11
x = 3, y = 10
x = 2, y = 10
x = 1, y = 10
x = 1, y = 9
x = 1, y = 8
x = 1, y = 7
x = 2, y = 7
x = 2, y = 6
x = 2, y = 5
x = 2, y = 4
x = 3, y = 4
x = 4, y = 4
x = 5, y = 4
x = 5, y = 5
x = 4, y = 5
x = 4, y = 4
x = 5, y = 4
x = 5, y = 5
x = 5, y = 6
x = 4, y = 6
x = 4, y = 5
x = 4, y = 4
x = 3, y = 4
x = 3, y = 3
x = 3, y = 2
x = 4, y = 2
x = 5, y = 2
x = 6, y = 2
x = 6, y = 1 <- Goal

我现在的一个想法是，如果我删除一个坐标，然后循环遍历其余坐标。然后我可以确定路径是否完整。但这需要很长时间。

Answer 1

我解决了这个问题。

看看 CControl 库。 https://github.com/DanielMartensson/CControl

工作示例在这里https://github.com/DanielMartensson/CControl/blob/master/src/CControl/Documents/Examples/Algorithms/A-Star/Astar.txt

去除不良坐标 - 最短路径算法

Remove bad coordinates - Shortest path algorithm

c

sorting

a-star