Учитывая квадратную сетку размера N, каждая ячейка которой содержит целочисленную стоимость, которая представляет собой стоимость прохождения через эту ячейку, нам нужно найти путь от верхней левой ячейки к нижней правой ячейке, при котором общие затраты будут минимальными. Из ячейки (i, j) мы можем перейти (i, j-1), (i, j + 1), (i-1, j), (i + 1, j).
Примечание: предполагается, что циклы отрицательной стоимости не существуют во входной матрице.
Example 1:
Input: grid = {{9,4,9,9},{6,7,6,4},
{8,3,3,7},{7,4,9,10}}
Output: 43
Explanation: The grid is-
9 4 9 9
6 7 6 4
8 3 3 7
7 4 9 10
The minimum cost is-
9 + 4 + 7 + 3 + 3 + 7 + 10 = 43.
Мой рабочий код:
global INT_MAX
# value of n is passed by the driver along with the grid
INT_MAX = 3 ** 38
class Solution:
# <- this returns the minVertex's co-orinates ->
def minimumVertex(self,distMat,visited):
minVertexi = 0
minVertexj = 0
max1 = INT_MAX
for i in range(n):
for j in range(n):
if distMat[i][j] < max1 and visited[i][j] == False:
max1 = distMat[i][j]
minVertexi = i
minVertexj = j
return minVertexi, minVertexj
def minimumCostPath(self, grid):
# <- visited matrix is created with all False ->
visited = []
for i in range(n):
eachRow = []
for j in range(n):
eachRow.append(False)
visited.append(eachRow)
# <- distMat is created with all values initialized with INT_MAX ->
distMat = []
for i in range(n):
eachRow1 = []
for j in range(n):
eachRow1.append(INT_MAX)
distMat.append(eachRow1)
distMat[0][0] = grid[0][0]
drow = [-1, 1, 0, 0]
dcol = [0, 0, -1, 1]
for _ in range(n):
for currj in range(n):
mini,minj = self.minimumVertex(distMat,visited)
visited[mini][minj] = True
for k in range(len(drow)):
nbri = mini + drow[k]
nbrj = minj + dcol[k]
# print("outside nbri = ",nbri,"outside nbrj = ",nbrj)
if nbri >=0 and nbrj >= 0 and nbri < n and nbrj < n:
if visited[nbri][nbrj] == False:
# print("inside nbri = ",nbri,"inside nbrj = ",nbrj)
if distMat[nbri][nbrj] > distMat[mini][minj] + grid[nbri][nbrj]:
distMat[nbri][nbrj] = distMat[mini][minj] + grid[nbri][nbrj]
return distMat[n-1][n-1]
Ожидаемое время Compelxity: O (n2 * журнал (n))
Ожидаемое вспомогательное пространство: О (п2)
Проблема с моим кодом:
Моя логика в порядке, но время превышает лимит, как мне ее оптимизировать?
ПРИМЕЧАНИЕ: Сетка всегда представляет собой квадратную сетку, и N (размер) передается функции вместе с сеткой. Я взял N = 4 здесь, потому что отлаживал код для одного тестового примера.
1 ответ
Фактическая временная сложность
Как вы правильно утверждаете, ожидал временная сложность Дейкстры на квадратной матрице равна O(n^2 log n)
. Однако ваш алгоритм имеет сложность не менее O(n^4)
из-за того, как вы располагаете минимальную вершину.
for _ in range(n):
for currj in range(n):
# <--- executed n^2 times here
mini,minj = self.minimumVertex(distMat,visited)
...
def minimumVertex(self,distMat,visited):
minVertexi = 0
minVertexj = 0
max1 = INT_MAX
for i in range(n):
for j in range(n):
# <--- takes n^2 time
...
Фактически, реализованный вами алгоритм не является чисто алгоритмом Дейкстры, а представляет собой смесь Алгоритм Дейкстры и Алгоритм Флойда. Вы должны прочитать ссылки выше, особенно Псевдокод разделы, чтобы понять, как работает каждый из алгоритмов, и какие части вы смешиваете.
Алгоритм Дейкстры
Ключевая структура данных, которая позволяет алгоритму Дейкстры работать в O(n^2 log n)
время это приоритетная очередь который позволяет вставлять элементы и удалять верхний элемент в O(log n)
время. Эта структура данных обычно реализуется с использованием двоичная куча, и имеет стандартную реализацию на Python как heapq
библиотека.
Вы должны адаптировать свой код для использования этой структуры данных вместо таблицы расстояний, как показано ниже. Важно, чтобы первый поле кортежа — это расстояние, так как оно определяет сортировку.
def minimumCostPath(self, grid):
# definitions of n, visited, drow, dcol
queue = [(grid[0][0], 0, 0)]
while queue:
dist, i, j = heapq.heappop(queue)
if visited[i][j]:
continue
visited[i][j] = True
if i == j == n - 1:
return dist
for k in range(len(drow)):
ni = i + drow[k]
nj = j + dcol[k]
if 0 <= ni < n and 0 <= nj < n:
heapq.heappush(queue, (dist + grid[ni][nj], ni, nj))
assert False, "queue is exhausted but we haven't reached the destination yet"
Сравнительный сюрприз
Написав все это, я решил количественно оценить улучшение с помощью сравнительного анализа. Это код, который я использовал, чтобы увидеть, как моя реализация сравнивается с оригиналом.
if __name__ == "__main__":
import time
N = 100
grid = [[j for _ in range(N)] for j in range(N)]
solver = Solution()
start = time.time()
print(solver.minimumCostPath(grid))
end = time.time()
print(f"Solved grid with size {N} in {1000*(end - start):.3f}ms")
К моему удивлению, ваша версия была на самом деле быстрее, но что более важно, это дало неверный полученные результаты.
Моя логика в порядке
Нет, это не так. Проблема в использовании n
в minimumVertex
функция. Потому что вы определяете n = 4
как глобальное значение используется вместо фактического размера сетки. Это делает ваш алгоритм быстрым, но на самом деле неверным для n > 4
.
Вывод
Как оказалось, алгоритм, который вы (я полагаю) намеревался реализовать, O(n^4)
, ваш код был на самом деле O(n^2)
все это время. Если это действительно привело к TLE, Python не сможет справиться с этим вопросом. Что я считаю более вероятным, так это то, что ваш код не прошел из-за неправильного ответа — использование правильной реализации Дейкстры, приведенной выше, может исправить это.
Этот код был предназначен для онлайн-судьи, и поэтому я определил n = 4, потому что я отлаживал код для одного тестового примера, где N было 4. Теперь поймите это, сетка всегда представляет собой квадратную сетку (строки = столбцы), а драйвер вызывает мою функцию с сеткой и N, так что это действительно не проблема, я надеюсь, вы понимаете то, что я пытаюсь сказать.
— Шубхам Прашар
Кроме того, не обижайтесь, но не говорите, что логика неверна, и попробуйте спросить ОП или подумать о причине чего-то.
— Шубхам Прашар
@ShubhamPrashar В следующий раз, пожалуйста, включите в вопрос весь код. В
minimumCostPath
вы вычисляете правильное n из данной сетки, но переходите к использованию разные п вminimumVertex
. С предоставленным фрагментом нет никакого разумного объяснения, кроме логической ошибки. Фактически, даже если вы определяете глобальное n как размер сетки, я все равно считаю это логической ошибкой — вы должны либо использовать глобальное n в обеих функциях, либо вычисленное n в обеих функциях.— сложены
Да, я полностью с вами согласен, но что вы думаете о части сложности? Все в порядке, но получить TLE. Как его оптимизировать?
— Шубхам Прашар
@ShubhamPrashar Перечитайте первые два раздела моего ответа, где я показываю, что сложность вашего решения на самом деле
O(n^4)
. Вы должны использовать правильная реализация Дейкстры, что даст вам желаемую сложностьO(n^2 log n)
.— сложены
Показать 3 больше комментариев