найти кратчайший путь между двумя точками с препятствиями

Question

Мне нужно найти кратчайший путь между двумя точками в сетке с учетом препятствий.

Учитывая 2-мерную матрицу, где некоторые элементы заполнены 1, а остальные элементы заполнены.Здесь X означает, что вы не можете перейти к этим точкам.Из ячейки вы можете перемещаться влево, вправо, вверх или вниз.По заданным двум точкам в матрице найти кратчайший путь между этими точками.Здесь S является отправной точкой, а E - конечной.

Я придумал приведенный ниже код, но я хотел понять с точки зрения собеседования, что является наиболее эффективным алгоритмом для решения этой проблемы?Есть ли лучший способ сделать это?

  public static void main(String[] args) {
    char[][] matrix =  {{'1','1','1', '1'},
                        {'1','S','1', '1'},
                        {'1','1','X', '1'},
                        {'1','1','1', 'E'}};

    System.out.println(shortestPath(matrix));
  }

  public static int shortestPath(char[][] matrix) {
    int s_row = 0, s_col = 0;
    boolean flag = false;
    for (s_row = 0; s_row < matrix.length; s_row++) {
      for (s_col = 0; s_col < matrix[0].length; s_col++) {
        if (matrix[s_row][s_col] == 'S')
          flag = true;
        if (flag)
          break;
      }
      if (flag)
        break;
    }
    return shortestPath(matrix, s_row, s_col);
  }

  public static int shortestPath(char[][] matrix, int s_row, int s_col) {
    int count = 0;
    Queue<int[]> nextToVisit = new LinkedList<>();
    nextToVisit.offer(new int[] {s_row, s_col});
    Set<int[]> visited = new HashSet<>();
    Queue<int[]> temp = new LinkedList<>();

    while (!nextToVisit.isEmpty()) {
      int[] position = nextToVisit.poll();
      int row = position[0];
      int col = position[1];

      if (matrix[row][col] == 'E')
        return count;
      if (row > 0 && !visited.contains(new int[] {row - 1, col}) && matrix[row - 1][col] != 'X')
        temp.offer(new int[] {row - 1, col});
      if (row < matrix.length - 1 && !visited.contains(new int[] {row + 1, col})
          && matrix[row + 1][col] != 'X')
        temp.offer(new int[] {row + 1, col});
      if (col > 0 && !visited.contains(new int[] {row, col - 1}) && matrix[row][col - 1] != 'X')
        temp.offer(new int[] {row, col - 1});
      if (col < matrix[0].length - 1 && !visited.contains(new int[] {row, col + 1})
          && matrix[row][col + 1] != 'X')
        temp.offer(new int[] {row, col + 1});

      if (nextToVisit.isEmpty() && !temp.isEmpty()) {
        nextToVisit = temp;
        temp = new LinkedList<>();
        count++;
      }

    }
    return count;
  }

Answer 1

Надеюсь, это поможет -

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

import GridNavigationTest.Direction;

public class GridNavigationTest {
    public static final int[][] navigableGrid = new int[][] { 
        { 1, 1, 1, 1 }, 
        { 1, 0, 0, 1 }, 
        { 1, 0, 1, 1 },
        { 1, 0, 1, 0 }, 
        { 1, 1, 9, 0 }
    };

    public enum Direction {
        UP, DOWN, RIGHT, LEFT;

        public Direction reverse() {
            Direction reverse = null;

            if (this.equals(Direction.UP)) {
                reverse = DOWN;
            } else if (this.equals(Direction.DOWN)) {
                reverse = UP;
            } else if (this.equals(Direction.RIGHT)) {
                reverse = LEFT;
            } else if (this.equals(Direction.LEFT)) {
                reverse = RIGHT;
            }

            return reverse;
        }
    };

    private static final Map<String, PathNode> nodesRegistry = new TreeMap<>();
    private static final RouteRegistry routeRegistry = new RouteRegistry();

    private static final String keyRefDelimiter = ":";
    private static final String keyRefFormat = "%d" + keyRefDelimiter + "%d";

    private static PathNode destinationNode = null;

    public static void main(String... arguments) {
        createNodesRegistry();
        findRoutes();
        printSignificantRoutes();
    }

    private static void printSignificantRoutes() {
        String shortestRoute = Arrays.toString(routeRegistry.getShortestRoute());
        System.out.println("-> Shortest\t: " + shortestRoute);

        String longestRoute = Arrays.toString(routeRegistry.getLongestRoute());
        System.out.println("-> Longest\t: " + longestRoute);
    }

    private static void createNodesRegistry() {
        for (int rowCount = 0; rowCount < navigableGrid.length; rowCount++) {
            for (int colCount = 0; colCount < navigableGrid[rowCount].length; colCount++) {
                // add current element's node representation to the nodes map, only if it is
                // active (value > 0)
                if (navigableGrid[rowCount][colCount] > 0) {
                    IntPair point = new IntPair(rowCount, colCount);
                    int value = navigableGrid[rowCount][colCount];

                    PathNode currentElementNode = new PathNode(point, value);
                    nodesRegistry.put(String.format(keyRefFormat, rowCount, colCount), currentElementNode);

                    // set adjacent references
                    setAdjacentReference(currentElementNode, rowCount - 1, colCount, Direction.UP);
                    setAdjacentReference(currentElementNode, rowCount + 1, colCount, Direction.DOWN);
                    setAdjacentReference(currentElementNode, rowCount, colCount + 1, Direction.RIGHT);
                    setAdjacentReference(currentElementNode, rowCount, colCount - 1, Direction.LEFT);

                    if (currentElementNode.getNodeValue() == 9) {
                        destinationNode = currentElementNode;
                    }
                }
            }
        }
    }

    private static void setAdjacentReference(PathNode currentNode, int row, int col, Direction direction) {
        PathNode adjacentNode = nodesRegistry.get(String.format(keyRefFormat, row, col));
        if (adjacentNode != null) {
            currentNode.setAdjacentNode(direction, adjacentNode);

            // set the reverse lookup link
            if (adjacentNode.getAdjacentNode(direction.reverse()) == null) {
                adjacentNode.setAdjacentNode(direction.reverse(), currentNode);
            }
        }
    }

    private static void findRoutes() {
        // initialize reverse tracing from the destination
        destinationNode.traceRoute(routeRegistry, null);
    }
}

class PathNode {
    private int nodeValue = 0;
    private Map<Direction, PathNode> adjacentNodes = new HashMap<>();
    private IntPair location = null;

    public PathNode() {
        super();
    }

    public PathNode(IntPair location, int value) {
        super();
        this.location = location;
        this.nodeValue = value;
    }

    public void traceRoute(RouteRegistry routeRegistry, PathNode fromNode) {
        if (!this.isStartNode()) {
            for (Entry<Direction, PathNode> entry : this.adjacentNodes.entrySet()) {
                PathNode node = entry.getValue(); 
                if (!node.equals(fromNode)) {
                    routeRegistry.put(this.location);
                    node.traceRoute(routeRegistry, this);
                }
            }
        } else {
            routeRegistry.put(this.location);
        }
    }

    public int getNodeValue() {
        return this.nodeValue;
    }

    public void setNodeValue(int value) {
        this.nodeValue = value;
    }

    public void setAdjacentNode(Direction direction, PathNode node) {
        this.adjacentNodes.put(direction, node);
    }

    public PathNode getAdjacentNode(Direction direction) {
        return this.adjacentNodes.get(direction);
    }

    public IntPair getLocation() {
        return location;
    }

    public void setLocation(IntPair location) {
        this.location = location;
    }

    public boolean isStartNode() {
        boolean returnValue = false;

        if (location != null) {
            returnValue = (location.getValue(0) == 0 && location.getValue(1) == 0);
        }

        return returnValue;
    }

    public boolean isDestinationNode() {
        return (this.getNodeValue() == 9);
    }
}

class IntPair {
    private Integer[] values = new Integer[2];

    public IntPair() {
        super();
    }

    public IntPair(Integer value1, Integer value2) {
        super();
        this.values[0] = value1;
        this.values[1] = value2;
    }

    public Integer getValue(int index) {
        return this.values[index];
    }

    public void setValue(int index, int value) {
        this.values[index] = value;
    }

    @Override
    public String toString() {
        return "[" + this.values[0] + ", " + this.values[1] + "]";
    }
}

class RouteRegistry {
    private int routeIndex = 1;
    private Map <String, List<IntPair>> routesMap = new HashMap<>();

    public RouteRegistry() {
        super();
    }

    public void put(IntPair point) {
        String activeRouteKey = String.format("Route %d", routeIndex);
        routesMap.computeIfAbsent(activeRouteKey, k -> new ArrayList<IntPair>());

        List<IntPair> routePoints = routesMap.get(activeRouteKey);
        routePoints.add(point);

        if (point.getValue(0) == 0 && point.getValue(1) == 0) {
            routeIndex++;
        }
    }

    public IntPair[] getShortestRoute() {
        IntPair[] routeArray = null;

        List<IntPair> shortestRoute = null;
        for (Entry<String, List<IntPair>> routeEntry :  routesMap.entrySet()) {
            List<IntPair> route = routeEntry.getValue();

            if (shortestRoute == null || shortestRoute.size() > route.size()) {
                shortestRoute = route;
            }
        }

        if (shortestRoute != null) {
            routeArray = shortestRoute.toArray(new IntPair[shortestRoute.size()]);
        } else {
            routeArray = new IntPair[0];
        }

        return routeArray;
    }

    public IntPair[] getLongestRoute() {
        IntPair[] routeArray = null;

        List<IntPair> longestRoute = null;
        for (Entry<String, List<IntPair>> routeEntry :  routesMap.entrySet()) {
            List<IntPair> route = routeEntry.getValue();

            if (longestRoute == null || longestRoute.size() < route.size()) {
                longestRoute = route;
            }
        }

        if (longestRoute != null) {
            routeArray = longestRoute.toArray(new IntPair[longestRoute.size()]);
        } else {
            routeArray = new IntPair[0];
        }

        return routeArray;
    }
}

Answer 2

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

Еще одна вещь, чтобы вы чувствовали себя комфортно в этом типе проблемы, один из способов - решить проблему такого типа больше.Вы найдете этот тип проблемы на этом сайте.