Оптимизация Дейкстры на сетке Python (интервью Microsoft)

Учитывая квадратную сетку размера 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 ответ
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).

    — сложены

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *