這個問題是由數學家 Euler 提出的：西洋棋的騎士能否走完一個空棋盤的六十四格，而且每格只走過一次。這條路徑，在圖論上稱為「Hamiltonian path」 ，而每個格子稱為「vertex」，每個格子能向外走出的步數稱為「該vertex的degree」。
本程式利用一種方法（accessibility heuristic），由任意點出發，找出一條Hamiltonian path：先走到degree少的格子，如此的話，越到後面，剩餘格子的degree可能比較大，則不容易因無路可走而失敗。運用此方法，在八格見方的棋盤上，由任一點找出一條Hamiltonian path的機率非常高。
(Quote From：作者台大數學系90年班 張文賢)
Links：At Wikipedia
At Wolfram Mathematica
沒有留言:
張貼留言