有没有任何方法可以保证除了广度优先搜索之外，最小转弯启发式被满足？也许需要更多的解释。
我有一个随机图，就像这样：
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
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]
现在，如果您只向左或向下移动，则具有最便宜的解决方案
解决方案在matrix[MAX_i][MAX_j]中
如果您也可以向左上方移动，则BigO要高得多（我可以找出最优解）
这个未经调优的 C 语言实现的广度优先搜索算法可以在不到 1 毫秒的时间内遍历完一个 100x100 的网格。你可能可以做得更好。
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;
}
}
}
}
}
编辑：之前的版本有误已经修正
既然Djikstra不行，我推荐使用一个简单的DP算法，它具有在最优时间内运行的好处，并且不需要您构建一个图形。
D [a] [b]是仅使用x≤a和y≤b的节点到x=a和y=b的最小距离。
由于您不能对角线移动，因此在计算D [a] [b]时只需查看D [a-1] [b]和D [a] [b-1]。
这给出以下递归关系：
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 x 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。
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
这是我对非可达启发式的想法：从这个点出发，水平移动直到与目标对齐，然后垂直移动直到到达目标，并计算您所做的状态更改次数。您还可以计算其他测试路径（例如先垂直再水平），并将最小值选作最终启发式。如果您的节点大小大致相等且形状规则（与我的示例不同），则效果可能不错。您做的测试路径越多，准确性就越高，但速度就越慢。
希望这有帮助，如果有任何不理解的地方，请告诉我。
本文介绍了 Dijsktra 算法的稍微更快的版本，可以降低常数项。但由于您确实需要查看每个节点，因此仍然是 O(n)。
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8746&rep=rep1&type=pdf
这是我使用简单的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";
}
这只是一个快速的hack，还有很多改进可以做。但我认为它在运行时复杂度方面已经非常接近最优，并且应该足够快地运行数千个板子（不要忘记更改SIZE的#define）。此外，我只测试了您提供的一个案例。所以，正如Knuth所说，“小心上述代码中的错误；我只证明了它的正确性，而没有尝试过。” :).