通过图算法从地点列表中获取最优的地点组合

Question

我们遇到的网络情况是，他有四个节点 - 比如说

A

、

B

、

C

和

D

。问题 -

A

、

B

、

C

和

D

尚未解决，但有很多可能性。

假设

A

可以具有值

A1

、

A2

直至

An

。 与

B

相同 -

B1

、

B2

、

Bn

。

C

和

D

也一样。每个

An

、

Bn

、

Cn

和

Dn

都有坐标作为属性（元组 -

(21.2134, -32.1189)

）。

我们想要实现的目标 - 找到

An

、

Bn

、

Cn

和

Dn

的最佳组合，如果按顺序遍历（

A -> B -> C -> D

），它们彼此最接近。例如，它可以是

A11 -> B1 -> C9 -> D4

- 基本上从

A

、

B

、

C

和

D

的所有可能值中选择一个选项，以便这些值的组合彼此最接近所有这些组合。

我们当然正在尝试暴力方法，但它非常昂贵，因为它的时间复杂度是

N(A) * N(A) * N(C) * N(D)

。

因此，我们正在寻找一些基于图形的解决方案，我们可以通过存储带有坐标的所有点来利用图形，并且在运行时我们可以简单地传入所有点集（

n

的所有

A

点，所有

k 

B

的

点，

j

的所有

C

点和

l

的所有

D

点）到它，它将为每个类输出正确的点（

A

，

B

，

C

和

D

），路线是最佳的。

如果图形需要存储在内存中也没关系，运行时响应时间越快越好，内存不是限制，而且

An

和

Bn

之间是否存在路线在这里无关紧要，我们想要做的就是找出基于坐标的接近度（假设每组点之间有一条线性路线）。

Answer 1

我使用

networkx

编写了一个简短的示例（为了这个答案，我学习了它的基础知识）；代码可能很笨拙并且可以缩短，但它至少应该提供编写代码的基础。

我根据这个图做了图表：

import networkx as nx
import math

nodes = {
    "A": [("A_1", (0, 2)), ("A_2", (0, 5)), ("A_3", (0, 8)), ],
    "B": [("B_1", (1, 1)), ("B_2", (1, 3)), ("B_3", (1, 5)), ("B_4", (1, 7)), ],
    "C": [("C_1", (2, 0)), ("C_2", (2, 5)), ("C_3", (2, 9)), ],
    "D": [("D_1", (3, 1)), ("D_2", (3, 5)), ("D_3", (3, 7)), ],
}

G = nx.Graph()

G.add_nodes_from(["in", "out"])


def add_edge(n1, n2):
    origin = G._node[n1]["coords"]
    extremity = G._node[n2]["coords"]
    G.add_edge(n1, n2, weight=math.sqrt((origin[0] - extremity[0])**2 + (origin[1] - extremity[1])**2))


for node in nodes["A"]:
    G.add_node(node[0], coords=node[1])
    G.add_edge("in", node[0], weight=0)

for node in nodes["B"]:
    G.add_node(node[0], coords=node[1])
    for a_node in nodes["A"]:
        add_edge(a_node[0], node[0])

for node in nodes["C"]:
    G.add_node(node[0], coords=node[1])
    for b_node in nodes["B"]:
        add_edge(b_node[0], node[0])

for node in nodes["D"]:
    G.add_node(node[0], coords=node[1])
    G.add_edge(node[0], "out", weight=0)
    for c_node in nodes["C"]:
        add_edge(c_node[0], node[0])

print(nx.shortest_path(G, "in", "out", weight="weight"))

结果：

['in', 'A_2', 'B_3', 'C_2', 'D_2', 'out']

Answer 2

一种选择是为每个类别建立一个

KDTree

和

query

交替最近的地方：

from scipy.spatial import KDTree

kdtrees = {cat: KDTree(list(coords.values())) for cat, coords in places.items()}


def shortest_comb(places, categories, kdtrees):
    min_dis = float("inf")

    for init_name, init_coo in places[categories[0]].items():
        route, total_dis = [init_name], 0
        curr = init_coo

        for next_cat in categories[1:]: # from B and further..
            distance, index = kdtrees[next_cat].query(curr)
            following = list(places[next_cat].keys())[index]
            curr = places[next_cat][following]
            route.append(following)
            total_dis += distance

        if total_dis < min_dis:
            min_dis = total_dis
            mpr = route

    return mpr, min_dis

---

mpr, min_dis = shortest_comb(places, categories, kdtrees)

print(f"most plausible route: {'->'.join(mpr)}, distance={min_dis/1000:.2f}km")
# most plausible route: A6->B3->C3->D4, distance=43.50km

使用的输入：

import random

random.seed(1)


def rnd_points(n, cat, bbox=(21, -32, 22, -31), as_latlon=False):
    min_lon, min_lat, max_lon, max_lat = bbox
    points = [
        (
            random.uniform(min_lat, max_lat),
            random.uniform(min_lon, max_lon)
        ) for _ in range(n)
    ]
    if not as_latlon:
        from pyproj import Transformer
        transformer = Transformer.from_crs(4326, 32734)
        points = [pt for pt in transformer.itransform(points)]
    return {f"{cat}{i}": coo for i, coo in enumerate(points, 1)}


categories = "ABCD"
places = {cat: rnd_points(n, cat) for cat, n in zip(categories, (9, 7, 5, 6))}