Guida a Backtracking · 4/6
Per ora questo capitolo è disponibile solo in inglese.
The running time of backtracking boils down to nodes visited times work per node. In the worst case it walks the whole state-space tree, so most problems are exponential or factorial. Pruning cannot change that upper bound, but it can drastically shrink the number of nodes actually visited. This chapter lists the complexity of the classic problems, measures the effect of pruning, and compares backtracking with brute force and dynamic programming (DP).
| Problem | Nodes (or solutions) | Time | Extra space |
|---|---|---|---|
| Subsets | 2^n | O(n · 2^n) | O(n) |
| Permutations | about e · n! | O(n · n!) | O(n) |
| Combinations C(n, k) | C(n, k) solutions | O(k · C(n, k)) | O(k) |
| N-Queens | at most n! | at most O(n!) | O(n) |
| Sudoku with m blanks | at most 9^m | at most O(9^m) | O(m) |
The extra factor n or k in the time column is the cost of copying each solution into the output. The space column counts only the recursion depth and path; the output list needs room for every solution on top of that. The best case depends on the problem. A Sudoku solver that needs a single answer can finish in time proportional to the number of blanks if its first guesses are right, but when every solution must be listed, the number of solutions itself is a lower bound.
Count the nodes the N-Queens search actually visits, and compare with placing a queen in any column of each row (n^n) and with only avoiding repeated columns (n!).
def count_nodes(n):
cols, diag, anti = set(), set(), set()
visited = 0
def place(row):
nonlocal visited
visited += 1
if row == n:
return
for c in range(n):
if c in cols or row - c in diag or row + c in anti:
continue
cols.add(c); diag.add(row - c); anti.add(row + c)
place(row + 1)
cols.remove(c); diag.remove(row - c); anti.remove(row + c)
place(0)
return visited
for n in (4, 8, 12):
print(n, count_nodes(n))| n | Solutions | Nodes visited | n! | n^n |
|---|---|---|---|---|
| 4 | 2 | 17 | 24 | 256 |
| 8 | 92 | 2,057 | 40,320 | 16,777,216 |
| 10 | 724 | 35,539 | 3,628,800 | 10,000,000,000 |
| 12 | 14,200 | 856,189 | 479,001,600 | about 8.9 trillion |
At n = 12 the search visits roughly 0.2% of n! nodes. The bound is the same, but the real amount of work differs by orders of magnitude, and that is what makes backtracking practical.
When looking for subsets that sum to target, sorting the numbers first means that once a number exceeds the remaining sum, every number after it can be skipped too. The key detail is that you can break instead of continue.
def subset_sum(nums, target):
nums = sorted(nums)
result, path = [], []
def dfs(start, remain):
if remain == 0:
result.append(path[:])
return
for i in range(start, len(nums)):
if nums[i] > remain:
break # later numbers are larger: cut them all
path.append(nums[i])
dfs(i + 1, remain - nums[i])
path.pop()
dfs(0, target)
return result
print(subset_sum([8, 2, 6, 3, 5], 11)) # [[2, 3, 6], [3, 8], [5, 6]]| Technique | How it searches | Good fit | Weakness |
|---|---|---|---|
| Brute force | build every candidate, then check | tiny inputs, test oracles | builds invalid candidates in full |
| Backtracking | check while building, undo on failure | listing solutions, constraint problems | worst case still exponential |
| Branch and bound | backtracking plus cut-offs from a bound on the best value | optimization (knapsack, TSP) | needs a good bounding function |
| DP | store answers to overlapping subproblems | counting, minimum or maximum | hard to list every solution |
The right tool depends on the question. To list every subset that sums to target, use backtracking. To ask whether one exists or how many there are, DP answers in O(n · target) and is far faster.
def count_subset_sum(nums, target):
ways = [1] + [0] * target # ways[s] = number of subsets summing to s
for x in nums:
for s in range(target, x - 1, -1):
ways[s] += ways[s - x]
return ways[target]
print(count_subset_sum([8, 2, 6, 3, 5], 11)) # 32^n or n!.
0 commenti
Accedi · Accedi per lasciare un commento.