knap19 search analysis
======================

Topic: independent-move reordering (search advisor B4), 2026-10-15.
Spec: probs/problem-knap19.lisp (original), probs/problem-knap19-1.lisp (ascending puts, tree search).

Question
--------
How many knapsack states are reached by more than one order of the same puts, and does a
canonical order for independent moves pay, here and on larger instances?

Analytic check (independent Python enumeration, outside Wouldwork)
-------------------------------------------------------------------
Distinct packings (subsets within capacity):
  knap19  36,326  (equals the recorded unpruned program cycles)
  knap30  13,053  (equals the recorded unpruned program cycles)
Reached by more than one order (2 or more items): knap19 36,308 of 36,326; knap30 13,022 of 13,053.
Successors generated by graph search with unordered puts (each packing of k items is
generated once from each of its k parents): knap19 231,158; knap30 81,685 (6.4 and 6.3 times
the distinct packings).
Tree search with unordered puts would follow every order: about 1.53 billion paths (knap19),
143 million (knap30).
With puts in ascending item order: one successor per packing (36,325 and 13,052).

Generalization: the waste factor is the average number of items in a reachable packing, so it
grows with the capacity relative to item weights.  It applies to any action that chooses
members of a set (an assignment by subset).

Independence argument (soundness)
---------------------------------
Two puts of different items commute: the final contents, load and worth are the same in either
order, and if both orders end within capacity, every intermediate load is within capacity too
(loads only grow).  So every packing is reachable by packing its items in ascending number,
and restricting put to items numbered above the largest packed item loses no packing.  The
bound already counts only items above the largest packed one (ordered completions), so it is
consistent with this order.

Change (problem-knap19-1.lisp)
------------------------------
- put: precondition requires the item to be numbered above the largest packed item; the
  effect appends it to contents.  The in relation, read only by the old precondition, removed.
- *tree-or-graph* tree: each packing has one path, so no closed table is needed.

Measurements (Linux VM on the user's PC, SBCL 2.6.9, serial unless noted)
-------------------------------------------------------------------------
                               knap19 (graph)     knap19-1 (tree)
With bound:     program cycles       432               432
                states processed     456               432
Without bound:  program cycles    36,326            36,326
                states processed 231,159            36,326
                elapsed            0.3 s             0.1 s
Best packing: items 3 5 6 9 11, load 30,996, worth 12,248, in all runs.
knap19-1 at 16 threads (VM, and the user's REPL): with bound 95 program cycles (the states
expanded while splitting into tasks are not counted), 645 states processed, worth 12,248;
without bound 36,326 program cycles, worth 12,248.

Forms (unbound comparison):
  (stage knap19-1)
  (ww-set *threads* 0)
  (solve)
  (fmakunbound 'bounding-function?)
  (solve)

Conclusion
----------
The canonical order is sound and removes all duplicate successors (6.4 times fewer generated
without the bound) and the closed table.  With knap19's strong bound the saving is small
(24 states), since the bound already assumed the order; it matters where the bound prunes
little (knap30: factor of 2) and as packings grow larger.  The general engine version
(sleep sets over each action's read and write facts) remains proposed.

2026-11-10  Consolidation
-------------------------
problem-knap19-1.lisp (ascending puts, tree search) replaced problem-knap19.lisp under the
name knap19; the unordered graph-search spec was retired.  The knap19-1 runs above are now
knap19.  (test) still finds worth 12,248 with items 3 5 6 9 11; its recorded final state was
updated because the in relation no longer exists.
