Наименьшее число эвристических поворотов

Это похоже на алгоритм Дейкстры. Самая трудная часть будет заключаться в правильной настройке графика (отслеживании того, какой узел получает какие дочерние элементы), но если вы можете посвятить этому несколько циклов процессора, вы будете в порядке после этого.

Почему бы вам не начать поиск вширь?

Здесь.. Мне было скучно : -) это в 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.

Это похоже на ту же проблему, что и этот projecteuler 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.

В зависимости от ваших обстоятельств, вы можете жить с решением, которое на самом деле не является кратчайшим путем, если вы можете получить ответ раньше. Здесь есть хороший блог Кристера Эриксона (Programmer for God of War 3 на PS3) на эту тему: http://realtimecollisiondetection.net/blog/?p=56

Вот моя идея для неразрешимой эвристики: от точки двигайтесь горизонтально, пока не достигнете цели, затем двигайтесь вертикально, пока не достигнете ее, и подсчитайте количество изменений состояния, которые вы сделали. Вы можете вычислить и другие пути тестирования (например, по вертикали, а затем по горизонтали) и выбрать минимальное значение в качестве конечной эвристики. Если ваши узлы примерно одинакового размера и правильной формы (в отличие от моего примера), это может сделать достаточно хороший. Чем больше тестовых путей вы сделаете, тем точнее вы получите, но тем медленнее это будет. Надеюсь, это поможет, дайте мне знать, если что-то из этого не имеет смысла.

Эта не настроенная C-реализация поиска по ширине может прожевать сетку размером 100 на 100 менее чем за 1 мс. Вы, вероятно, можете сделать лучше.

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;
                }
            }
        }
    }
}

В этой статье есть немного более быстрая версия алгоритма Дийсктры, которая уменьшает постоянный член. Тем не менее, все еще 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<=a и y<=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) время, и это одна из лучших функций, на которые вы можете надеяться, и она имеет гораздо более низкий постоянный коэффициент, чем у Джикстры.

Вы должны легко справляться с N до нескольких тысяч в секунду.

Можно ли вообще гарантировать, что наименьшее число эвристических поворотов удовлетворяется чем-либо, кроме поиска по ширине?

Более быстрый способили более простой способ? :)

Вы можете искать вширь с обоих концов, чередуя, пока две области не встретятся в середине. Это будет намного быстрее, если график имеет много разветвлений, как на карте города, но в худшем случае то же самое. Это действительно зависит от графика.

Это моя реализация с использованием простого BFS. Дейкстра также будет работать (замените stl::priority_queue, который сортирует по убыванию затрат на stl::queue), но серьезно будет перебором.

Здесь следует отметить, что на самом деле мы ищем на графе, узлы которого не совсем соответствуют ячейкам в данном массиве. Чтобы добраться до этого графика, я использовал простую заливку на основе DFS (вы также можете использовать BFS, но DFS немного короче для меня). Что это делает, так это найти все связанное и те же компоненты символов и назначить их тому же цвету / узлу. Таким образом, после заполнения мы можем узнать, к какому узлу принадлежит каждая ячейка в базовом графе, посмотрев на значение цвета[строка][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";
}

Это просто быстрый Хак, можно сделать много улучшений. Но я думаю, что он довольно близок к оптимальному с точки зрения сложности выполнения, и должен работать достаточно быстро для плат размером в несколько тысяч (не забудьте изменить #define из SIZE). Кроме того, я проверил его только в одном случае, который вы предоставили. Итак, как сказал кнут, " остерегайтесь ошибок в вышеприведенном код; я только доказал его правильность, а не попробовал его.":).