Iterative broadening in Python
Repeats a search with an increasing breadth limit at each node, so early choices are explored before later ones.
- File
iterative_broadening.py, 57 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/iterative-broadening/. The authors are listed in prov/5WXKC7.jsonl.
import itertools
from collections.abc import Callable, Hashable, Sequence
from typing import Optional, TypeVar
S = TypeVar("S", bound=Hashable)
def iterative_broadening(
start: S,
successors: Callable[[S], Sequence[S]],
is_goal: Callable[[S], bool],
first_cutoff: int = 2,
trace: Optional[list] = None,
) -> Optional[list[S]]:
"""Depth-first search with a breadth cutoff c = first_cutoff, first_cutoff + 1, ...
Precondition: the tree of paths from start is finite (each path ends), and
first_cutoff >= 1. Each run looks only at the first c children of each
node, in the order given by successors. Returns a path [start, ..., goal]
or None when the tree holds no goal. If trace is a list, each goal-tested
state is appended to it.
Cost: at most sum over c of the nodes of the tree cut to breadth c; for a
uniform tree of branching b and depth d, at most (1 + b/(d+1)) b^d fringe
nodes over all runs. Space: O(depth) stack frames.
"""
if first_cutoff < 1:
raise ValueError("the first breadth cutoff must be at least 1")
pruned = False
def bounded(s: S, c: int) -> Optional[list[S]]:
nonlocal pruned
if trace is not None:
trace.append(s)
if is_goal(s): # @line L6
return [s]
children = successors(s) # @line L7
if len(children) > c: # @line L8
pruned = True
for t in children[:c]: # @line L9
r = bounded(t, c) # @line L10
if r is not None: # @line L11
r.append(s)
return r
return None # @line L12
for c in itertools.count(first_cutoff): # @line L1
pruned = False # @line L2
r = bounded(start, c) # @line L3
if r is not None: # @line L4
r.reverse()
return r
if not pruned: # @line L5
return None
return None
test_iterative_broadening.py 100 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/iterative-broadening/. The authors are listed in prov/5WXKC7.jsonl.
import random
import unittest
from iterative_broadening import iterative_broadening
def uniform(b, d):
return lambda s: [s + (i,) for i in range(b)] if len(s) < d else []
def all_nodes(start, successors):
out, stack = [], [start]
while stack:
s = stack.pop()
out.append(s)
stack.extend(successors(s))
return out
class TestPageExample(unittest.TestCase):
goals = {(1, 0, 1), (1, 2, 2), (2, 1, 0)}
def test_broadening(self):
trace: list = []
r = iterative_broadening((), uniform(3, 3), lambda s: s in self.goals, trace=trace)
self.assertEqual(r, [(), (1,), (1, 0), (1, 0, 1)])
self.assertEqual(len(trace), 12)
def test_plain_dfs(self):
trace: list = []
r = iterative_broadening((), uniform(3, 3), lambda s: s in self.goals, first_cutoff=3, trace=trace)
self.assertEqual(r, [(), (1,), (1, 0), (1, 0, 1)])
self.assertEqual(len(trace), 18)
def test_worst_case_table(self):
def n(c, d):
return sum(c**i for i in range(d + 1))
rows = {(3, 3): 55, (4, 7): 25380, (6, 6): 82199, (10, 5): 249627}
for (b, d), total in rows.items():
self.assertEqual(sum(n(c, d) for c in range(2, b + 1)), total)
self.assertLess(sum(c**d for c in range(2, b + 1)), (1 + b / (d + 1)) * b**d)
def test_worst_case_run_count(self):
b, d = 3, 3
last = (2, 2, 2)
trace: list = []
r = iterative_broadening((), uniform(b, d), lambda s: s == last, trace=trace)
self.assertEqual(r[-1], last)
self.assertEqual(len(trace), 15 + 40)
class TestEdgeCases(unittest.TestCase):
def test_start_is_goal(self):
self.assertEqual(iterative_broadening(0, lambda s: [], lambda s: s == 0), [0])
def test_no_goal(self):
trace: list = []
self.assertIsNone(iterative_broadening((), uniform(4, 2), lambda s: False, trace=trace))
self.assertEqual(len(trace), 7 + 13 + 21)
def test_bad_cutoff(self):
with self.assertRaises(ValueError):
iterative_broadening(0, lambda s: [], lambda s: False, first_cutoff=0)
def test_leaf_root_no_goal(self):
self.assertIsNone(iterative_broadening(0, lambda s: [], lambda s: False))
class TestRandom(unittest.TestCase):
def test_random_trees(self):
rng = random.Random(1992)
for trial in range(600):
kids: dict = {}
def build(node, depth):
k = rng.randint(0, 5) if depth < 4 else 0
kids[node] = [node + (i,) for i in range(k)]
for ch in kids[node]:
build(ch, depth + 1)
build((), 0)
nodes = all_nodes((), lambda s: kids[s])
goals = {v for v in nodes if rng.random() < 0.05}
r = iterative_broadening((), lambda s: kids[s], lambda s: s in goals)
if not goals:
self.assertIsNone(r, trial)
else:
self.assertIsNotNone(r, trial)
self.assertEqual(r[0], ())
self.assertIn(r[-1], goals)
for a, b in zip(r, r[1:]):
self.assertIn(b, kids[a])
if __name__ == "__main__":
unittest.main()
What the next level needs
- the tests did not run in this build