3

我在图片中有多个点。垂直方向最近的两个点之间的距离（在A和B、或B和C、或D等之间E）是distance_y。两个最近点之间的水平距离（在A和之间D等）为distance_x。

假设：

distance_y < distance_x < 2*distance_y

                distance_x
           A <-------------> D <-------------> G
           | 
distance_y |
           | 
           B <-------------> E <-------------> H

           -

           C <-------------> F <-------------> I

我将任意两点之间的距离公式化如下：

Distance(point P1, point P2) = m * distance_x + n * distance_y

例如，对于点Aand B，m = 0和n = 1;

问题是：从一个点开始P，我怎样才能通过最近的邻居首先遍历所有剩余的点（即按远离点的距离降序排列P）？

我不想计算从其他点到的整个距离P，然后按距离的降序对这些点进行排序，P因为这很耗时。我想寻找可以快速评估邻居位置而不计算其他点位置的算法。

例如，从点开始D，以下几点将是

E (m= 0, n = 1),
A (m= 1, n = 0),
G (m= 1, n = 0),
F (m =0, n = 2),
B (m= 1, n = 1),
H (m= 1, n = 1),
C (m= 1, n = 2),
I (m= 1, n = 2).

如何确定搜索最近邻居的顺序m和搜索顺序？n

4

2 回答 2

0

您只有两种连接：长连接和短连接。

将您的图存储为邻接列表，其中每个节点都有 2 个容器，而不是节点列表。第一个容器具有所有短 ( y) 距离节点，而第二个长 ( x) 距离节点。

在图上执行BFS搜索，唯一的区别是您将有两个搜索队列。

从起始节点：将短距离容器添加到第一个队列，将长距离容器添加到第二个队列。您从第一个队列中弹出容器并遍历其元素并将每个节点的所有短距离容器组合成一个并将它们添加到第一个队列和长距离（也全部组合在一起）到第二个队列，然后从您的第二个队列，对于该容器中的每个节点，您将短距离容器一起添加到一个大队列中，然后将大队列添加到第二个队列，将长距离添加到第一个队列。然后你再次从第一个队列中弹出一个容器......

总结一下：你一个一个地弹出每个队列。结果是一个带有节点的容器，您遍历每个节点并收集所有短距离容器并将它们添加到您从中弹出容器的队列中，长距离容器也会发生同样的事情，只是它们被添加到第一个队列。

唯一的问题是，使用这种算法，n长总是比n+1短好。

这就是从 C 开始遍历的样子，每个节点旁边的 bumber 显示了它们到达的顺序。

A5---B2---C0---D2---E5 
|    |    |    |    |
F8---G4---H1---I4---L8
|    |    |    |    |
M10--N7---O3---R7---P10
|    |    |    |    |
W11--Y9---X6---T9---S11
于 2013-11-02T21:39:35.547 回答
0

不确定我是否理解，但看起来像一个 Dijkstra 算法应用程序： http ://en.wikipedia.org/wiki/Dijkstras_algorithm

于 2013-11-02T19:17:59.517 回答