馬踏棋盤(貪心算法)

馬踏棋盤:將馬隨機放在國際象棋的Board[0~7][0~7]的某個方格中,馬按走棋規則進行移動,走遍棋盤上全部64個方格,不重復。

右圖展示了采用貪心算法求解馬踏棋盤的過程。關鍵點在於對路徑有目的地篩選,盡量選擇出口少的路先走,也就是對當前點的下一個落腳點(可能是8個)進行排序,優先走可走的路最少的那個點,使得走法較好。

貪心算法(又稱貪婪算法)是指,在對問題求解時,總是做出在當前看來是最好的選擇。也就是說,不從整體最優上加以考慮,他所做出的是在某種意義上的局部最優解。 貪心算法不是對所有問題都能得到整體最優解,關鍵是貪心策略的選擇,選擇的貪心策略必須具備無後效性,即某個狀態以前的過程不會影響以後的狀態,只與當前狀態有關。

js源碼在 這裏

速度:

嘗試次數:0