Самый короткий путь между связанными парами кортежей

Question

Я новичок в этом, и я был бы очень полезен для любой помощи ... У меня есть список кортежей, и мне нужно найти кратчайший путь между связанными парами кортежей. Например, у меня есть список, называемый пар = [(1,2), (2,4), (1,3), (3,1), (4,3)], и мне нужно найти кратчайший путь для:

1 to 2, 1 to 3 and 1 to 4 
2 to 1, 2 to 3 and 2 to 4 
3 to 1, 3 to 2 and 3 to 4 

в этом списке пар, если при поиске для подключения от 1 до 3, я должен возможных исходов:

1) (1,3) 
2) (1,2)-(2,4)-(4,3) 

и, конечно, самый короткий из них первый - (1,3)

Thanx ...

Answer 1

Это Travelling salesman problem. Вы можете использовать генетический алгоритм, он будет нацелен на достижение цели с наименьшей стоимостью операций. Приветствую.

Answer 2

Используйте BFS для решения задачи кратчайшего пути на невзвешенном графике.

Псевдо код:

Create Queue q; 
push into q starting node and mark distance to starting node as 0. 
while(q is not empty){ 
get n : first elemnt in the queue 
get all connected nodes to n that are not yet visited and push them to the queue: 
mark the distance to those node as the distance to n + 1. 
} 

Пример: предполагается, что ваш начальный узел равен 1.

соединения вы имеете в графике:

1->2, 1->3, 1->4 
    2->1, 2->3, 2->4 
    3->1, 3->2, 3->4 

Установите посещаемый массив булевы: посетил 4 = {false, false, false, false} и массив расстояний dist 4 = {inf, inf, inf, inf} и родительский массив = {-1, -1, -1, -1}.

Теперь толкать узел 1 в очереди Q, установить его расстояние до 0 и родителя до 1 затем начать:

Итерация 1 состояние:

Queue = {1} 
Dist = {0,inf,inf,inf} 
visited= {true,false,false,false} 
parent= {1,-1,-1,-1} 

Итерация 2:

единственный узел в очереди - 1, вы выбираете его и нажимаете своих соседей на очередь, которые являются узлами: 2,3,4. обновить их расстояния

Queue = {2,3,4} 
Dist = {0,1,1,1} 
visited= {true,false,false,false} 
parent= {1,1,1,1} 

и так далее, пока вы не получите пустую очередь. (означает, что вы посетили все узлы).

В этом примере вы увидите, что расстояние до узла 3 равно Dist 3 = 1, родительский элемент этого узла является родительским 3 = 1 (в случае, если вы хотите восстановить путь).

для получения дополнительной информации проверки BFS, а также реализация в Python: Python BFS DFS или this

Answer 3

Если вы ищете только для кратчайшего пути между двумя числами (позволяет называть их узлы) и длиной ребер между ними- , вы можете использовать BFS, если у них есть другое расстояние, вы можете использовать Dijkstra. Поскольку оба являются алгоритмами графа, вам может потребоваться их немного изменить, поскольку у вас есть только список ребер, а не структура графика.

Answer 4

def components_pairs(pairs): 

    components = [] 

    for v1, v2 in pairs: 
     for component in components: 
      if v1 in component or v2 in component: 
       component.add(v1) 
       component.add(v2) 
       break 
     else: 
      components.append({v1, v2}) 

    return components 

pairs = [(1,2),(1,3),(2,4),(3,1),(4,3)] 

print(components_pairs(pairs))