logo标签列表

计算曼哈顿距离

javaalgorithm
13

我正在使用Java 2D数组int[][] state实现NxN拼图。我需要按以下方式使用曼哈顿启发式：

             the sum of the vertical and horizontal distances from 
                the current node to the goal node/tile

                                +(plus)

    the number of moves to reach the goal node from the initial position

目前我不知道该如何继续了。我是一个2D数组拼图游戏编程的初学者，所以很难理解某些概念。我该如何用Java编写这段代码？

1个回答
55

这更像是一个数学问题，但无论如何曼哈顿距离是水平距离和垂直距离的绝对值之和。

int distance = Math.abs(x1-x0) + Math.abs(y1-y0);

查看更多信息：http://en.wikipedia.org/wiki/Taxicab_geometry

谢谢您的回复。这就是我需要计算水平和垂直距离的全部吗？作为一个初学者，我需要帮助。我认为也许我需要从一个瓷砖移动到另一个瓷砖，并每次将1添加到累积成本中。 - Eddy Freeman
我提供的代码仅适用于普通曼哈顿距离 - 如果我正确理解这个谜题，您需要将移动次数加入其中。 - Otto Allmendinger
1
Eddy：是的，因为曼哈顿距离是相同的，无论你走哪条“街道”去那里。 - malejpavouk
由于某种原因，在我上AI课时，我误以为曼哈顿距离是欧几里得距离的平方（即为了节省一个sqrt）。感谢您帮助我的学生们挽回了一些分数。 - 3Doubloons
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接