基于python的骑士游历问题解析

作者：凡人多烦事01 | 2024-05-15 15:12:20

踩

基于python的骑士游历问题解析

系统：windows

语言：C++

在棋盘上，骑士只能走日字（L 形）.假设骑士在（0,0），我们希望用最少的移动步数使他走到（x,y）（例如，从（0,0）到（1,1）需要两步，骑士可以移动到棋盘的负坐标处）。

要求：设计一个可采纳的启发式函数，来估计需要的最小移动步数值，保证结果足够地精确。用 A*算法和你的启发式函数来编程实现求解。结果输出详细过程。

证明你的函数是可采纳的。

将路径长度规定为移动步数。

所得解路径必为哈密顿路径。

根据对称性，可以看出需要到达负坐标之后再到达目的地的路径，完全可以先到达对称处的正坐标点，再到达目的地。

如下图：

s —> t1：可以找到相应的对称点A1’；

s —> t2：可以找到相应的对称点B1’和B2’；

并且路径长度是相同的。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/573507