在只能进行水平和垂直移动的网格中,从点a到点b寻找最短路径时,你如何考虑曼哈顿距离和切比雪夫距离的知情度和可接受性?
回答:
曼哈顿距离是两个独立轴上的距离之和,Manhattan = |x_a - x_b| + |y_a - y_b|
,而切比雪夫距离则是这两个距离中的最大值:Chebyshev = max(|x_a - x_b|, |y_a - y_b|)
。因此,曼哈顿距离总是至少与切比雪夫距离一样大,通常更大。
在网格上不允许对角线移动的情况下,这两种距离都是可接受的(它们都不会高估真实距离)。
鉴于这两种距离度量总是等于或小于真实距离,并且曼哈顿距离总是等于或大于切比雪夫距离,曼哈顿距离将始终至少与“真实情况”一样接近。换句话说,在这种特定情况下,曼哈顿距离将更具信息性。
请注意,如果允许对角线移动,或者如果你不是在讨论网格,那么情况可能会有所不同。