算法问题:马去外婆家。

黄正文 发布于 2013/04/19 13:09
阅读 387
收藏 2

象棋中的小马,去外婆家玩,但是路上有些地方有老虎,不能去,还有些地方有山翻不过去,假设小马家在(0,0),外婆家在(a,b)求算法找出最优的路径,让小马到外婆家的所用的时间最短

老虎和山其它就是: 目的地有棋或拐脚马的问题,初步可以不考虑

另外:假设棋盘无限大。。。。。

以下是问题补充:

@黄正文:这个最优解其它只要算出向那个方向走了多少步就行了。具体路线是很多的 (2013/04/19 13:33)
@黄正文:群友讨论记录:在出发点上的八个方向上的点才能按直线到达 可以先求:从一个点,跳到另一个点,的最小步数 (0,0),跳到(0,1)至少需要3步 (0,1)跳到(1,1)至少需要?步 人家是马,只能按马的规则跳。。(暂不考虑拐脚马和目标点有棋子的问题) 棋盘无限大 ----------------------------------- 先通过 0,0——a,b界定 棋盘范围 算(X1,Y1)坐标点有几个位置可以走 得到list (X21,Y21)(X22,Y22) 然后迭代 直到有一个坐标是(A,B) 然后记录步数 因为马能移动的距离有限(最多为坐标+2)所以 在没有障碍物的情况下不用考虑那个都 就在0,0——a,b范围上+2 就可以界定边界 -----------------------------------(深度搜索或双向深度搜索) 这个最优解其它只要算出向那个方向走了多少步就行了。具体路线是很多的 (2013/04/19 13:52)
@黄正文:(0,0)走到(1,1)要2步 (2013/04/19 14:04)
@黄正文:希望数学算法 和 程序算法 (2013/04/19 14:08)
加载中
0
泡不烂的凉粉
泡不烂的凉粉

早期的时候,忘记是在哪地方见过。

不考虑障碍。 可以计算绝对值, x+y 如果是偶数,步骤肯定是偶数,如果是奇数,步骤肯定是奇数。

0
黄正文
黄正文
数学工式是:
已知:,n1(-1,-2)+n2(-2,-1)+n3(-1,+2)+n4(-2,+1)+n5(+1,+2)+n6(+1,-2)+n7(+2,-1)+n8(+2,+1)=(a,b)
(a,b)已知,求min(n1+n2+n3+n4+n5+n6+n7+n8)
0
中山野鬼
中山野鬼
说人话好吗?看了外婆和小马,总觉得还有个狼,就是不知道啥问题,哈。是否能用数学和图形表示?
0
ChenQi
ChenQi
这个问题不太容易哦。
0
用户已屏蔽
用户已屏蔽
。。。我也没明白。。。
0
返回顶部
顶部