Блог

Пожалуйста, помогите мне реализовать следующий алгоритм. Я новичок, и эта проблема сбивает меня с толку.

Алгоритм должен найти кратчайший путь от верхнего левого угла до нижнего правого. Нижний правый элемент всегда равен 0. Массив всегда квадратный (например, 3×3).

Перемещаться по массиву можно только вниз или вправо. Текущая позиция и элемент int, так называемая сила перехода (например, если мы находимся в начале в точке [0] [0], а соответствующий элемент равен 2, тогда мы можем переместить 2 вниз (D2 ) -> [2] [0] или 2 вправильно (R2) -> [0] [2]). Если сила прыжка выбрасывает нас за пределы поля (например, массив 3х3 и мы наступили на ячейку 5, то в любом случае мы вылетаем с поля в обе стороны), нам нужно начинать сначала и искать другой путь.

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

Пример того, как работает алгоритм (таким образом, путь будет [D1, R2, D1] — один ход вниз, два хода вправо и один ход вниз)

Я пробовал разные подходы, теперь я борюсь с DFS после составления неявного графика из input int[][], и ответ, который я получаю, не является кратчайшим путем. Я также слышал, что динамическое программирование может помочь, но не знаю, как это реализовать.

мой код с небольшим тестом включен:

 public class Main {

int indexError = 0;
int shortestPathLen = Integer.MAX_VALUE;
List<String> shortestPath = new ArrayList<>();
List<List<String>> allPaths;
List<String> solution = new ArrayList<>();

public List<List<String>> findAllPaths(int[][] map, int D, int R) {
int currentPosition = map[D][R]; //D - down, R - right
 if (currentPosition == 0) {
allPaths.add(solution);
return allPaths;
}
if (D   currentPosition <= indexError) {
solution.add("D"   currentPosition);
findAllPaths(map, D currentPosition, R);
}
if (R   currentPosition <= indexError) {
solution.add("R"   currentPosition);
findAllPaths(map, D, R currentPosition);
}
solution = new ArrayList<>();
return allPaths;
}  

public List<String> findPath(int[][] map) {
indexError = map[0].length - 1;
shortestPathLen = Integer.MAX_VALUE;
allPaths = new ArrayList<>();

List<List<String>> l = findAllPaths(map, 0, 0);
for (List<String> path : l) {
if (path.size() < shortestPathLen) {
    shortestPathLen = path.size();
    shortestPath = path;
}
}
return shortestPath;
}

public static void main(String[] args) {
Main main = new Main();
// int len = 3;
// int[] array =   {1, 2, 2,
//                 2, 10, 1,
//                 3, 2, 0}; // from example
int len = 9;
int[] array =
            {1, 10, 20, 1, 2, 2, 1, 2, 2,
            1, 10, 1, 10, 2, 2, 1, 2, 2,
            1, 10, 1, 1, 20, 2, 1, 2, 2,
            2, 1, 10, 1, 1, 20, 1, 2, 2,
            1, 2, 2, 10, 1, 1, 10, 2, 2,
            2, 1, 1, 1, 10, 1, 1, 20, 2,
            1, 2, 2, 1, 2, 10, 1, 1, 20,
            1, 1, 1, 1, 2, 2, 10, 1, 1,
            1, 2, 1, 1, 2, 2, 1, 1, 0};
int[][] map = new int[len][len];
int k = 0;
for (int i = 0; i < len; i  ) {
   for (int j = 0; j < len; j  ) {
    map[i][j] = array[k];
    k  ;
  }
}
List result = main.findPath(map);
System.out.println("n"   result   ", "   result.size()   " jumps");
// = must be [D1, D1, D1, D2, R2, D1, R2, D2, R2, R1, R1], 11 jumps
}}
 

Или с подходом поиска в глубину.

 public List<List<String>> findAllPaths(int[][] map, int D, int R) {
    System.out.printf("findPath(map, %d, %d) called %n", D, R);
    
    // Get the limits of the map
    int mapSize_Y = map.length;
    int mapSize_X = map[0].length;

    // If given coordinates are not in the map
    // Since the moves are restircted to down and right, no need to check lower border
    if (R >= mapSize_X || D >= mapSize_Y) {
        System.out.printf("Point at (%d, %d) not in the map%n", D, R);
        return null;
    }

    int jumpStrength = map[D][R]; //D - down, R - right

    if (jumpStrength == 0) {
        System.out.printf("Found goal at (%d, %d)%n", D, R);
        return Collections.emptyList();
    }

    // Move forward and call the function recursively
    // Spoken - get all subpaths that are possible from this point on
    var subPathsDown = findAllPaths(map, D   jumpStrength, R);
    System.out.printf("subpaths after findPath(map, %d, %d) returned -> %s%n", D   jumpStrength, R, subPathsDown);
    var subPathsRight = findAllPaths(map, D, R   jumpStrength);
    System.out.printf("subpaths after findPath(map, %d, %d) returned -> %s%n", D, R   jumpStrength, subPathsRight);

    // Add the move that produced the subpaths to the result
    var subPaths = new HashMap<String, List<List<String>>>() {{
        if (Objects.nonNull(subPathsDown)) {
            put("D"   jumpStrength, subPathsDown);
        }
        if (Objects.nonNull(subPathsRight)) {
            put("R"   jumpStrength, subPathsRight);
        }
    }};

    // If no further path is found return
    if (MapUtils.isEmpty(subPaths)) {
        System.out.printf("No valid Subpaths at Point (%d, %d) %n", D, R);
        return null;
    }

    // Change key-value structure to a list with the key as first entry
    // and the values of the map value afterwards 
    List<List<String>> result = subPaths.entrySet()
            .stream()
            .flatMap(e -> {
                if (CollectionUtils.isEmpty(e.getValue())) {
                    return Stream.of(new ArrayList<String>() {{
                        add(e.getKey());
                    }});
                }

                return e.getValue()
                        .stream()
                        .map(sp -> new ArrayList<String>() {{
                            add(e.getKey());
                            addAll(sp);
                        }});
            })
            .collect(Collectors.toList());

    return resu<
}
 

Кроме того, вы можете удалить все атрибуты вашего основного класса, если измените метод findPath на:

 public List<String> findPath(int[][] map) {
    int shortestPathLen = Integer.MAX_VALUE;
    List<String> shortestPath = new ArrayList<>();

    List<List<String>> l = findAllPaths(map, 0, 0);
    for (List<String> path : l) {
        if (path.size() < shortestPathLen) {
            shortestPathLen = path.size();
            shortestPath = path;
        }
    }
    return shortestPath;
}