У меня есть бинарная матрица. Каждый столбец соответствует вершине графа. Если я иду по пути (начиная с вершины "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, но мне не удалось сформулировать тот, который не ломался бы в некоторых случаях, независимо от того, пытаюсь ли я добавить построчно или столбец за столбцом.
Начнем с простого вопроса. Допустим, вы находитесь в строке 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
)
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])
matrix[0][0]
, откуда вы прослеживаете путь, проверяя минимальные значения в каждом столбце.Последний момент, который нам нужно осветить, это как получить min_value in matrix[i][j+1] to matrix[n][j+1]
на шаге 2? Если вы переходите от row n
к row 1
, задача в основном сводится к отслеживанию наименьшего посещенного элемента, что можно сделать с помощью простой переменной/счетчика.
Этот подход не требует дополнительного места (поскольку мы модифицируем данную матрицу) и O(M*N)
временной сложности.
@Kemonius нет, жадный алгоритм идет слева направо со стоимостью 1, так как cost[0][1] = 1
и cost[1][1] = 2
Ах, моя ошибка, я не видел бит справа налево. Спасибо за Ваш ответ!
Я могу ошибаться, но я не думаю, что это работает. Предположим, наша матрица: 0100 0011 Оптимальный путь движется слева направо без ожидания (общая стоимость 1), но жадный алгоритм ждет час в вершине 1, прежде чем перейти к вершинам 2, 3, затем 4 с общей стоимостью 2.