无论如何，是否可以确保除了广度优先搜索之外的任何东西都能满足最少数量的启发式算法？也许更多的解释会有所帮助。
我有一个随机图，很像这样：
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。
目前我使用双向搜索，但树大小的爆炸性增长很快。在我的一生中，我一直无法调整问题，以便我可以安全地为节点分配权重并让它们确保最少的状态更改数量以达到目标，而不会变成广度优先搜索。将此视为城市地图，启发式将是达到目标的最少转弯次数。
最少的转数是该搜索的结果，这一点非常重要，因为该值是更复杂问题的启发式算法的一部分。
你自己说过每组数字代表一个节点，每个节点都连接到相邻的节点。那么这是一个简单的最短路径问题，您可以使用（例如）Dijkstra 算法，每条边的权重为 1（转一圈）。
这听起来像 Dijkstra 的算法。最困难的部分在于正确设置图表（跟踪哪个节点获取哪个子节点），但是如果您可以为此投入一些 CPU 周期，那么之后就可以了。
为什么不想要广度优先搜索？
在这里.. 我很无聊 :-) 这是在 Ruby 中，但可能会让你开始。请注意，它未经测试。
class Node
attr_accessor :parents, :children, :value
def initialize args={}
@parents = args[:parents] || []
@children = args[:children] || []
@value = args[:value]
end
def add_parents *args
args.flatten.each do |node|
@parents << node
node.add_children self unless node.children.include? self
end
end
def add_children *args
args.flatten.each do |node|
@children << node
node.add_parents self unless node.parents.include? self
end
end
end
class Graph
attr_accessor :graph, :root
def initialize args={}
@graph = args[:graph]
@root = Node.new
prepare_graph
@root = @graph[0][0]
end
private
def prepare_graph
# We will iterate through the graph, and only check the values above and to the
# left of the current cell.
@graph.each_with_index do |row, i|
row.each_with_index do |cell, j|
cell = Node.new :value => cell #in-place modification!
# Check above
unless i.zero?
above = @graph[i-1][j]
if above.value == cell.value
# Here it is safe to do this: the new node has no children, no parents.
cell = above
else
cell.add_parents above
above.add_children cell # Redundant given the code for both of those
# methods, but implementations may differ.
end
end
# Check to the left!
unless j.zero?
left = @graph[i][j-1]
if left.value == cell.value
# Well, potentially it's the same as the one above the current cell,
# so we can't just set one equal to the other: have to merge them.
left.add_parents cell.parents
left.add_children cell.children
cell = left
else
cell.add_parents left
left.add_children cell
end
end
end
end
end
end
#j = 0, 1, 2, 3, 4
graph = [
[3, 4, 4, 4, 2], # i = 0
[8, 3, 1, 0, 8], # i = 1
[9, 0, 1, 2, 4], # i = 2
[9, 8, 0, 3, 3], # i = 3
[9, 9, 7, 2, 5]] # i = 4
maze = Graph.new :graph => graph
# Now, going from maze.root on, we have a weighted graph, should it matter.
# If it doesn't matter, you can just count the number of steps.
# Dijkstra's algorithm is really simple to find in the wild.
这看起来与此项目http://projecteuler.net/index.php?section=problems&id=81的问题相同
解决方案的复杂性是 O(n) n-> 节点数
你需要的是记忆。
在每个步骤中，您最多可以从 2 个方向获得。所以选择更便宜的解决方案。
有点像（只需添加在边界上取 0 的代码）
for i in row:
for j in column:
matrix[i][j]=min([matrix[i-1][j],matrix[i][j-1]])+matrix[i][j]
现在，如果您只是向左或向下移动，您就有了最便宜的解决方案
解决方案在矩阵[MAX_i][MAX_j]中
如果你也可以向左和向上，比 BigO 高得多（我可以找出最佳解决方案）
为了让 A* 始终找到最短路径，您的启发式需要始终低估实际成本（启发式是“可接受的”）。简单的启发式方法，如在网格上使用欧几里得或曼哈顿距离，效果很好，因为它们计算速度很快，并且保证小于或等于实际成本。
不幸的是，就您而言，除非您可以对节点的大小/形状做出一些简化的假设，否则我不确定您可以做些什么。例如，考虑在这种情况下从 A 到 B：
B 1 2 3 A
C 4 5 6 D
C 7 8 9 C
C e f g C
C C C C C
最短路径是 A -> D -> C -> B，但使用空间信息可能会给 3 提供比 D 更低的启发式成本。
根据您的情况，您可能能够接受实际上不是最短路径的解决方案，只要您能尽快得到答案。Christer Ericson（PS3 上的《战神 3》程序员）在此发表了一篇不错的博文： http ://realtimecollisiondetection.net/blog/?p=56
这是我对不可接受的启发式的想法：从该点开始，水平移动直到达到目标，然后垂直移动直到达到目标，并计算您所做的状态更改的次数。您也可以计算其他测试路径（例如垂直然后水平），并选择最小值作为最终启发式。如果您的节点大小大致相等且形状规则（与我的示例不同），这可能会做得很好。你做的测试路径越多，你得到的越准确，但它会越慢。
希望对您有所帮助，如果其中任何一个没有意义，请告诉我。
这种未调整的 C 实现的广度优先搜索可以在不到 1 毫秒的时间内浏览 100×100 的网格。你可能会做得更好。
int shortest_path(int *grid, int w, int h) {
int mark[w * h]; // for each square in the grid:
// 0 if not visited
// 1 if not visited and slated to be visited "now"
// 2 if already visited
int todo1[4 * w * h]; // buffers for two queues, a "now" queue
int todo2[4 * w * h]; // and a "later" queue
int *readp; // read position in the "now" queue
int *writep[2] = {todo1 + 1, 0};
int x, y, same;
todo1[0] = 0;
memset(mark, 0, sizeof(mark));
for (int d = 0; ; d++) {
readp = (d & 1) ? todo2 : todo1; // start of "now" queue
writep[1] = writep[0]; // end of "now" queue
writep[0] = (d & 1) ? todo1 : todo2; // "later" queue (empty)
// Now consume the "now" queue, filling both the "now" queue
// and the "later" queue as we go. Points in the "now" queue
// have distance d from the starting square. Points in the
// "later" queue have distance d+1.
while (readp < writep[1]) {
int p = *readp++;
if (mark[p] < 2) {
mark[p] = 2;
x = p % w;
y = p / w;
if (x > 0 && !mark[p-1]) { // go left
mark[p-1] = same = (grid[p-1] == grid[p]);
*writep[same]++ = p-1;
}
if (x + 1 < w && !mark[p+1]) { // go right
mark[p+1] = same = (grid[p+1] == grid[p]);
if (y == h - 1 && x == w - 2)
return d + !same;
*writep[same]++ = p+1;
}
if (y > 0 && !mark[p-w]) { // go up
mark[p-w] = same = (grid[p-w] == grid[p]);
*writep[same]++ = p-w;
}
if (y + 1 < h && !mark[p+w]) { // go down
mark[p+w] = same = (grid[p+w] == grid[p]);
if (y == h - 2 && x == w - 1)
return d + !same;
*writep[same]++ = p+w;
}
}
}
}
}
本文有一个稍快的 Dijsktra 算法版本，它降低了常数项。不过仍然是 O(n)，因为你真的要查看每个节点。
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8746&rep=rep1&type=pdf
编辑：以前的版本是错误的并已修复
因为一个 Djikstra 出来了。我会推荐一个简单的 DP，它的好处是可以在最佳时间运行并且不需要您构建图表。
D[a][b]是到x=a且仅使用和y=b的节点的最小距离。x<=ay<=b
而且由于您不能沿对角线移动，因此您只需要查看D[a-1][b]和D[a][b-1]计算时D[a][b]
这为您提供以下重复关系：
D[a][b] = min(if grid[a][b] == grid[a-1][b] then D[a-1][b] else D[a-1][b] + 1, if grid[a][b] == grid[a][b-1] then D[a][b-1] else D[a][b-1] + 1)
但是，在这种情况下仅执行上述操作会失败：
0 1 2 3 4
5 6 7 8 9
A b d e g
A f r t s
A z A A A
A A A f d
因此，您需要缓存到目前为止找到的每组节点的最小值。而不是看D[a][b]你看组的最小值grid[a][b]。
这是一些 Python 代码：注意grid是作为输入给出的网格，假设网格N是N
groupmin = {}
for x in xrange(0, N):
for y in xrange(0, N):
groupmin[grid[x][y]] = N+1#N+1 serves as 'infinity'
#init first row and column
groupmin[grid[0][0]] = 0
for x in xrange(1, N):
gm = groupmin[grid[x-1][0]]
temp = (gm) if grid[x][0] == grid[x-1][0] else (gm + 1)
groupmin[grid[x][0]] = min(groupmin[grid[x][0]], temp);
for y in xrange(1, N):
gm = groupmin[grid[0][y-1]]
temp = (gm) if grid[0][y] == grid[0][y-1] else (gm + 1)
groupmin[grid[0][y]] = min(groupmin[grid[0][y]], temp);
#do the rest of the blocks
for x in xrange(1, N):
for y in xrange(1, N):
gma = groupmin[grid[x-1][y]]
gmb = groupmin[grid[x][y-1]]
a = (gma) if grid[x][y] == grid[x-1][y] else (gma + 1)
b = (gmb) if grid[x][y] == grid[x][y-1] else (gma + 1)
temp = min(a, b)
groupmin[grid[x][y]] = min(groupmin[grid[x][y]], temp);
ans = groupmin[grid[N-1][N-1]]
这将在哈希函数所花费的时间（通常是时间）中运行O(N^2 * f(x))，f(x)这O(1)是您可以期望的最好的函数之一，它的常数因子比 Djikstra 的要低得多。
您应该能够轻松地在一秒钟内处理多达几千个的 N。
无论如何，是否可以确保除了广度优先搜索之外的任何东西都能满足最少数量的启发式算法？
更快的方法，还是更简单的方法？:)
您可以从两端交替进行广度优先搜索，直到两个区域在中间相遇。如果图表有很多扇出，这会快得多，比如城市地图，但最坏的情况是一样的。这真的取决于图表。
这是我使用简单 BFS 的实现。Dijkstra 也可以工作（stl::priority_queue用降低成本来代替stl::queue），但会严重过大。
这里要注意的是，我们实际上是在一个图上搜索，其节点与给定数组中的单元格不完全对应。为了获得该图，我使用了一个简单的基于 DFS 的填充（您也可以使用 BFS，但 DFS 对我来说稍微短一些）。这样做是找到所有连接的和相同的字符组件，并将它们分配给相同的颜色/节点。因此，在填充之后，我们可以通过查看 colour[row][col] 的值来找出每个单元格在底层图中属于哪个节点。然后我只是遍历单元格并找出相邻单元格不具有相同颜色的所有单元格（即位于不同节点中）。因此，这些是我们图表的边缘。我维护一个stl::set当我遍历单元格以消除重复的边缘时，边缘的数量。之后，从边列表构建一个邻接列表就很简单了，我们就可以开始使用 bfs 了。
代码（在 C++ 中）：
#include <queue>
#include <vector>
#include <iostream>
#include <string>
#include <set>
#include <cstring>
using namespace std;
#define SIZE 1001
vector<string> board;
int colour[SIZE][SIZE];
int dr[]={0,1,0,-1};
int dc[]={1,0,-1,0};
int min(int x,int y){ return (x<y)?x:y;}
int max(int x,int y){ return (x>y)?x:y;}
void dfs(int r, int c, int col, vector<string> &b){
if (colour[r][c]<0){
colour[r][c]=col;
for(int i=0;i<4;i++){
int nr=r+dr[i],nc=c+dc[i];
if (nr>=0 && nr<b.size() && nc>=0 && nc<b[0].size() && b[nr][nc]==b[r][c])
dfs(nr,nc,col,b);
}
}
}
int flood_fill(vector<string> &b){
memset(colour,-1,sizeof(colour));
int current_node=0;
for(int i=0;i<b.size();i++){
for(int j=0;j<b[0].size();j++){
if (colour[i][j]<0){
dfs(i,j,current_node,b);
current_node++;
}
}
}
return current_node;
}
vector<vector<int> > build_graph(vector<string> &b){
int total_nodes=flood_fill(b);
set<pair<int,int> > edge_list;
for(int r=0;r<b.size();r++){
for(int c=0;c<b[0].size();c++){
for(int i=0;i<4;i++){
int nr=r+dr[i],nc=c+dc[i];
if (nr>=0 && nr<b.size() && nc>=0 && nc<b[0].size() && colour[nr][nc]!=colour[r][c]){
int u=colour[r][c], v=colour[nr][nc];
if (u!=v) edge_list.insert(make_pair(min(u,v),max(u,v)));
}
}
}
}
vector<vector<int> > graph(total_nodes);
for(set<pair<int,int> >::iterator edge=edge_list.begin();edge!=edge_list.end();edge++){
int u=edge->first,v=edge->second;
graph[u].push_back(v);
graph[v].push_back(u);
}
return graph;
}
int bfs(vector<vector<int> > &G, int start, int end){
vector<int> cost(G.size(),-1);
queue<int> Q;
Q.push(start);
cost[start]=0;
while (!Q.empty()){
int node=Q.front();Q.pop();
vector<int> &adj=G[node];
for(int i=0;i<adj.size();i++){
if (cost[adj[i]]==-1){
cost[adj[i]]=cost[node]+1;
Q.push(adj[i]);
}
}
}
return cost[end];
}
int main(){
string line;
int rows,cols;
cin>>rows>>cols;
for(int r=0;r<rows;r++){
line="";
char ch;
for(int c=0;c<cols;c++){
cin>>ch;
line+=ch;
}
board.push_back(line);
}
vector<vector<int> > actual_graph=build_graph(board);
cout<<bfs(actual_graph,colour[0][0],colour[rows-1][cols-1])<<"\n";
}
这只是一个快速破解，可以进行很多改进。但我认为它在运行时复杂性方面非常接近最优，并且对于几千块大小的板应该运行得足够快（不要忘记更改#defineof SIZE）。另外，我只用您提供的一个案例对其进行了测试。所以，正如 Knuth 所说，“当心上述代码中的错误；我只是证明它是正确的，没有尝试过。” :)。