Как найти путь наименьшей суммы, двигаясь вправо и вниз в двоичной матрице

У меня есть бинарная матрица. Каждый столбец соответствует вершине графа. Если я иду по пути (начиная с вершины "col 1", затем перехожу к "col 2" и т. д.), я должен заплатить некоторые штрафы. Но так как полицейских на пути ровно столько, я могу подождать некоторое время, пока в следующей вершине не останется ни одного полицейского, а затем перейти. Чтобы уточнить, следующая матрица (первая строка - строка «название»):

A B C D
0 0 1 0
1 0 0 1
1 1 0 0
1 1 1 1
0 0 0 0

Кодирует, что я заплачу, если окажусь на А после ожидания дополнительных 1, 2 или 3 часов до этой точки; на B я заплачу через 2 или 3 дополнительных часа; на C я заплачу через 0 или 3 часа; на D я заплачу, если подожду 1 или 3 часа.

Таким образом, оптимальный путь здесь «перейти к B, подождать 1 час, перейти к C, подождать 1 час, перейти к D» с общей стоимостью 0. (этот путь отмечен «X» на следующем)

A B C D
X X 1 0
1 X X 1
1 1 X X
1 1 1 1
0 0 0 0

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

Как я могу эффективно создать такой путь?

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

Я думал об использовании подхода DP, но мне не удалось сформулировать тот, который не ломался бы в некоторых случаях, независимо от того, пытаюсь ли я добавить построчно или столбец за столбцом.

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
0
29
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Начнем с простого вопроса. Допустим, вы находитесь в строке i, столбце j (то есть в ячейке (i,j)) матрицы. Какой выбор у вас есть для следующего шага?

Поскольку мы движемся по столбцам, j становится j+1. Но для ряда вы можете жадно выбрать ряд, который платит минимальный штраф. То есть вы можете выбрать i' в диапазоне (i+1, row_count) так, чтобы fine(i,j) было минимальным. (Примечание: поскольку строка представляет моменты времени, вы не можете перейти от строки i к i-1, что эффективно сокращает наше пространство поиска).

Алгоритм:
(n = number of rows = len(matrix), m = number of columns)

  1. Для крайнего правого столбца у нас нет дальнейших путей, поэтому никаких изменений не требуется.
  2. Для столбцов m-1 to 1 минимальный штраф для ячейки (i,j) составит
fine(i,j) = (matrix[i][j] == 1) + (min_value in matrix[i][j+1] to matrix[n][j+1])
  1. Минимальная стоимость пути будет matrix[0][0], откуда вы прослеживаете путь, проверяя минимальные значения в каждом столбце.

Последний момент, который нам нужно осветить, это как получить min_value in matrix[i][j+1] to matrix[n][j+1] на шаге 2? Если вы переходите от row n к row 1, задача в основном сводится к отслеживанию наименьшего посещенного элемента, что можно сделать с помощью простой переменной/счетчика.

Этот подход не требует дополнительного места (поскольку мы модифицируем данную матрицу) и O(M*N) временной сложности.

Я могу ошибаться, но я не думаю, что это работает. Предположим, наша матрица: 0100 0011 Оптимальный путь движется слева направо без ожидания (общая стоимость 1), но жадный алгоритм ждет час в вершине 1, прежде чем перейти к вершинам 2, 3, затем 4 с общей стоимостью 2.

Kemonius 30.03.2022 16:41

@Kemonius нет, жадный алгоритм идет слева направо со стоимостью 1, так как cost[0][1] = 1 и cost[1][1] = 2

Abhinav Mathur 30.03.2022 16:44

Ах, моя ошибка, я не видел бит справа налево. Спасибо за Ваш ответ!

Kemonius 30.03.2022 17:01

Другие вопросы по теме