通过矩阵的最优路径需要考虑多个成本
Optimal path through a matrix with multiple costs to consider
例如给定以下矩阵:
[[[0, 8], [0, 3], [0, 8]],
[[8, 0], [3, 0], [0, 5]],
[[0, 1], [0, 6], [0, 0]]]
其中每个元组的第一个数字是食物,第二个数字是水。我需要从右下角到左上角只能向上或向左移动
我需要尽可能多地收集食物和水,这样我才能活得尽可能久。对于我想要生存的每一天,我需要 1 份食物和 1 份水,所以如果我可以在导致 (7,4) 的路径和导致 (6,6) 的路径之间做出选择,正确的选择是 (6,6 ) 因为这样我还能活 6 天。
如何找到通过所述矩阵的最佳路径?
我当前的代码在下面但是它不起作用(它找到了一个非常高成本的路径但不是最高的)我不知道如何去做。我不知道如何开始实施它,尽管有人告诉我要避免递归。
def maxSuppliesPath(matrix):
n = len(matrix) - 1
bestPath = matrix
# Initialize first column of bestPath array
for i in range(1, n + 1):
if bestPath[i][0] == 0:
bestPath[i][0] = bestPath[i - 1][0]
else:
bestPath[i][0] = (bestPath[i][0][0] + bestPath[i - 1][0][0], bestPath[i][0][1] + bestPath[i - 1][0][1])
# Initialize first row of bestPath array
for j in range(1, n + 1):
if bestPath[0][j] == 0:
bestPath[0][j] = bestPath[0][j - 1]
else:
bestPath[0][j] = (bestPath[0][j - 1][0] + bestPath[0][j][0], bestPath[0][j - 1][1] + bestPath[0][j][1])
# Construct rest of the bestPath array
for i in range(1, n + 1):
for j in range(1, n + 1):
if min(bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1]) > min(
bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1]):
bestPath[i][j] = (bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1])
else:
bestPath[i][j] = (bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1])
return min(bestPath[n][n][0], bestPath[n][n][1])
解决问题的第一步是了解如何遍历矩阵。下图显示了从起点到其他点的距离。
注意等距点排列在对角线上。给定一个代表一条对角线的 set
(称为 A),找到下一条对角线上的点(称为 B)如下:
for each point in set A
if the x coordinate is greater than zero
add (x-1, y) to set B
if the y coordinate is greater than zero
add (x, y-1) to set B
在示例中,表示对角线的集合应如下所示:
[(2, 2)] // starting position
[(1, 2), (2, 1)] // after 1 move
[(2, 0), (1, 1), (0, 2)] // after 2 moves
[(0, 1), (1, 0)] // after 3 moves
[(0, 0)] // after 4 moves
下图显示了可以使用多少条不同的路径到达矩阵中的每个点。路径数量与Pascal's triangle中的数量相同。对于这个问题的目的,唯一重要的是数字增长很快,所以我们需要减少数量。
为了减少路径数,我们需要在遍历矩阵时剔除非生产性路径。这是通过比较元组来实现的,其中每个元组由食物和水组成。元组 (F,W)
支配元组 (f,w)
当且仅当 F >= f
AND W >= w
。
例如,考虑矩阵中的中心位置。我们可以通过先向上然后向左移动,或者先向左然后向上移动来到达那个点。先上后左移动产量(食物、水)为 (3,5),而先左后上移动产量 (3,6)。 (3,6) 支配(3,5),所以我们只需要考虑(3,6)。所以在两步之后,我们有如下所示的情况。请注意,我们在中心位置只有 1 个元组,而不是 Pascal 三角形预测的两个元组。
三步走后,出现下图的情况。第三条对角线上的每个点都有两个元组。这是必要的,因为一个元组有更多的食物而另一个元组有更多的水,所以两者都不支配另一个。
四步之后,我们有四个可能的答案,选择最佳答案是比较 min(food, water)
每个元组的简单问题。
例如给定以下矩阵:
[[[0, 8], [0, 3], [0, 8]],
[[8, 0], [3, 0], [0, 5]],
[[0, 1], [0, 6], [0, 0]]]
其中每个元组的第一个数字是食物,第二个数字是水。我需要从右下角到左上角只能向上或向左移动
我需要尽可能多地收集食物和水,这样我才能活得尽可能久。对于我想要生存的每一天,我需要 1 份食物和 1 份水,所以如果我可以在导致 (7,4) 的路径和导致 (6,6) 的路径之间做出选择,正确的选择是 (6,6 ) 因为这样我还能活 6 天。
如何找到通过所述矩阵的最佳路径?
我当前的代码在下面但是它不起作用(它找到了一个非常高成本的路径但不是最高的)我不知道如何去做。我不知道如何开始实施它,尽管有人告诉我要避免递归。
def maxSuppliesPath(matrix):
n = len(matrix) - 1
bestPath = matrix
# Initialize first column of bestPath array
for i in range(1, n + 1):
if bestPath[i][0] == 0:
bestPath[i][0] = bestPath[i - 1][0]
else:
bestPath[i][0] = (bestPath[i][0][0] + bestPath[i - 1][0][0], bestPath[i][0][1] + bestPath[i - 1][0][1])
# Initialize first row of bestPath array
for j in range(1, n + 1):
if bestPath[0][j] == 0:
bestPath[0][j] = bestPath[0][j - 1]
else:
bestPath[0][j] = (bestPath[0][j - 1][0] + bestPath[0][j][0], bestPath[0][j - 1][1] + bestPath[0][j][1])
# Construct rest of the bestPath array
for i in range(1, n + 1):
for j in range(1, n + 1):
if min(bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1]) > min(
bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1]):
bestPath[i][j] = (bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1])
else:
bestPath[i][j] = (bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1])
return min(bestPath[n][n][0], bestPath[n][n][1])
解决问题的第一步是了解如何遍历矩阵。下图显示了从起点到其他点的距离。
注意等距点排列在对角线上。给定一个代表一条对角线的 set
(称为 A),找到下一条对角线上的点(称为 B)如下:
for each point in set A
if the x coordinate is greater than zero
add (x-1, y) to set B
if the y coordinate is greater than zero
add (x, y-1) to set B
在示例中,表示对角线的集合应如下所示:
[(2, 2)] // starting position
[(1, 2), (2, 1)] // after 1 move
[(2, 0), (1, 1), (0, 2)] // after 2 moves
[(0, 1), (1, 0)] // after 3 moves
[(0, 0)] // after 4 moves
下图显示了可以使用多少条不同的路径到达矩阵中的每个点。路径数量与Pascal's triangle中的数量相同。对于这个问题的目的,唯一重要的是数字增长很快,所以我们需要减少数量。
为了减少路径数,我们需要在遍历矩阵时剔除非生产性路径。这是通过比较元组来实现的,其中每个元组由食物和水组成。元组 (F,W)
支配元组 (f,w)
当且仅当 F >= f
AND W >= w
。
例如,考虑矩阵中的中心位置。我们可以通过先向上然后向左移动,或者先向左然后向上移动来到达那个点。先上后左移动产量(食物、水)为 (3,5),而先左后上移动产量 (3,6)。 (3,6) 支配(3,5),所以我们只需要考虑(3,6)。所以在两步之后,我们有如下所示的情况。请注意,我们在中心位置只有 1 个元组,而不是 Pascal 三角形预测的两个元组。
三步走后,出现下图的情况。第三条对角线上的每个点都有两个元组。这是必要的,因为一个元组有更多的食物而另一个元组有更多的水,所以两者都不支配另一个。
四步之后,我们有四个可能的答案,选择最佳答案是比较 min(food, water)
每个元组的简单问题。