FDRS / FCSR Classical Cube Foundations IV

從狀態圖到搜尋：BFS、雙向搜尋、A* 與 IDA* 的統一語義

英文題名： From State Graphs to Search: A Unified Semantics for BFS, Bidirectional Search, A*, and IDA*
系列： FDRS / FCSR Classical Cube Foundations
系列編號： EML-FDRS-FCSR-CUBE-04
版本： v0.1
日期： 2026-08-20
作者： Neo.K
機構： 一言諾科技有限公司（EveMissLab）
狀態： Orthodox Origin Continuation / 經典地基第四篇

摘要

前三篇已分別建立 FCSR 的表示語義、標準 $3\times3\times3$ 魔方的合法狀態空間，以及 Facelet、Cubie、Permutation 與 Coordinate representation 的區別。本文進入真正的搜尋層：不再問「狀態如何表示」，而問「在給定表示與 move semantics 下，計算機如何系統性地尋找一條從起始狀態到目標狀態的路徑」。

本文提出一個統一的 Search Problem Contract：

\mathcal{Q} = (X,A,T,G,c,h),

其中 $X$ 為搜尋節點空間， $A$ 為可用操作集合， $T$ 為轉移函數， $G$ 為目標判定， $c$ 為邊成本， $h$ 為可選 heuristic。重要的是， $X$ 不必等於完整 canonical state space；它可以是 full cubie state、完整 coordinate tuple、phase coordinate space、quotient graph 或其他對當前任務 sufficient 的表示。

在此統一語義下，本文比較 Breadth-First Search、Bidirectional Search、A* 與 IDA*。BFS 在單位邊成本下可找到最短步數解，但 frontier 與 visited set 通常造成指數級記憶體需求。雙向搜尋同時從起點與目標端擴張；在規則、可逆、近似均衡的搜尋樹中，其理想節點量可由約 $b^d$ 降為約 $2b^{d/2}$ ，但一般圖上的交會偵測、終止條件與兩側成本一致性不能被忽略。A* 以

f(n)=g(n)+h(n)

排序 frontier；若 heuristic 為 admissible，並在 graph-search 情況下正確處理重開或採用 consistency 等足夠條件，可保持最短路徑保證。IDA* 則以逐輪增加的 $f$ -threshold 執行 depth-first search，把 A* 的 heuristic 邊界與 depth-first 的低記憶體特性結合起來。

本文特別將 2026 年既有 FDRS 魔方網頁 Demo 重新定位：其 permutation engine、粗略 piece-count lower bound 與 IDA* 已構成 search proof-of-concept，但 node cap、有限 scramble depth 與 demo-oriented fallback 使它不應被視為全域 completeness 或 optimality 證明。新版 Search Kernel 將拆除這些語義混淆，把「搜尋器是否找得到解」、「找到的解是否最短」、「因資源上限中止」與「heuristic 是否可證 admissible」分開報告。

本文最後提出 Search Trace 作為新版可視化的第一級資料：frontier size、expanded nodes、generated nodes、duplicate hits、threshold、 $g/h/f$ 、pruned branches、meeting state 與 solution certificate 都應可被同步觀察。如此 FCSR 從「看魔方如何展平」進一步升級為「看計算機如何在狀態空間中移動」。

關鍵詞： BFS、bidirectional search、A*、IDA*、state graph、heuristic search、frontier、optimality、FCSR、FDRS、search visualization

1. 從表示問題進入搜尋問題

前三篇形成：

\text{Canonical State} \rightarrow \text{Legal State} \rightarrow \text{Representation}.

但 representation 本身不會自動產生解。

令起始狀態為：

s_0,

目標狀態為：

s_\star.

solver 的核心任務仍然是找一條 move sequence：

p=(a_1,\ldots,a_k)

使：

T^\ast(s_0,p)=s_\star.

若追求最短解，還需最小化：

C(p) = \sum_{i=1}^{k}c(a_i).

因此求解本質上是一個最短路徑／狀態空間搜尋問題。

2. Search Problem Contract

定義：

\mathcal{Q} = (X,A,T,G,c,h),

其中：

$X$ ：搜尋器實際操作的節點空間；
$A(x)$ ：狀態 $x$ 可採取的動作；
$T(x,a)$ ：轉移函數；
$G(x)$ ：goal predicate；
$c(x,a,x')\geq0$ ：轉移成本；
$h(x)\geq0$ ：可選 heuristic。

對經典 HTM 魔方，可令每個合法 face move 成本：

c=1.

若搜尋完整 canonical state：

X = \mathcal{S}_{\mathrm{legal}}.

若搜尋 phase coordinate：

X = \mathcal{X}_{\mathrm{phase}}.

這直接承接第三篇的核心要求：

談搜尋演算法之前，必須先說明搜尋器到底在哪個 representation / quotient graph 上運作。

3. State graph 與 search tree 必須區分

Search problem 誘導一張有向圖：

\Gamma_{\mathcal{Q}} = (V,E),

其中：

V=X,

且：

(x,x')\in E

若存在：

a\in A(x)

使：

T(x,a)=x'.

但實際搜尋過程通常形成一棵或多棵 search tree。

同一個 graph state 可以透過不同 move sequences 重複到達，因此：

\text{search node} \neq \text{unique state}.

這個區別非常重要。

如果完全不做 duplicate detection，搜尋器可能反覆探索：

x \rightarrow y \rightarrow x \rightarrow y \rightarrow \cdots

魔方尤其如此，因為每個 move 都可逆。

因此應區分：

\text{Tree Search}

與：

\text{Graph Search}.

4. Branching factor 不是固定的「18」

若 move alphabet 使用：

\mathcal{A}_{18}

則 root 最多有 $18$ 個直接 successors。

但實際 branching factor 取決於 pruning policy。

例如連續在同一 face 上操作：

R,R

可以合併為：

R^2,

而：

R,R'

直接抵消。

所以搜尋器常禁止：

\text{same-face immediate repetition}.

對互相可交換的 opposite faces，還可建立 canonical ordering 以移除重複序列。

因此我們定義：

b_{\mathrm{raw}} = |A|,

以及：

b_{\mathrm{eff}} = \text{search policy 下的平均有效分支數}.

後續所有複雜度估計如果使用：

b,

都必須說明它是理想模型、raw branching 或 empirical effective branching。

5. Breadth-First Search

BFS 在單位邊成本圖中按照深度逐層擴張：

L_0,L_1,L_2,\ldots

其中：

L_d = \{x:d(s_0,x)=d\}.

在標準 graph-search 版本中，BFS 維護：

FIFO frontier；
visited set；
parent / move metadata。

若所有 move cost 為 $1$ ，第一次依 BFS 層序確定 goal 時即可得到最短 move-count solution。

所以在有限、unit-cost reachable graph 與正確 duplicate handling 下：

\boxed{ \text{BFS is complete and optimal}. }

6. BFS 的根本瓶頸是 frontier memory

對近似均勻、branching factor 為 $b$ 、最短解深度為 $d$ 的 tree model，節點量級為：

1+b+b^2+\cdots+b^d = O(b^d).

BFS 不只需要生成這些節點，還必須保存大量 frontier / visited information。

因此其空間成本同樣可達：

O(b^d).

這對魔方這種高 branching、解深可達數十步的問題非常不利。

所以：

\text{BFS optimality}

並不等於：

\text{BFS practicality}.

7. Bidirectional Search

若 move 是可逆的，則可以同時搜尋：

s_0 \rightarrow \cdots

與：

s_\star \rightarrow \cdots

並尋找：

F_{\mathrm{forward}} \cap F_{\mathrm{backward}} \neq \varnothing.

若交會於狀態 $m$ ，可將：

s_0 \rightsquigarrow m

與：

m \rightsquigarrow s_\star

拼接成完整解。

對均勻樹的理想模型，單向 BFS 約探索：

O(b^d),

而兩側各探索至約：

d/2

時，總量可近似：

O(2b^{d/2}).

這是 bidirectional search 最直觀的平方根深度效應。

8. 雙向搜尋不是「兩個 BFS 就一定更好」

實際圖搜尋還存在幾個問題：

8.1 Meeting test

必須有效判斷：

x\in V_f\cap V_b.

8.2 Frontier imbalance

若一側分支明顯更大，固定交替擴張可能浪費工作。

8.3 Goal representation

若 goal 是一個 subgroup 或 equivalence class，backward side 不是單一節點。

8.4 Weighted edges

若成本不全為 $1$ ，第一次 frontier 相遇不一定保證全域最短。

8.5 Memory

雙向 BFS 仍然需要保存兩側 visited/frontier。

所以：

\boxed{ \text{bidirectional} \neq \text{memory-free}. }

9. A*：把 domain knowledge 放進搜尋順序

A* 對 node $n$ 定義：

f(n) = g(n)+h(n),

其中：

g(n) = \text{起點到 }n\text{ 的已知成本},

h(n) = \text{從 }n\text{ 到 goal 的估計成本}.

A* 每次優先擴張 frontier 中最小 $f$ 的節點。

若：

h(n)=0,

A* 退化為 uniform-cost search；在 unit-cost 情況下即回到按最短已知深度擴張的搜尋。

10. Admissibility 與 consistency

heuristic 稱為 admissible，若：

0 \leq h(n) \leq h^\ast(n),

其中：

h^\ast(n) = d(n,G)

是真實剩餘最短成本。

也就是：

h

永遠不能高估剩餘距離。

對 graph search，若 heuristic 進一步滿足 consistency：

h(n) \leq c(n,n')+h(n'),

則 $f$ 沿路徑具有單調性，closed-node handling 可以更簡潔。

若 heuristic admissible 但 inconsistent，仍可透過允許更佳 $g$ 值觸發 reopen 等正確機制維持 optimality。

因此不能把：

\text{admissible heuristic}

單獨等同於：

\text{任意 A* 程式必然 optimal}.

11. A* 的時間－空間張力

A* 的優勢是：

h

能把搜尋集中到較有希望的區域。

但 best-first search 需要保存 frontier，通常還要保存 closed set 與 $g$ 資訊。

對大型隱式狀態空間，實際限制常常不是單次 move 計算，而是 frontier memory。

因此：

\boxed{ \text{A* solves ordering well, but may lose on memory}. }

這導向 IDA*。

12. IDA：把 A 的 $f$ 邊界放進 depth-first search

IDA* 同樣使用：

f(n) = g(n)+h(n).

但不維護全域 priority queue。

它選擇 threshold：

\theta,

進行 depth-first search，只展開：

f(n) \leq \theta

的節點。

若未找到 goal，下一輪把 threshold 提升到上一輪所有超界值中的最小值：

\theta' = \min\{f(n):f(n)>\theta\}.

因此形成：

\theta_0 < \theta_1 < \theta_2 < \cdots.

13. IDA* 的核心交換：重算換記憶體

A* 傾向：

\text{expand once} + \text{store many}.

IDA* 傾向：

\text{re-expand across iterations} + \text{store one DFS path}.

若最大搜尋深度為 $d$ ，純 DFS recursion stack 為：

O(d).

因此在狀態空間巨大、解深相對有限的 puzzle 中，IDA* 常比保存整個 best-first frontier 更可行。

Korf 1985 的 iterative-deepening 工作正是這種 time / space / solution-cost tradeoff 的經典基線。

14. IDA* 的 optimality 與 pruning safety

在 nonnegative edge cost 且 heuristic admissible 的標準設定中，IDA* 以：

f=g+h

threshold 遞增。

若：

g(n)+h(n)>\theta,

因：

h(n)\leq h^\ast(n),

可得所有經過 $n$ 的 goal path 成本至少為：

g(n)+h^\ast(n) \geq g(n)+h(n) > \theta.

因此該 subtree 不可能包含總成本不超過 $\theta$ 的解，可以安全剪枝。

這就是 IDA* 最值得形式驗證的核心命題之一。

15. IDA* 不自動等於「快」

若：

h(n)=0,

IDA* 接近普通 iterative deepening。

若：

h(n)

接近：

h^\ast(n),

大量 subtrees 可以在淺層被剪掉。

所以性能真正取決於：

\text{representation} + \text{heuristic} + \text{move pruning} + \text{node ordering} + \text{duplicate handling}.

這延續第三篇：

P = F(R,H,A,\text{precomputation},\text{hardware}).

16. 原始 FDRS Demo 的 IDA* 重新定位

既有 HTML Demo 已包含：

permutation-based state engine；
$18$ 個 move variants；
piece-based heuristic；
IDA*；
node cap；
scramble / solve FSM。

其 heuristic 可概括為：

h_c(s) = \left\lceil \frac{N_c^{\mathrm{wrong}}}{4} \right\rceil,

h_e(s) = \left\lceil \frac{N_e^{\mathrm{wrong}}}{4} \right\rceil,

再取：

h(s) = \max(h_c(s),h_e(s)).

直覺是：一個 face move最多直接改變四個 corners 與四個 edges，因此若仍有 $k$ 個完全未歸位 pieces，至少需要約：

\left\lceil k/4\right\rceil

次 move 才可能全部修正。

這是一個非常粗的 lower bound，但適合作為 Demo heuristic。

17. Demo heuristic 的可證明性要求

若要把上述 heuristic 升級成正式 solver component，需證：

h(s) \leq h^\ast(s).

對：

h_c

需要證明任意單步 face move 最多能使四個原本 incorrect corners 變為 correct。

對：

h_e

同理。

若：

h_c \leq h^\ast

且：

h_e \leq h^\ast,

則：

\max(h_c,h_e) \leq h^\ast.

因此：

h

admissible。

這將成為第五篇可直接形式化的第一個簡單 heuristic theorem。

18. 為什麼舊 Demo 不能直接宣稱 complete

舊 Demo 設定：

\text{NODE\_CAP} = 2.2\times10^6.

若節點數超過上限，search 會中止。

此外 solver 的最大 bound 受 scramble depth 附近的範圍限制，且 planning failure 時會 fallback reset。

因此程式層真正語義是：

\boxed{ \text{bounded demonstration solver}. }

而不是：

\forall s\in\mathcal{S}_{\mathrm{legal}}, \exists p: \operatorname{Solve}(s)=p.

19. Search status 與 solver correctness 必須分離

新版 API 至少應區分：

Solved(path)
Exhausted
BoundExceeded
ResourceLimit
Cancelled
InvalidState
InternalError

Solved

必須滿足：

T^\ast(s_0,p)=s_\star.

Exhausted

只有當有限 search domain 已完整展開且無 goal，才能宣稱該 domain 中不存在解。

BoundExceeded

只代表目前 cost / depth bound 內沒找到。

ResourceLimit

只代表計算被 time / memory / node cap 中止。

因此：

\boxed{ \text{not found} \neq \text{no solution}. }

20. 統一四種演算法的核心差異

在同一個：

\mathcal{Q} = (X,A,T,G,c,h)

下，四種算法主要差在 frontier policy 與記憶體策略。

BFS

對 unit cost：

\text{priority}(n) = g(n).

Bidirectional BFS

維護：

F_f,F_b

兩個 frontier，尋找 intersection。

A*

\text{priority}(n) = g(n)+h(n).

IDA*

不用全域 priority queue，而把：

g+h

變成 DFS threshold。

所以它們都是：

\boxed{ \text{如何安排狀態空間探索順序與記憶體} }

的不同答案。

21. 搜尋算法的比較維度

本文不以單一秒數比較算法。

定義 search profile：

\mathbf{P} = (N_{\mathrm{gen}}, N_{\mathrm{exp}}, N_{\mathrm{dup}}, M_{\mathrm{peak}}, D_{\mathrm{sol}}, C_{\mathrm{sol}}, T_{\mathrm{wall}}).

其中：

$N_{\mathrm{gen}}$ ：generated nodes；
$N_{\mathrm{exp}}$ ：expanded nodes；
$N_{\mathrm{dup}}$ ：duplicate hits；
$M_{\mathrm{peak}}$ ：peak memory；
$D_{\mathrm{sol}}$ ：solution depth；
$C_{\mathrm{sol}}$ ：solution cost；
$T_{\mathrm{wall}}$ ：wall-clock time。

若使用 heuristic，再增加：

N_{\mathrm{prune}},

以及 threshold history：

(\theta_0,\theta_1,\ldots).

22. Search Trace 應成為可視化第一級物件

新版 FCSR 不只畫最後 solution path。

SearchTrace 應保存事件：

SearchStarted
NodeGenerated
NodeExpanded
DuplicateDetected
HeuristicEvaluated
NodePruned
ThresholdRaised
FrontiersMet
GoalFound
SearchStopped

每個事件可以帶：

stateRef
representationRef
move
g
h
f
depth
parent
reason
step

這樣 UI 可以真正播放：

\boxed{ \text{計算機如何找解}. }

23. 四種可視化模式

23.1 BFS Layer View

顯示：

L_0,L_1,L_2,\ldots

以及每層節點量。

23.2 Bidirectional Meeting View

顯示：

F_f

與：

F_b

如何逐漸接近並交會。

23.3 A* Frontier View

顯示 frontier 上：

g,h,f

分布，以及下一個被 pop 的節點。

23.4 IDA* Threshold View

顯示：

\theta_0 \rightarrow \theta_1 \rightarrow \cdots

以及每一輪被：

f>\theta

剪掉多少節點。

24. Search graph 也可以是 quotient graph

第三篇已指出 coordinate：

R: \mathcal{S} \rightarrow X

可能不是 injective。

若 move-compatible：

R(T(s,a)) = M_a(R(s)),

就可以直接在：

X

上建立 quotient search graph。

因此同一個 cube problem 可以有：

\Gamma_{\mathrm{full}},

\Gamma_{\mathrm{coord}},

\Gamma_{\mathrm{sym}},

\Gamma_{\mathrm{phase}}.

它們的節點數、branching、goal set 與 heuristic 可能完全不同。

所以：

\boxed{ \text{搜尋算法不能脫離搜尋圖談性能}. }

25. FDRS 的新計算命題：表示改變搜尋拓樸

令：

R: \Gamma \rightarrow \Gamma_R.

representation / quotient 可能改變：

節點 cardinality；
多狀態等價類；
goal geometry；
heuristic 可計算性；
effective depth；
duplicate structure；
symmetry structure。

因此可以研究：

C_{\mathrm{search}}(\Gamma_R,A)

隨 representation $R$ 如何變化。

形成可測量命題：

\boxed{ R_1,R_2 \Rightarrow C_{\mathrm{search}}(R_1) \neq C_{\mathrm{search}}(R_2) }

在具體問題上是否成立，必須由實驗或定理驗證，而不能預設「降維必然加速」。

26. 演算法選擇不是固定答案

對小深度：

\text{BFS}

可能最簡單。

若 goal 唯一且轉移高度可逆：

\text{bidirectional}

可能有明顯優勢。

若有強 heuristic 且 memory 足夠：

\text{A*}

可能極有效。

若有強 admissible heuristic 但 frontier 太大：

\text{IDA*}

常更適合。

所以系統不應內建：

IDA* 永遠最好。

真正的設計是：

\operatorname{ChooseSearch} ( R, h, M_{\max}, C_{\mathrm{goal}}, \text{optimality requirement} ).

27. 形式驗證目標：Search Kernel

S1. Path replay semantics

\operatorname{applyPath}(s,[]) = s.

\operatorname{applyPath}(s,a::p) = \operatorname{applyPath}(T(s,a),p).

S2. BFS depth correctness

對 unit-cost graph，在正確 visited semantics 下：

\operatorname{BFS}(s)=p \Rightarrow |p| = d(s,G).

S3. Bidirectional path composition

若：

p_f:s\rightsquigarrow m

與：

p_b:G\rightsquigarrow m,

且 moves 可逆，則：

p_f \mathbin{+\!\!+} \operatorname{reverseInverse}(p_b)

為合法 solution path。

S4. A* lower-bound theorem

若：

h\leq h^\ast

並滿足所採 graph-search correctness 條件，則確定的 goal path 為 optimal。

S5. IDA* pruning safety

若：

h\leq h^\ast

且：

g(n)+h(n)>\theta,

則不存在總成本：

\leq\theta

且經過 $n$ 的 goal path。

28. 搜尋與證明應分層

即使未來某個高速 solver 沒有完整形式化，仍可以把：

\text{Search}

與：

\text{Check}

分開。

Searcher 回傳：

p.

Verified checker 只需計算：

T^\ast(s_0,p)

並確認：

T^\ast(s_0,p)=s_\star.

因此：

\boxed{ \text{untrusted search} + \text{trusted certificate checker} }

可以先提供 soundness。

optimality certificate 則更困難，因為還需要證明不存在更短 path。

29. 本文核心命題

命題 S1：搜尋問題必須綁定搜尋表示

\mathcal{Q} = (X,A,T,G,c,h).

命題 S2：搜尋圖與搜尋樹不同

duplicate path 不等於新 state。

命題 S3：BFS 的主要代價是 frontier memory

最短性保證不代表在巨大狀態域上實用。

命題 S4：Bidirectional search 改變有效搜尋深度

但 meeting、termination 與 memory 仍需明確處理。

命題 S5：A* 的核心是 $g+h$ frontier ordering

f=g+h.

命題 S6：IDA* 用重複計算換取低記憶體

\text{best-first bound} + \text{depth-first traversal}.

命題 S7：Algorithm performance 不是 algorithm name 的函數

P = F( \text{representation}, \text{heuristic}, \text{search policy}, \text{precomputation}, \text{hardware} ).

30. 結論

本文完成 FDRS/FCSR 經典魔方線從「表示」到「搜尋」的第一次正式跨越。

前三篇建立了：

\text{合法狀態} + \text{表示} + \text{coordinate reduction}.

本文進一步建立：

\boxed{ \text{Search Problem} = (X,A,T,G,c,h). }

BFS、雙向搜尋、A* 與 IDA* 不再被看成四個孤立技巧，而被理解為：

\boxed{ \text{同一狀態空間探索問題的不同 frontier / memory policies}. }

從這一篇開始，任何求解效率宣稱都必須至少附帶：

\text{representation}, \quad \text{move set}, \quad \text{metric}, \quad \text{heuristic}, \quad \text{duplicate policy}, \quad \text{resource bound}.

下一篇將專門處理其中最關鍵、也最能改變搜尋規模的一項：

《啟發式與剪枝：Admissibility、Pattern Database 與搜尋下界》。

參考資料與來源定位

起源與既有實作

[F2026-D] FDRS_展開收斂_同步性.html，FDRS/FCSR permutation engine、piece heuristic、IDA*、FSM 與同步可視化原型。

外部搜尋理論基線

[R1] P. E. Hart, N. J. Nilsson, B. Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics, 1968。
[R2] P. E. Hart, N. J. Nilsson, B. Raphael, Correction to "A Formal Basis for the Heuristic Determination of Minimum-Cost Paths", SIGART Newsletter, 1972。
[R3] Richard E. Korf, Depth-First Iterative-Deepening: An Optimal Admissible Tree Search, Artificial Intelligence 27(1), 1985。
[R4] Ira Pohl, Bi-Directional and Heuristic Search in Path Problems, Stanford Linear Accelerator Center Technical Report / Dissertation, 1969。
[R5] Richard E. Korf, Finding Optimal Solutions to Rubik's Cube Using Pattern Databases, AAAI, 1997。
[R6] Richard E. Korf, Michael Reid, Stefan Edelkamp, Time Complexity of Iterative-Deepening-A*, Artificial Intelligence 129, 2001。
[R7] Herbert Kociemba, The Two-Phase Algorithm 與 Pruning Tables，官方技術說明。

版本註記

v0.1 建立統一 Search Problem Contract，將 BFS、Bidirectional、A*、IDA* 放入同一搜尋語義，並將既有 FDRS Demo 明確定位為 bounded proof-of-concept，而非全域 solver correctness 證明。

後續第五篇：