狀態空間搜尋（state-space search）
/ STAYT-spays surch /
狀態空間搜尋，是AI解決問題的一種根基性方式：把問題看成在一座巨大的「可能性迷宮」裡尋找一條路徑。你可能身處的每一種局面都是一個「狀態」；你能採取的每一步移動，都把你從一個狀態帶到另一個；而解決問題，就是找出一串從「起點」到「你想去之處」的移動。想想數字華容道：每一種拼塊的擺法都是一個狀態，每一次滑動都是一步移動，而搜尋就是去尋覓那串能拼出目標圖案的移動。
把它攤開來說，一個搜尋問題有四個部件：一個起始狀態、一組在狀態之間移動的動作、一個告訴你「到沒到」的目標測試，以及（常有的）每一步移動的代價，好讓你能偏好更省的路徑。所有可達狀態構成的那整張網，就是「狀態空間」。一個搜尋演算法會系統地探索這個空間——從起點向外鋪開，記下自己去過哪裡，一步步朝目標推進。不同策略以不同次序探索：有的求廣，有的求深，有的則順著一個啟發式，優先奔向最有希望的狀態。
它的重要性有兩重。從歷史看，把智能框定為搜尋，是AI最早的幾個大想法之一——下棋、尋路、規劃、解謎，全都套得進這個模子，它也在符號時代支撐了一批經典系統。從實用看，它至今仍在路線規劃器、物流排程器和遊戲AI底下運轉。它的硬性極限在於規模：狀態的數目往往會組合式地爆炸（一盤棋的局面，比可觀測宇宙中的原子還多），所以在大問題上，純粹的蠻力搜尋毫無指望。正是這種爆炸，讓啟發式——關於「該優先探索哪些狀態」的聰明猜測——成了必需，而非可有可無。
把解魔術方塊當作搜尋：方塊的每一種打亂狀態都是一個狀態；每一次轉動一面都是一個動作；目標測試是「每一面都是同一種顏色」。從任何一個狀態出發，都有18種可能的轉法，於是可達狀態會膨脹到天文數字。盲目的搜尋永遠做不完——這正是求解器為何要倚仗啟發式與結構，才能鎖定解法。
狀態、動作與目標測試——以及那場讓啟發式成為必需的組合爆炸。
狀態空間搜尋的致命敵人是組合爆炸：現實問題的狀態數多到天文級，窮舉搜尋因而不可能。這正是啟發式——把搜尋朝有希望的狀態修剪——並非奢侈品的原因：正是它，才讓搜尋壓根兒能用起來。