Fewest number of turns heuristic

Question

Is there anyway to ensure the that the fewest number of turns heuristic is met by anything except a breadth first search? Perhaps some more explanation would help.

I have a random graph, much like this:

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

Starting in the top left corner, I need to know the fewest number of steps it would take to get to the bottom right corner. Each set of connected colors is assumed to be a single node, so for instance in this random graph, the three 1's on the top row are all considered a single node, and every adjacent (not diagonal) connected node is a possible next state. So from the start, possible next states are the 1's in the top row or 3 in the second row.

Currently I use a bidirectional search, but the explosiveness of the tree size ramps up pretty quickly. For the life of me, I haven't been able to adjust the problem so that I can safely assign weights to the nodes and have them ensure the fewest number of state changes to reach the goal without it turning into a breadth first search. Thinking of this as a city map, the heuristic would be the fewest number of turns to reach the goal.

It is very important that the fewest number of turns is the result of this search as that value is part of the heuristic for a more complex problem.

Answer 1

This looks like same problem as this projeceuler http://projecteuler.net/index.php?section=problems&id=81

Comlexity of solution is O(n) n-> number of nodes

What you need is memoization.

At each step you can get from max 2 directions. So pick the solution that is cheaper.

It is something like (just add the code that takes 0 if on boarder)

for i in row:
    for j in column:
         matrix[i][j]=min([matrix[i-1][j],matrix[i][j-1]])+matrix[i][j]

And now you have lest expensive solution if you move just left or down

Solution is in matrix[MAX_i][MAX_j]

If you can go left and up too, than the BigO is much higher (I can figure out optimal solution)

Answer 2

This sounds like Dijkstra's algorithm. The hardest part would lay in properly setting up the graph (keeping track of which node gets which children), but if you can devote some CPU cycles to that, you'd be fine afterwards.

Why don't you want a breadth-first search?

Here.. I was bored :-) This is in Ruby but may get you started. Mind you, it is not tested.

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.

Answer 3

You said yourself each group of numbers represents one node, and each node is connected to adjascent nodes. Then this is a simple shortest-path problem, and you could use (for instance) Dijkstra's algorithm, with each edge having weight 1 (for 1 turn).

Answer 4

Is there anyway to ensure the that the fewest number of turns heuristic is met by anything except a breadth first search?

A faster way, or a simpler way? :)

You can breadth-first search from both ends, alternating, until the two regions meet in the middle. This will be much faster if the graph has a lot of fanout, like a city map, but the worst case is the same. It really depends on the graph.

Answer 5

In order for A* to always find the shortest path, your heuristic needs to always under-estimate the actual cost (the heuristic is "admissable"). Simple heuristics like using the Euclidean or Manhattan distance on a grid work well because they're fast to compute and are guaranteed to be less than or equal to the actual cost.

Unfortunately, in your case, unless you can make some simplifying assumptions about the size/shape of the nodes, I'm not sure there's much you can do. For example, consider going from A to B in this case:

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

The shortest path would be A -> D -> C -> B, but using spatial information would probably give 3 a lower heuristic cost than D.

Depending on your circumstances, you might be able to live with a solution that isn't actually the shortest path, as long as you can get the answer sooner. There's a nice blogpost here by Christer Ericson (progammer for God of War 3 on PS3) on the topic: http://realtimecollisiondetection.net/blog/?p=56

Here's my idea for an nonadmissable heuristic: from the point, move horizontally until you're even with the goal, then move vertically until you reach it, and count the number of state changes that you made. You can compute other test paths (e.g. vertically then horizontally) too, and pick the minimum value as your final heuristic. If your nodes are roughly equal size and regularly shaped (unlike my example), this might do pretty well. The more test paths you do, the more accurate you'd get, but the slower it would be.

Hope that's helpful, let me know if any of it doesn't make sense.

Answer 6

This is my implementation using a simple BFS. A Dijkstra would also work (substitute a stl::priority_queue that sorts by descending costs for the stl::queue) but would seriously be overkill.

The thing to notice here is that we are actually searching on a graph whose nodes do not exactly correspond to the cells in the given array. To get to that graph, I used a simple DFS-based floodfill (you could also use BFS, but DFS is slightly shorter for me). What that does is to find all connected and same character components and assign them to the same colour/node. Thus, after the floodfill we can find out what node each cell belongs to in the underlying graph by looking at the value of colour[row][col]. Then I just iterate over the cells and find out all the cells where adjacent cells do not have the same colour (i.e. are in different nodes). These therefore are the edges of our graph. I maintain a stl::set of edges as I iterate over the cells to eliminate duplicate edges. After that it is a simple matter of building an adjacency list from the list of edges and we are ready for a bfs.

Code (in 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";
}

This is just a quick hack, lots of improvements can be made. But I think it is pretty close to optimal in terms of runtime complexity, and should run fast enough for boards of size of several thousand (don't forget to change the #define of SIZE). Also, I only tested it with the one case you have provided. So, as Knuth said, "Beware of bugs in the above code; I have only proved it correct, not tried it." :).

Answer 7

This untuned C implementation of breadth-first search can chew through a 100-by-100 grid in less than 1 msec. You can probably do better.

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

Answer 8

This paper has a slightly faster version of Dijsktra's algorithm, which lowers the constant term. Still O(n) though, since you are really going to have to look at every node.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8746&rep=rep1&type=pdf

Answer 9

EDIT: THE PREVIOUS VERSION WAS WRONG AND WAS FIXED

Since a Djikstra is out. I'll recommend a simple DP, which has the benefit of running in the optimal time and not having you construct a graph.

D[a][b] is the minimal distance to x=a and y=b using only nodes where the x<=a and y<=b.

And since you can't move diagonally you only have to look at D[a-1][b] and D[a][b-1] when calculating D[a][b]

This gives you the following recurrence relationship:

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)

However doing only the above fails on this case:

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

Therefore you need to cache the minimum of each group of node you found so far. And instead of looking at D[a][b] you look at the minimum of the group at grid[a][b].

Here's some Python code: Note grid is the grid that you're given as input and it's assumed the grid is N by 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]]

This will run in O(N^2 * f(x)) where f(x) is the time the hash function takes which is normally O(1) time and this is one of the best functions you can hope for and it has a lot lower constant factor than Djikstra's.

You should easily be able to handle N's of up to a few thousand in a second.