Python 算法题 |如何在连通图中找到欲望权重的路径？

Question

问题

假设你有一个这样的 m * n 矩阵：

Grid = 4 * 4

1 1 1 1    
2 2 2 2    
3 3 3 3    
4 4 4 4

你想从左上角连接到右下角，只能向右或向下。此外，您想找到获得所需总和所需的操作。

例如：

课本中找到的脚本，不清楚

def move(m, n, sum):
  count = m + n - 1
  max_val = m
  s = sum
  r = []
  while max_val > 0:
    if count <= 0:
      return False, r
    least = max_val * ((max_val - 1) / 2)
    r.append(max_val)
    s -= max_val
    count -= 1
    while ((count > 0) and (s > least + (count - (max_val - 1)) * (max_val - 1))):
      r.append(max_val)
      s -= max_val
      count -= 1
    if s < least:
      return False, r
    max_val -= 1
  return True, r


def combine(m, n, sum):
  result, new_res = move(m, n, sum)
  new_res.reverse()
  for i in range(1, len(new_res)):
    if new_res[i] == new_res[i - 1]:
      print("R")
    else:
      print("D")

combine(4, 4, 16)

我不太明白解决方案。

有人可以解释算法吗？

特别是在函数 move 中，它在 while 循环中执行此检查：

while ((count > 0) and (s > least + (count - (max_val - 1)) * (max_val - 1))):

问题

这个算法的名字是什么？
这个脚本是如何工作的？
运行时间（时间复杂度）是多少？

谢谢！

Answer 1

所以脚本写得不好，也没有遵循最佳实践，话说我重新调整了它，希望更清晰

源代码

注意：我已经添加到我的GitHubAlgorithm-Complete-Guide正在建设中，请随意使用它

def move(m, n, weight_limit):

    # ==== < CONFIG VARIABLES > ==== #
    step_counter = m + n - 1
    max_val = m         # NOTE: It starts from the last Value (4) and Goes Backwards
    path = []           # NOTE: Stores the path (need to reverse it afterwards)
    while max_val:
        if step_counter <= 0:   # NOTE: starting Node so it break Not need to return
            break
        least = max_val * ((max_val - 1) / 2)
        path.append(max_val)
        weight_limit -= max_val
        step_counter -= 1
        if weight_limit < least:  # NOTE: Moved it up here because makes more sense to check this first and break
            break
        # ==== < ROW CHECK | CAN IT GO TO THE LEFT? > ==== #
        if step_counter:     # NOTE: Moved it as makes it more clear
            check_row = least + (step_counter - (max_val - 1)) * (max_val - 1)
            while weight_limit > check_row:  # FAQ: 1 Footnotes
                path.append(max_val)
                weight_limit -= max_val
                step_counter -= 1

        max_val -= 1
    return path


def combine(m, n, sum):
    path = move(m, n, sum)
    path.reverse()  # NOTE: Reverse the result Path
    result = []
    for i in range(1, len(path)):
        if path[i] == path[i - 1]:   # NOTE: Check if next Value is the same then it moved it to the Right
            result.append((path[i], 'Right'))
        else:
            result.append((path[i], 'Left'))
    return result


def prettify_result(res):
    for value in res:
        print(f'V={value[0]}) {value[1]} |-> ', end='')


if __name__ == '__main__':
    path = combine(4, 4, 16)
    prettify_result(path)

说明

我首先想到的是 Rat in a Maze problem solved with Backtracking technique of the Algorithm Depth-first_search that runs at Time Complexity: O(2^(n^2)) but after a review I doubt it, and it seems more a kind of Dijkstra's algorithm 但我可能错了。我不认为 Backtracking 简单，因为它不是递归的（并且从不回溯..）但是因为它检查节点的权重，所以它看起来像 Dijkstra 的 具有给定的最大重量。
重要说明，迷宫是颠倒的，从下到上解决的！所以它从值 4 开始向后运行！因此实际上是检查：
- 方向 UP 优先级更高。
- 方向LEFT一直在每一步都检查（我在脚本里留了个大注释），如果走不了（因为成本太高）那就走向上（向上花费少一，因为它是 4、3、2、1）
"function move, what is least + (count - (max_val - 1)) * (max_val - 1)" 这个我有点费解同样，基本上只是一个数学技巧，我将它添加到一个名为 check_row 的变量中以使其更明确，但基本上它会检查是否可以向左移动。
在算法的末尾，它向后反转了列表，因此看起来像是从上到下。

考虑

函数move()return总是2个值，第一个如果False并且存储在变量result中但不是偶数用过的。它很奇怪（似乎没有编程实践）并且无论如何都没有使用所以我只是删除并用 break 语句替换它。这是因为在 while 循环中中断比 return 更有意义。函数然后在最后注意 return path。
我删除了许多针对 0 的 while max_val > 0 或类似的 bool 检查，因为它完全是多余的而不是 Pythonic，如指南 realpython.com/python-conditional-statements/

联机文档

BACKTRACKING

Depth-first search

Dijkstra's algorithm

Python 算法题 |如何在连通图中找到欲望权重的路径？

Python Algorithm Problem | How to find a path of desire weight in a connected graph?

python

algorithm

graph

graph-algorithm

weighted-graph

问题

课本中找到的脚本，不清楚

问题

源代码

说明

考虑

联机文档