Найти такой путь из клетки [i1, j1] в клетку [i2, j2], чтобы сумма чисел по данному пути была минимальной

Здравствуйте, есть такая задача:

1.Дан двумерный числовой массив размером N1xN2.
2.Найти такой путь из клетки [i1,j1] в клетку [i2,j2], чтобы сумма чисел по данному пути была минимальной.
3.Из каждой клетки массива допустимо двигаться вправо, влево, вверх или вниз. В клетки с нулями заходить нельзя.
4.Числа i1,i2,j1,j2 вводятся с клавиатуры.

Задача на динамическое программирование, понимающие, помогите пожалуйста с алгоритмом, код сам могу написать.

0

Сообщение от Котананас помогите пожалуйста с алгоритмом

обход графа в ширину/глубину

0

А другие варианты решения есть ?

0

волной вроде тоже годится, а те чем плохи?

0

Обход графа в ширину - это и есть волновой обход не ? Просто волновой алгоритм мне нужно использовать в следующем задании, не в этом, данное же задание нужно решить без использования графов.

0

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

Алгоритм.
1. Создать таблицу 1, в которую будет записываться оптимальная стоимость прохода в каждую ячейку на данном этапе оптимизации.
2. В начальную ячейку записать стоимость ее посещения, остальные ячейки заполнить числом -1.
3. Создать новую таблицу 2 аналогично таблице 1.
4. Выполнить просмотр всех ячеек таблицы 2 в цикле.
4.1 Если текущая ячейка проходима (стоимость посещения > 0), то выбрать одну из проходимых ячеек слева, справа, сверху или снизу в таблице 1, стоимость прохода для которой минимальна.
4.2 Записать в текущую ячейку таблицы 2 стоимость прохода до выбранной ячейки + стоимость посещения текущей ячейки.
5. Переписать значения из таблицы 2 в таблицу 1.
6. Повторять шаги 3-5 до тех пор, пока есть хотя бы одна оптимизация.
7. После завершения цикла конечная ячейка таблицы 1 содержит минимальную стоимость прохода до нее.

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

1

Сейчас заметил, что алгоритм получился не очень удачный: он делает больше шагов, чем требуется. Можно попробовать адаптировать алгоритм Дейкстры. Если получится, выложу сюда.

1

Спасибо.

0

При внимательном рассмотрении алгоритма Дейкстры выясняется, что он несколько избыточен для данной задачи. В графе больше свободы, чем в таблице. Попытки его упрощения приводят к волновому алгоритму с задержками. В отличие от базового его варианта, волна должна задерживаться в клетке на указанное количество шагов. Чтобы не просматривать все клетки в поиске следующего шага, можно использовать приоритетную очередь, из которой первыми извлекаются элементы с наименьшей оценкой.

Алгоритм.
1. Создать таблицу d, в которой все элементы равны -1, элемент (i1, j1) равен стоимости посещения данной ячейки.
2. Поместить в очередь координаты (i1, j1).
3. Извлечь из очереди координаты (i, j) с минимальной оценкой d[i][j].
4. Рассмотреть соседние ячейки сверху, снизу, справа и слева. Если среди них есть доступные для посещения (стоимость > 0) и ранее не посещенные (d[i'][j'] < 0), записать для них в таблицу d сумму d[i][j] + стоимость посещения выбранной ячейки. Поместить координаты этой ячейки (i', j') в очередь.
5. Пока очередь не пуста, повторять шаги 3 - 4.

Восстановление пути: запись направлений во вспомогательный массив или поиск пути от (i2, j2) к (i1, j1) по ячейкам таблицы d с минимальной оценкой d[i][j].

2

Ответьте пожалуйста:
1.На 3 этапе мы извлекли элемент с минимальной оценкой, куда этот элемент записывается ?
2.на 4 этапе "Поместить координаты этой ячейки (i', j') в очередь", какой именно, в которую мы записали "d[i][j] + стоимость посещения выбранной ячейки" ?
3.В 5-ом пункте, где именно нужно ставить это условие ?

0

Сообщение от Котананас 1.На 3 этапе мы извлекли элемент с минимальной оценкой, куда этот элемент записывается ?

Его координаты записываются во временную переменную, чтобы можно было ссылаться на его соседей. В конце итерации о нем можно забыть, т.к. путь до него уже вычислен и он будет оптимальным (доказательство есть в алгоритме Дейкстры. Правда там еще одна оптимизация проводится, но в таблице ее можно не делать, т.к. в ней невозможны более короткие пути, как в графе).

Сообщение от Котананас 2.на 4 этапе "Поместить координаты этой ячейки (i', j') в очередь", какой именно, в которую мы записали "d[i][j] + стоимость посещения выбранной ячейки" ?

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

Сообщение от Котананас 3.В 5-ом пункте, где именно нужно ставить это условие ?

Просто цикл while (!priority_queue.empty()), в котором будут выполняться действия шагов 3-4. Очередь можно сделать на обычном массиве/векторе с последующей сортировкой по убыванию. Нужный элемент всегда будет в конце и удаляется из массива за 1 шаг.

Если нужен код с примером реализации - скажите, выложу.

1

Спасибо, сделал, а как реализовать такую тему как у вас, чтобы в реальном времени показывало как по массиву идем ?

Добавлено через 1 час 49 минут
Можете не отвечать, уже сделал.

0

Добавлено через 7 минут

Сообщение от valen10 Если нужен код с примером реализации - скажите, выложу

Можно увидеть этот код?

0