algorithm - 最少轮数启发式

Question

除了广度优先搜索之外，是否有任何方法可以确保启发式算法的轮数最少？也许更多的解释会有所帮助。

我有一个随机图，很像这样:

0 1 1 1 2
3 4 5 6 7
9 a 5 b c
9 d e f f
9 9 g h i

从左上角开始，我需要知道到达右下角所需的最少步数。每组连接的颜色都被假定为单个节点，因此例如在此随机图中，顶行的三个 1 都被视为单个节点，并且每个相邻(非对角线)连接的节点都是可能的下一个状态。所以从一开始，可能的下一个状态是第一行中的 1 或第二行中的 3。

目前我使用双向搜索，但树大小的爆炸性增长非常快。在我的一生中，我一直无法调整问题，以便我可以安全地为节点分配权重，并让它们确保状态更改次数最少以达到目标，而不会变成广度优先搜索。将其视为城市 map ，启发式算法将是达到目标的最少转弯次数。

非常重要的是，最少的轮数是此搜索的结果，因为该值是更复杂问题的试探法的一部分。

Answer 1

你自己说每组数字代表一个节点，每个节点都连接到相邻的节点。那么这是一个简单的shortest-path问题，你可以使用(例如)Dijkstra's algorithm ，每条边的权重为 1(1 圈)。