Efficiency of Breadth First Search

Question

What would be the most efficient way to compute the fewest hops it takes to get from x1, y1 to x2, y2 on an unbounded/infinite chess board? Assume that from x1, y1 we can always generate a set of legal moves.

This sounds tailor made for BFS and I have implemented one successfully. But its space and time complexity seem atrocious if x2, y2 is arbitrarily large.

I have been looking at various other algorithms like A*, Bidirectional search, iterative deepening DFS etc but so far I am clueless as to which approach would yield the most optimal (and complete) solution. Is there some insight I am missing?

Answer 1

To expand on the discussion in comments, an uninformed search like breadth-first search (BFS) will find the optimal solution (the shortest path). However it only considers the cost-so-far g(n) for a node n and its cost increases exponentially with distance from source to target. To tame the cost of the search whilst still ensuring that the search finds the optimal solution, you need to add some information to the search algorithm via a heuristic, h(n).

Your case is a good fit for A* search, where the heuristic is a measure of distance from a node to the target (x2, y2). You could use the Euclidian distance "as the crow flies", but as you're considering a Knight then Manhattan distance might be more appropriate. Whatever measure you choose it has to be less (or equal to) the actual distance from the node to the target for the search to find the optimal solution (in this case the heuristic is known as "admissible"). Note that you need to divide each distance by a constant in order to get it to underestimate moves: divide by 3 for the Manhattan distance, and by sqrt(5) for the Euclidian distance (sqrt(5) is the length of the diagonal of a 2 by 1 square).

When you're running the algorithm you estimate the total distance f(n) from any node n that we've got to already as the distance so far plus the heuristic distance. I.e. f(n) = g(n) + h(n) where g(n) is the distance from (x1,y1) to node n and h(n) is the estimated heuristic distance from node n to (x2,y2). Given the nodes you've got to, you always choose the node n with the lowest f(n). I like the way you put it:

maintain a priority queue of nodes to be checked out ordered by g(n) + h(n).

If the heuristic is admissible then the algorithm finds the optimal solution because a suboptimal path can never be at the front of the priority queue: any fragment of the optimal path will always have a lower total distance (where, again, total distance is incurred distance plus heuristic distance).

The distance measure we've chosen here is monotonic (i.e. increases as the path lengthens rather than going up or down). In this case it's possible to show that it's efficient. As usual, see wikipedia or other sources on the web for more details. The Colorado state university page is particularly good and has nice discussions on optimality and efficiency.

Taking an example of going from (-200,-100) to (0,0), which is equivalent to your example of (0,0) to (200,100), in my implementation what we see with a Manhattan heuristic is as follows

The implementation does too much searching because with the heuristic h = Manhattan distance, taking steps of across 1 up 2 seem just as good as the optimal steps of across 2 up 1, i.e. the f() values don't distinguish the two. However the algorithm still finds the optimal solution of 100 moves. It takes 2118 steps, which is still a lot better than the breadth first search, which spreads out like an ink blot (I estimate it might take 20000 to 30000 steps).

How does it do if you choose the h = Euclidian distance?

This is a lot better! It only takes 104 steps, and it does so well because it incorporates our intuition that you need to head in roughly the right direction. But before we congratulate ourselves let's try another example, from (-200,0) to (0,0). Both heuristics find an optimal path of length 100. The Euclidian heuristic takes 12171 steps to find an optimal path, as shown below.

Whereas the Manhattan heuristic takes 16077 steps

Leaving aside the fact that the Manhattan heuristic does worse, again, I believe the real problem here is that there are multiple optimal paths. This isn't so strange: a re-ordering of an optimal path is still optimal. This fact is automatically taken into account by recasting the problem in a mathematical form along the lines of @Sneftel's answer.

In summary, A* with an admissible heuristic produces an optimal solution more efficiently than does BFS but it is likely that there are more efficient soluions out there. A* is a good default algorithm in cases where you can easily come up with a distance heuristic, and although in this case it isn't going to be the best solution, it's possible to learn a lot about the problem by implementing it.

Code below in C++ as you requested.

#include <memory>
using std::shared_ptr;
#include <vector>
using std::vector;
#include <queue>
using std::priority_queue;
#include <map>
using std::map;
using std::pair;
#include <math.h>

#include <iostream>
using std::cout;
#include <fstream>
using std::ofstream;

struct Point
{
    short x;
    short y;
    Point(short _x, short _y) { x = _x; y = _y; }
    bool IsOrigin() { return x == 0 && y == 0; }
    bool operator<(const Point& p) const {
        return pair<short, short>(x, y) < pair<short, short>(p.x, p.y);
    }
};

class Path
{
    Point m_end;
    shared_ptr<Path> m_prev;
    int m_length; // cached

public:
    Path(const Point& start)
        : m_end(start)
        { m_length = 0; }

    Path(const Point& start, shared_ptr<Path> prev)
        : m_end(start)
        , m_prev(prev)
    { m_length = m_prev->m_length +1; }

    Point GetEnd() const { return m_end; }
    int GetLength() const { return m_length; }

    vector<Point> GetPoints() const
    {
        vector<Point> points;
        for (const Path* curr = this; curr; curr = curr->m_prev.get()) {
            points.push_back(curr->m_end);
        }
        return points;
    }

    double g() const { return m_length; }
    //double h() const { return (abs(m_end.x) + abs(m_end.y)) / 3.0; } // Manhattan
    double h() const { return sqrt((m_end.x*m_end.x + m_end.y*m_end.y)/5); } // Euclidian
    double f() const { return g() + h(); }
};

bool operator<(const shared_ptr<Path>& p1, const shared_ptr<Path>& p2)
{
    return 1/p1->f() < 1/p2->f(); // priority_queue has biggest at end of queue
}

int main()
{
    const Point source(-200, 0);
    const Point target(0, 0);

    priority_queue<shared_ptr<Path>> q;
    q.push(shared_ptr<Path>(new Path(source)));

    map<Point, short> endPath2PathLength;
    endPath2PathLength.insert(map<Point, short>::value_type(source, 0));

    int pointsExpanded = 0;
    shared_ptr<Path> path;
    while (!(path = q.top())->GetEnd().IsOrigin())
    {
        q.pop();
        const short newLength = path->GetLength() + 1;
        for (short dx = -2; dx <= 2; ++dx){
            for (short dy = -2; dy <= 2; ++dy){
                if (abs(dx) + abs(dy) == 3){
                    const Point newEnd(path->GetEnd().x + dx, path->GetEnd().y + dy);
                    auto existingEndPath = endPath2PathLength.find(newEnd);
                    if (existingEndPath == endPath2PathLength.end() ||
                        existingEndPath->second > newLength) {
                        q.push(shared_ptr<Path>(new Path(newEnd, path)));
                        endPath2PathLength[newEnd] = newLength;
                    }
                }
            }
        }
        pointsExpanded++;
    }

    cout<< "Path length " << path->GetLength()
        << " (points expanded = " << pointsExpanded << ")\n";

    ofstream fout("Points.csv");
    for (auto i : endPath2PathLength) {
        fout << i.first.x << "," << i.first.y << "," << i.second << "\n";
    }

    vector<Point> points = path->GetPoints();
    ofstream fout2("OptimalPoints.csv");
    for (auto i : points) {
        fout2 << i.x << "," << i.y << "\n";
    }

    return 0;
}

Note this isn't very well tested so there may well be bugs but I hope the general idea is clear.