有很多选择

Содержание и основные понятия

返回目录
第25章 第25.2页
有很多选择
当一个问题没有明智的解决办法时,我们通过截断它来跨越所有选择。
审查各种备选办法
- 这是一个通用的方法: 尝试每一个组合,你可以选择最好的。
全球环境基金,全环基金
PIF 太平洋岛屿论坛
EGE 第12号
01
合并对象类型
对象
公式公式公式
示例示例示例
空格无重复
A(n,k) = n! / (n-k)!
5人中三人坐下
搬迁
P(n) = n!
全部5个都解决
不重复合并
C(n,k) = n! / (k!(n-k)!)
选择5组中的第3组
经常地点
n
k
4位数密码
与重复合并
C(n+k-1, k)
将球放入框中
02
后追寻——返回搜索
Backtracking
- 场外算法:
逐级作出决定,在每一级别选择一种选择。
如果目前的部分选择没有导致一个完整的解决方案,它将倒退,再尝试另一个选项。
他使用搜索树: 根是一个空洞的选择, 叶子是一个完整的解决方案 。
最坏的情况是:O(搜索树叶数),往往指数化。
后履式木柴:3发烧(简化)
每个级别都选择一列。反向 = 返回到前一级。
Q1
Q2
Q2
Q3
Q3
Q3
Q3
X
OK
X
红线=反弹(冲突)、绿线=允许
树长得更大: 每一层是下一个 Q; 如果位置比前几个 Q 强, 树枝就会断裂 。
def n_queens(n, row=0, cols=[], diag1=[], diag2=[]):
if row == n:
print(cols) # одна расстановка: cols[i] = столбец ферзя на строке i
return 1
count = 0
for col in range(n):
if col in cols or (row-col) in diag1 or (row+col) in diag2:
continue # откат — бит, пропускаем
count += n_queens(n, row+1, cols+[col], diag1+[row-col], diag2+[row+col])
return count
print(f"Решений для 8 ферзей: {n_queens(8)}") # 92
# Визуализация:
def print_board(cols):
n = len(cols)
for r in range(n):
row = ['.' if c != cols[r] else 'Q' for c in range(n)]
print(' '.join(row))
print_board([0, 4, 7, 5, 2, 6, 1, 3]) # первое решение
8 Fersei - 比额表
超过648 x 2.8x1014 组合, 削减约15,000个节点(共44亿)。
减少约1 900万倍
我不知道该怎么处理它, 因为反向追踪!
Labyrinth: 搜索返回路径
开始 ~ 结束 。 在每个单元格中, 我们尝试从左到右的邻居。 假的 = 返回( 后行 ) 。
S
A
B
✗
D
E
F
G
H
End
①
②
③
④
⑤
↩
↩
⑥
✓
= 测试,点 = 回溯轨道
路由:S.A.B.O.M.E.I.End(以六步为单位发现),B.C.被丢弃(粗略),E.H.被抛弃(G.H给了最佳路径)。
def solve_maze(maze, start, end):
path = []
visited = set()
def backtrack(pos):
if pos == end:
return True
for row in range(len(maze)):
for col in range(len(maze[row])):
if maze[row][col] == 1 and (row, col) not in visited:
visited.add((row, col))
path.append((row, col))
if backtrack((row, col)):
return True
path.pop() # backtrack
return False
visited.add(start)
path.append(start)
return path if backtrack(start) else []
maze = [[0,1,0,0,0],
[0,1,1,1,0],
[0,0,0,1,0],
[0,0,0,1,0]]
print(solve_maze(maze, (0,1), (3,4)))
# → [(0,1),(0,2),(0,3),(1,3),(2,3),(3,3)]
🧭
Labyrinth:动动后跟踪
N-皇后区:逐步树(4 个皇后,简化)
0级:空。1级:第0栏中的 Q : 第2级: 第1栏的 Q...
∅
[0]
[1]
[0,1]
✗
✗
[1,3]
✗
✓
✗
✗
✗
✓
✗
=空 [0.1] = 女王0 在栏0, 女王1 在栏1 解决方案
分支[0.1]. * [0.1.3? ]已作出决定。 ~99.999999%的分支被切断。
♕
N-Quens:动动后跟踪
🎯
小型试验:5个问题
XP: 0
🧩
主题的快速测试
五个问题,每个正确答案20XP