通过矩阵的最佳路径需要考虑多种成本 [英] 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(矩阵) - 1最佳路径 = 矩阵# 初始化bestPath数组的第一列对于范围内的 i (1, n + 1):如果 bestPath[i][0] == 0:bestPath[i][0] = bestPath[i - 1][0]别的:bestPath[i][0] = (bestPath[i][0][0] + bestPath[i - 1][0][0], bestPath[i][0][1] + bestPath[i - 1][0][1])# 初始化bestPath数组的第一行对于范围内的 j (1, n + 1):如果最佳路径[0][j] == 0:最佳路径[0][j] = 最佳路径[0][j - 1]别的:bestPath[0][j] = (bestPath[0][j - 1][0] + bestPath[0][j][0], bestPath[0][j - 1][1] + bestPath[0][j][1])# 构造bestPath数组的其余部分对于范围内的 i (1, n + 1):对于范围内的 j (1, n + 1):如果 min(bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1]) >分钟(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])别的:bestPath[i][j] = (bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1])返回 min(bestPath[n][n][0], bestPath[n][n][1])

解决方案

解决问题的第一步是了解如何遍历矩阵.下图显示了从起点到其他点的距离.

注意等距点排列在对角线上.给定一个表示一条对角线的 set(称为 A)，下一条对角线(称为 B)上的点可以按如下方式找到:

对于集合A中的每个点如果 x 坐标大于零将 (x-1, y) 添加到集合 B如果 y 坐标大于零将 (x, y-1) 添加到集合 B

在示例中，表示对角线的集合应如下所示:

[(2, 2)]//起始位置[(1, 2), (2, 1)]//1次移动后[(2, 0), (1, 1), (0, 2)]//2次移动后[(0, 1), (1, 0)]//3次移动后[(0, 0)]//4 次移动后

下图显示了可以使用多少条不同的路径到达矩阵中的每个点.路径数与

为了减少路径数，我们需要在遍历矩阵时剔除非生产性路径.这是通过比较元组来实现的，其中每个元组由食物和水组成.元组 (F,W) 支配元组 (f,w) iff F >= f AND W >=w.

例如，考虑矩阵中的中心位置.我们可以通过先向上再向左移动或先向左移动来达到该点.先向上再向左移动会产生 (3,5) 的(食物、水)，而先向左移动会产生 (3,6).(3,6)支配(3,5)，所以我们只需要考虑(3,6).所以经过两次移动后，我们的情况如下图所示.请注意，我们在中心位置只有 1 个元组，而不是 Pascal 三角形预测的两个元组.

经过三步后，情况如下图.第三对角线上的每个点都有两个元组.这是必要的，因为一个元组有更多的食物，另一个有更多的水，所以两者都不支配另一个.

经过四次移动后，我们有四个可能的答案，选择最佳答案很简单，只需比较每个元组的 min(food, water).

For example given the below matrix:

[[[0, 8], [0, 3], [0, 8]],
 [[8, 0], [3, 0], [0, 5]],
 [[0, 1], [0, 6], [0, 0]]]

where for each tuple the first number is food and the second number is water. I need to get from the bottom right to the top left and I can only move up or left.

I need to gather as much food and water as possible so I can survive as long as possible. For each day I want to survive I need 1 food and 1 water so if I could choose between a path that would result in (7,4) and one that would result in (6,6) the correct choice is (6,6) as that will allow me to live for 6 days.

How does one go about finding the best path through said matrix?

My current code is below however it does not work(it finds a very high cost path but not the highest) and I have no idea how to go about it. I have no idea how to begin implementing it, though I have been told to avoid recursion.

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])

解决方案

The first step in solving the problem is to understand how to traverse the matrix. The image below shows the distance from the starting point to each other point.

Notice that equidistant points are arranged on a diagonal. Given a set (call it A) that represents one diagonal, the points on the next diagonal (call it B) are found as follows:

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

In the example, the sets representing the diagonals should look like this:

[(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

The image below shows how many different paths can be used to reach each point in the matrix. The number of paths is the same as the numbers in Pascal's triangle. For the purposes of this question, the only thing that matters is that the numbers grow quickly, so we need to reduce the count.

To reduce the path count, we need to cull non-productive paths as we traverse the matrix. This is accomplished by comparing tuples, where each tuple consists of food and water. A tuple (F,W) dominates a tuple (f,w) iff F >= f AND W >= w.

For example, consider the center position in the matrix. We can reach that point either by moving up-then-left, or by moving left-then-up. Moving up-then-left yields (food, water) of (3,5), whereas moving left-then-up yields (3,6). (3,6) dominates (3,5), so we only need to consider (3,6). So after two moves, we have the situation shown below. Note that we only have 1 tuple in the center position, rather than the two that Pascal's triangle would predict.

After three moves, we have the situation shown below. We have two tuples for each point on the third diagonal. That's necessary because one of the tuples has more food and the other has more water, so neither dominates the other.

After four moves, we have four possible answers, and choosing the best is a simple matter of comparing min(food, water) for each of the tuples.

这篇关于通过矩阵的最佳路径需要考虑多种成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！