代价函数变化的 Dijkstra 算法

Question

我面临以下编码挑战问题：

"你在 NxN 山区的起始位置 [0, 0]，你只能在四个主要方向之一（即北、东、南、西）中移动。Return 最小到目标位置 [N-1, N-1] 的爬升轮数。相邻位置之间的爬升轮数定义为位置高度差（上升或下降）。位置高度定义为整数 (0-9)。"

例如，

的结果

  "010",
  "010",
  "010"

将是 2，因为我们在 [0,1] 中从 0 上升到 1，在 [2,2] 中我们从 1 下降到 0。我的想法是实现 Dijkstra 算法，改变代价函数。距离将给出为： distance_current_vertex_to_0 + delta_next_vertex_to_current_vertex 但是，我的实现有问题，因为我总是得到局部最优值而不是全局最优值。例如

"9589747",
"9141279",
"2915307",
"5271413",
"8795390",
"1251866",
"4697825"

应该 return 26，但我的代码实现得到 30。所以我的问题是：我的 Djikstra 算法版本有什么不正确的地方？我从 this explanation video. The coding question comes from: here.

中激励自己

我的代码：

from copy import deepcopy
import numpy as np

def search_neighbours(pos, vv, min_distances, nearest_neighbors, m):

    pos_id = int(pos[0] * len(m) + pos[1])
    sorted_neighbours = {}

    #for the current vertex, examine it's unvisited vertices
    for key, comb in enumerate([[1, 0], [0, 1], [0, -1], [-1, 0]]):

        i = comb[0]
        j = comb[1]

        next_pos = [pos[0] + i, pos[1] + j]
        next_pos_id = int(next_pos[0] * len(m) + next_pos[1])

        if 0 <= next_pos[0] < len(m) and 0 <= next_pos[1] < len(m):

            #if the calculated distance of a vertex ist less than the known distance, update the shortest distance
            d = min_distances[pos[0]][pos[1]] + abs(int(m[next_pos[0]][next_pos[1]]) - int(m[pos[0]][pos[1]]))
            if d < min_distances[next_pos[0]][next_pos[1]]:
                min_distances[next_pos[0]][next_pos[1]] = d
                #update the previous vertex for each of the updated distances
                nearest_neighbors[next_pos[0]][next_pos[1]] = pos

            if next_pos_id not in vv:
                sorted_neighbours[tuple(comb)] = abs(int(m[next_pos[0]][next_pos[1]]) - int(m[pos[0]][pos[1]]))

    sorted_neighbours = {k: v for k, v in sorted(sorted_neighbours.items(), key=lambda item: item[1])}
    #add the current vertex to the list of vertices
    vv.append(pos_id)

    #visit the unvisited vertex with the smallest distance from the start vertex
    if pos == [len(m) - 1, len(m) - 1]:
        return True
    else:
        k = 0
        while k < len(sorted_neighbours.keys()):
            dir = list(sorted_neighbours.keys())[k]
            next_pos = [pos[0] + dir[0], pos[1] + dir[1]]
            if not search_neighbours(next_pos, vv, min_distances, nearest_neighbors, m):
                k += 1
            else:
                return True

        return False #in this case ended somewhere else on the map and don't want that

def path_finder(m):
    print(m)
    m = m.split("\n")
    pos = [0, 0]
    vv = []  # visited vertices
    min_distances = [[99 for _ in range(len(m))] for _ in range(len(m))]
    min_distances[0][0] = 0
    nearest_neighbors = [[0 for _ in range(len(m))] for _ in range(len(m))]
    nearest_neighbors[0][0] = [0,0]
    search_neighbours(pos, vv, min_distances, nearest_neighbors, m)
    return min_distances[len(m) - 1][len(m) - 1]

m = "\n".join([
    "9589747",
    "9141279",
    "2915307",
    "5271413",
    "8795390",
    "1251866",
    "4697825"
])


path_finder(m)

Answer 1

这是 Dijkstra 的样子：

def dijkstra(m):
    heights = [[int(c) for c in line] for line in m.split()]
    n, m = len(heights), len(heights[0])
    distances = [[float('inf') for _ in range(m)] for _ in range(n)]
    heap = [((0, 0, 0))]  # cost so far, x, y
    while heap:
        prev_distance, x, y = heapq.heappop(heap)
        if (x, y) == (m-1, n-1):
            return prev_distance
        for stepx, stepy in ((0, 1), (1, 0), (-1, 0), (0, -1)):
            new_x, new_y = x + stepx, y + stepy
            if not 0 <= new_x < m or not 0<= new_y < n:
                continue  # out of bounds, ignore
            new_distance = prev_distance + abs(heights[y][x] - heights[new_y][new_x])
            if new_distance < distances[new_y][new_x]:  # expand
                distances[new_y][new_x] = new_distance
                heapq.heappush(heap, (new_distance, new_x, new_y))
    return -1  # path not found

dijkstra(m) returns 26，符合预期

代价函数变化的 Dijkstra 算法

Djikstra's algorithm with change in cost function

python

graph

dijkstra