After reading both artifacts' source code in detail, here is the explanation:
BFS state-deduplication logic (in runSearch):
const key = nd.left * 2 + (nd.bL ? 1 : 0);
if (closed.has(key) && gBest.get(key) < nd.g) continue;
closed.add(key);
// child added if:
if (!gBest.has(nkey) || gBest.get(nkey) > ng) { ... open.push(c.id) }A child node is generated even for previously-seen states, as long as the new path cost g is lower. This is correct A*-style re-expansion logic — but when astar=false (BFS mode), all g-costs are equal (BFS treats all edges the same), so the de-duplication condition rarely fires. The tree keeps generating new nodes for states that might have been visited by different paths.
Budget: 6,000 steps. The branching factor for 20 entities with k=3 boat capacity is enormous — up to C(20,1)+C(20,2)+C(20,3) ≈ 1,350 moves per state. BFS exhausts 6K nodes almost instantly in the first few depth levels, producing a very wide, flat, never-ending-looking tree.
BFS state-deduplication logic (in runBFS):
if (!vis.has(ns)) {
vis.set(ns, {par:s, grp, dir:side, d:nd});
// only then create a node
}Each state is visited at most once. Once a state is recorded in vis, it is permanently skipped on all future encounters. This is textbook BFS on a graph — it guarantees the shortest path and produces a compact tree where every node is a genuinely new state.
No budget cap (only stops at goal or exp<2,000,000). It explores ~35,000 states and reaches the goal, so the tree terminates naturally and efficiently.
| Artifact 1 (BFS) | Artifact 2 (BFS) | |
|---|---|---|
| State dedup | A*-style: skip only if seen with lower g | Classic: skip if seen at all |
| BFS effect | Same g for all paths → dedup rarely fires → multiple tree nodes per state | Each state visited once → tight tree |
| Budget | 6,000 nodes (hard cap, never reaches goal) | No hard cap, stops at goal (~35K states) |
| Problem size | 20 entities, ~1,350 moves/state | Same 20-person problem |
| Visual result | Explosively wide, flat, "never-ending" | Grows level by level, terminates at goal |
The root cause: Artifact 1 uses a shared runSearch(astar, budget) function designed primarily for A*, where re-expansion of states with better g-values is meaningful. When used as BFS (all costs equal), the guard condition gBest.get(key) > ng almost never triggers, so nearly every reachable state transition creates a new tree node — even if the destination state was already visited. This is not a bug; it's an intentional design that shows how BFS on a 20-entity problem with no tight pruning is computationally intractable, which is precisely the point of the comparison. Artifact 2 is a "Real BFS" implementation that does proper graph-search deduplication, which is why it terminates efficiently.