0

Помогите, пожалуйста, реализовать следующий алгоритм.

Необходимо реализовать алгоритм для нахождения самого короткого пути из верхнего левого угла в правый нижний. Правый нижний элемент всегда равен 0. Массив всегда квадрат (например 3х3).

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

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

Пример работы алгоритма

Таким образом путь будет [D1, R2, D1] - один ход вниз, два хода направо и один ход вниз

Моё решение, которое способно решить пример выше, но не справляется с решением массивов побольше (тест приложен)

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}; // массив из примера
    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
}}
3
  • Вообще, если я правильно понимаю, то вам просто нужно написать bfs по неявному графу. В данном случае вершинами графа будут являться все клетки поля, а ребер, исходящих из каждой вершины, всегда будет не больше двух: вниз и направо. конкретный алгоритм для графа в явном виде очень просто гуглится, а если возникнут проблемы с адаптированием для вашего конкретного случая, то пишите сюда же, к примеру
    – EzikBro
    Commented 29 нояб. 2020 в 14:46
  • @EzikBro Как я понял, необходимо построить граф из вводных данных, где каждая вершина будет иметь не более двух ребер и после применить поиск в ширину?
    – Nim Pr
    Commented 30 нояб. 2020 в 13:25
  • Да, но более верное решение вам уже написали в ответах: используйте динамическое программирование.
    – EzikBro
    Commented 30 нояб. 2020 в 13:53

1 ответ 1

4

Задачу можно решить динамическим программированием.

Добавление: для нахождения самого пути (а не только его длины) нужно ещё записывать, из какой ячейки пришли в текущую

Заполняем таблицу B[][] заведомо большим значением (2*Size). B[0][0] = 0. В каждой ячейке будет содержаться минимальное количество шагов для её достижения.

В таблице C[][] будем хранить, откуда пришли в данную ячейку по кратчайшему пути

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

step = A[i][j]
if B[i,j]+1 < B[i+step][j]:
     B[i+step][j] = B[i,j]+1
     С[i+step][j] = (i, j)
if B[i,j]+1 < B[i][j+step]:
     B[i][j+step] = B[i,j]+1
     С[i][j+step] = (i, j)

После заполнения таблице идём из правого нижнего угла влево-вверх по ячейкам, записанным в C[][]

2
  • Немного не понял как именно можно применить это и что будет находится в массиве B после обхода исходного массива. Также B[i,j]+1 ввело меня в тупик
    – Nim Pr
    Commented 30 нояб. 2020 в 13:18
  • Так написано же - в B[i][j] хранится количество шагов до данной ячейки. Если мы попадаем в B[i+step][j] из B[i,j], то делаем количество шагов в B[i,j] и ещё один шаг. А если то, что уже есть в B[i+step][j] - меньше, то маршрут через B[i,j] не нужен
    – MBo
    Commented 1 дек. 2020 в 3:04

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.