移动路线问题

tommywong

在4×6矩形框内，取对角线上A,B两点
问：一，从A移动到B有多少条不重复的路线？（每条路线经过的节点不能重复）
二，若将图中的红点去掉，则表示“此路不通”，需要绕道而行。现在要使得从A到B的路线少于原先的二分之一，则至少要去掉几个红点？为什么？

图一：未去掉红点

图二：已去掉部分红点

hbghlyj

用动态规划来解决。但时间复杂度关于$\min(n,m)$为指数级。

abababa

这个是不是考虑减少的路线就行了，比如一个点$(x,y)$，通过这个点的路线应该是有$\binom{x+y}{x}\cdot\binom{10-(x+y)}{6-x}$条路线。然后算出这个的最大值是多少，去掉这个最大值的点，就能去掉最多的线路。
但是我觉得把点A或点B去掉，不就直接满足条件了吗，这行不行呢？

hbghlyj

abababa wrote at 2025-5-25 09:24
把点A或点B去掉，不就直接满足条件了吗

去掉任意$n$个点后，从A到B的路线都少于原先的1/2，则$n$至少为？

abababa

hbghlyj 发表于 2025-5-25 18:59
去掉任意$n$个点后，从A到B的路线都少于原先的1/2，则$n$至少为？

任意n个就是求那个乘积的最小值吧，不够就一直往上加，直到达到1/2。

Aluminiumor

abababa 发表于 2025-5-25 16:24
通过这个点的路线应该是有$\binom{x+y}{x}\cdot\binom{10-(x+y)}{6-x}$条

你这样考虑对应的是只能向上和向右走，但题目没有限定

Aluminiumor

问题并没有限制只能向上和向右走，那么问题一的答案也没那么简单（不是 $C_{10}^4$）

abababa

Aluminiumor 发表于 2025-5-25 19:30
问题并没有限制只能向上和向右走，那么问题一的答案也没那么简单（不是 $C_{10}^4$） ...

我觉得应该有限制才行吧，如果不限制的话，那就在一小段里多次重复，重复的次数不同，就算不同的路线了，这就没意义了。

Aluminiumor

abababa 发表于 2025-5-25 19:51
我觉得应该有限制才行吧，如果不限制的话，那就在一小段里多次重复，重复的次数不同，就算不同的路线了， ...

题目有限制不能重复经过节点

Aluminiumor

1. def count_paths():
2.     max_x = 6
3.     max_y = 4
5.     start = (0, 0)
6.     end = (6, 4)
8.     # 记录哪些点已经被访问过
9.     visited = [[False for _ in range(max_y + 1)] for _ in range(max_x + 1)]
11.     # 检查点是否在网格内且未被访问
12.     def is_valid(x, y):
13.         return 0 <= x <= max_x and 0 <= y <= max_y and not visited[x][y]
15.     directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
17.     def backtrack(current_x, current_y):
18.         if (current_x, current_y) == end:
19.             return 1
20.         count = 0
21.         for dx, dy in directions:
22.             next_x, next_y = current_x + dx, current_y + dy
23.             if is_valid(next_x, next_y):
24.                 visited[next_x][next_y] = True
25.                 count += backtrack(next_x, next_y)
26.                 visited[next_x][next_y] = False
27.         return count
29.     visited[start[0]][start[1]] = True
30.     total_paths = backtrack(start[0], start[1])
31.     return total_paths
34. print(count_paths())

Copy the Code

写了一段 Python 代码，输出 752061