年少時對解這類「益智問題」，總有著那麼些興趣。學生時期，在人工智能 (AI: Artificial Intelligence) 的課程裡，教授們介紹 searching methods 時，有時也可以看到這個問題。可惜的是，或許是因為當時的課程內容太豐富，反倒沒有機會真的將這個程式寫出來玩玩。
這一陣子想整理一些從前感興趣的小程式，偶然間就想起 8-puzzle（或者更大盤面的「15-puzzle」）來。於是，花了些時間用 PHP5 把它實作出來。
演算法是採用 IDA* (Iterative Deepening A*)，因此理論上求得的應該是最佳解（什麼時候不是最佳解？就是我程式寫錯的時候啦）。上圖左方的盤面，程式花了 22 步才走到右方的目的地。
沒有留言:
張貼留言