马踏棋盘(贪心算法)

马踏棋盘:将马随机放在国际象棋的Board[0~7][0~7]的某个方格中,马按走棋规则进行移动,走遍棋盘上全部64个方格,不重复。

右图展示了采用贪心算法求解马踏棋盘的过程。关键点在于对路径有目的地筛选,尽量选择出口少的路先走,也就是对当前点的下一个落脚点(可能是8个)进行排序,优先走可走的路最少的那个点,使得走法较好。

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

js源码在 这里

速度:

尝试次数:0