用Python查找最小代价路径的程序

用Python查找最小代价路径的程序

假设我们有一个称为height的m×n的2D矩阵。heights[i][j]表示单元格(i,j)的高度。如果我们在单元格(0,0)处,我们想要前往右下角的单元格(m−1,n−1)。我们可以向上、向下、向左或向右移动,我们希望找到需要最小代价的路径。在这个问题中,路径的代价是路径中两个连续单元格之间高度差的最大绝对值。因此,最后我们需要找到到达目的地所需的最小代价。

如果输入如下:

2 3 4
4 9 5
6 4 6

那么输出将为1,因为路线[2,3,4,5,6]在连续单元格中的最大绝对值差为1。

为了解决问题,我们将遵循以下步骤:

  • 将行数与高度中的列数、列数分配给c。
  • 一个初始为tup(0,0,0)的队列。
  • 当队列不为空时,执行以下操作:
    • cur:队列中的第一个项目,并从队列中删除。
    • c_eff:cur[0]
    • x:cur[1]
    • y:cur[2]
    • 如果x等于r-1且y等于c-1,则:
      • 返回c_eff。
    • 如果heights[x, y]是空字符串,则:
      • 转到下一次迭代。
    • 对于每个dx,dy,都在[[1,0],[-1,0],[0,1],[0,-1]]中执行以下操作:
      • newx:x + dx
      • newy:y + dy
      • 如果0 <= newx
      • eff:c_eff和|heights[newx,newy] – heights[x,y]|的最大值。
      • 将tup(eff,newx,newy)插入队列中。
  • heights[x,y]:空字符串。

示例

下面是对这一问题的更好理解的实现:

import heapq
def solve(heights):
   r,c=len(heights),len(heights[0])
   queue=[(0,0,0)]

   while queue:

      cur=heapq.heappop(queue)
      c_eff=cur[0]
      x=cur[1]
      y=cur[2]

      if x==r-1 and y==c-1:
         return c_eff

      if heights[x][y]=="":
         continue

      for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
         newx=x+dx
         newy=y+dy
         if 0<newx<r and 0<=newy<c and heights[newx][newy]!="":

            eff = max(c_eff, abs(heights[newx][newy] - heights[x][y]))
            heapq.heappush(queue,(eff, newx, newy))

      heights[x][y]=""

matrix = [[2,3,4],[4,9,5],[6,4,6]]
print(solve(matrix))

输入

[[2,3,4],[4,9,5],[6,4,6]]

输出

1

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程