CODEWITHSUNDEEP
javarecursionoptimizationpath-findingbacktracking
cmplx96
cmplx96

Reputation: 1651

backtracking - find optimal path in 2-d grid

input:

3,4,8,7,3
5,S,7,2,3,
8,5,5,8,10
9,3,3,8,7
6,10,3,G,1

the goal is to find the optimal path from the start (S) to the goal (G).

we can move upwards, downwards, to the left and to the right.

the cost is the sum of all elements on the path.

my idea was to use backtracking, however so far i have only managed to find a path, but it is far from optimal.

public List<Point> getNeighbours(Point p, int[][] grid) {
    List<Point> neighbours = new LinkedList<>();
    if (p.getX() > 0) {
        neighbours.add(new Position(p.getX() - 1, p.getY()));
    }
    if (p.getX() < grid.length - 1) {
        neighbours.add(new Position(p.getX() + 1, p.getY()));
    }
    if (p.getY() > 0) {
        neighbours.add(new Point(p.getX(), p.getY() - 1));
    }
    if (p.getY() < grid[p.getX()].length - 1) {
        neighbours.add(new Point(p.getX(), p.getY() + 1));
    }
    return neighbours;
}

private class IntBox {
    int value;

    public IntBox(int value) {
        this.value = value;
    }

}

private boolean findPath(int[][] grid, Point current, Point goal LinkedList<Point> path, Set<Point> visited, IntBox minDist, int dist) {
    if (current.getX() == goal.getX() && current.getY() == goal.getY()) {
        minDist.value = Math.min(dist, minDist.value);
        return true;
    }
    for (Point neighbour : getNeighbours(current, grid)) {
        if (visited.contains(neighbour)) {
            continue;
        }
        visited.add(nachbar);
        if (findPath(grid, neighbour, goal, path, visited, minDist, dist+grid[neighbour.getX()][neighbour.getY()])) {
            path.addFirst(nachbar);
            return true;
        }
    }
    return false;
}

Upvotes: 0

Views: 1074

Answers (1)

J&#225;n Halaša
J&#225;n Halaša

Reputation: 8421

Take a look at the Dijkstra's algorithm or some other shortest path problem solutions.

The solution could be like this:

  1. Every node in the grid will have two extra fields - minimal cost from the start and the closest node that leads to the starting point (on the minimal cost path).
  2. Calculating new field values for all nodes directly accessible from S and then move to a node with the lowest minimal cost value. For an animated example, see Wikipedia.
  3. When you calculate values for all nodes, you will have a value for G as well and you can track the path with the lowest cost using the new field.

Upvotes: 1

Related Questions