Вычислить кратчайшие расстояния между несколькими точками

Question

Итак, вот в чем проблема: мне нужен алгоритм, заданный набором точек n(x;y) Какой у вас самый короткий путь, чтобы связать все точки вместе, без каких-либо ограничений , что означает, что одна точка может ссылаться на любое количество других точек.

Первая идея решить эту проблему была для каждой несвязанной точки, найти ближайшую точку и ссылку на нее, а затем удалить эти две точки из несвязанного списка точек и начать сначала до тех пор, пока у вас не будет больше несогласованных точек. На этом этапе вы создали блоки ближайших точек. Затем вы связываете эти блоки, находя их кратчайшее расстояние между ними.

Проблемы этого метода: 1. Он не дает кратчайший путь 2. Это кажется довольно неэффективным. Поэтому я спрашиваю вас, какой тип алгоритма выполняет такой расчет (мне просто нужно общее расстояние между точками, Меня не волнует, как они на самом деле связаны)?

Answer 1

Это звучит так, как будто вы можете использовать алгоритм связующего дерева. В псевдокоде:

build_tree(unconnected_nodes): 
    connected_nodes = set() 
    // pick a random unconnected node 
    connected_nodes.add(unconnected_nodes.pop()) 

    while not empty(unconnected_nodes): 
    best_connected_node = None 
    best_unconnected_node = None 
    shortest_distance = +Infinity 

    for node1 in connected_nodes: 
     for node2 in unconnected_nodes: 
     if distance(node1, node2) < shortest_distance: 
      shortest_distance = distance(node1, node2) 
      best_unconnected_node = node2 
      best_connected_node = node1 
    connect(best_connected_node, best_unconnected_node) 
    unconnected_nodes.remove(best_unconnected_node) 
    connected_nodes(best_unconnected_node) 

    return connected_nodes 

Это при условии, что у вас есть то, что это по существу полностью связный граф и по «координатам» и «никаких ограничений» Я не думаю, что это то, что у вас есть. Если нет, вам нужно пересечь множество вершин из подключенных к несвязанным узлам.

Answer 2

Я думаю, вы можете применить алгоритм кратчайшего пути Prim или алгоритм кратчайшего пути Крускала. Эти алгоритмы обычно обеспечивают самый короткий путь между двумя различными узлами в сети. Для вашей проблемы вы можете представить каждую координирующую пару как вершину и найти кратчайший путь между ними, создав минимальное остовное дерево ребер. Я пишу псевдокод ниже:

mst = queue of all the result edges(or co-ordinates) 
p = queue of all the connected edges 
while p is not empty 
    edge e = min of p 
    if union-find(both vertices of edge e) 
    continue 
    else 
    union-find.add(both vertices of edge e) 
    mst.add(e) 

В конце концов вы будете иметь «МСТ», представляющий кратчайший путь между всеми координатами