Python Создание возможных путей для точек x и y - PullRequest
Новая
       32

Python Создание возможных путей для точек x и y

0 голосов
/ 28 апреля 2019

У меня есть список точек X и Y, которые будут импортированы в программу.Мне было интересно, если есть возможность сделать каталог, как их подключить?Почти как древовидный граф, но вместо использования ребра он будет использовать точки x и y.

Символ [0] в этом примере будет отправной точкой, а числа будут точками из импортированного файла.

Например, 

                           ----4------5
                           |
8------7-----6----[0]------1-------2-----3
       |
    9---

Я обнаружил алгоритм с именем Breadth-first search, который может определить лучший путь, если ему даны начальная и конечная точка.Я знаю, что алгоритм предназначен для поиска возможных путей, но не определения путей.Если бы вы получили очки из приведенного выше примера .. 

point    X    Y
  0      0    0
  1      1    0
  2      2    0
  3      3    0
  4      1.5  0.5
  5      2.5  0.5
  6      -1   0
  7      -2   0
  8      -3   0
  9      -2.5 -0.5

Я бы хотел, чтобы приведенные выше пункты создавали каталог, подобный .. 

graph = {
        '0': ['1', '6'],
        '1': ['2', '4'],
        '2': ['3'],
        '4': ['5'],
        '6': ['7'],
        '7': ['8','9']
        }

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

Поиск в ширину.py 

def bfs(graph, start, end):
    queue = []
    queue.append([start])
    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node == end:
            return path
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print(bfs(graph, '0', '5'))

Ответы [ 2 ]

0 голосов
/ 28 апреля 2019

Как вы сказали, поиск в ширину не является алгоритмом для поиска наилучшего пути по двум узлам, он только сообщает вам, существует ли путь, соединяющий их.Если вы хотите лучший путь, для этого есть три известных алгоритма: Дейкстра, Беллман-Форд и Флойд-Варшалл.В вашем случае я считаю, что Dijkstra будет лучшим выбором.

В Python есть простая в использовании и замечательная библиотека для работы с графиками, она называется Networkx .В нем есть много методов почти для каждой проблемы, связанной с графами, включая алгоритмы, которые я упомянул.Вот ссылка на алгоритм Дейкстры , реализованный в этой библиотеке.

0 голосов
/ 28 апреля 2019

Предполагая, что вы хотите включить 5 в качестве ключа в свой результат, вы можете использовать рекурсию для создания желаемого словаря: 

import math, collections
data = {0.0: [0.0, 0.0], 1.0: [1.0, 0.0], 2.0: [2.0, 0.0], 3.0: [3.0, 0.0], 4.0: [1.5, 0.5], 5.0: [2.5, 0.5], 6.0: [-1.0, 0.0], 7.0: [-2.0, 0.0], 8.0: [-3.0, 0.0], 9.0: [-2.5, -0.5]}
def group(d, start, seen = []):
   x, y = d[start]
   r = [a for a, [j, k] in d.items() if a != start and a not in seen and math.hypot(abs(x-j), abs(y-k)) <= 1]
   if not r:
     return {}
   result = {start:r}
   for i in r:
     result.update(group(d, i, seen+[start, *r]))
   return result

result = group(data, 0)

Вывод: 

{0: [1.0, 6.0], 1.0: [2.0, 4.0], 2.0: [3.0, 5.0], 4.0: [5.0], 5.0: [3.0], 6.0: [7.0], 7.0: [8.0, 9.0]}

Преобразование значений в строки: 

new_result = {str(int(a)):list(map(str, map(int, b))) for a, b in result.items()}

Вывод: 

{'0': ['1', '6'], '1': ['2', '4'], '2': ['3', '5'], '4': ['5'], '5': ['3'], '6': ['7'], '7': ['8', '9']}
...