Кратчайший путь через набор точек - PullRequest
Новая
       19

Кратчайший путь через набор точек

1 голос
/ 13 января 2020

У меня есть набор точек (представленных комплексными значениями), и мне нужно найти кратчайший путь через них. Это немного похоже на проблему коммивояжера, но я не могу найти (или понять) решение, которого нет в O (n!). Я знаю, как вычислить достаточно короткие решения в O (n ^ 3), O (n²), но я хотел знать, возможно ли получить лучшее. Спасибо ! Вот код, который я использую для "Short Enough Path" 

def insert(x,liste,taille):
    max_add = 10**9
    n = len(liste) -1
    for i in range(n):
        test = abs(liste[i] -x) + abs(liste[i+1] - x) - taille[i]
        if test < max_add:
            max_add = test
            i_max = i

    taille[i_max] = abs(liste[i_max]-x)
    taille.insert(i_max+1,abs(liste[i_max+1] - x))
    liste.insert(i_max+1,x)

def sort(x,i=0):
    taille = [0]
    tri = [x[i]]*2
    for y in x[:i]+x[i+1:]:
        inserer(y,tri,taille)
    return tri, taille

def the_best(liste):
    n = len(liste)
    shortest = 10**9
    for i in range(n):
        a,b = sort(liste,i)
        if sum(b) < shortest:
            back = a,b
    return back

`Конечно, функция" the_best "находится в O (n ^ 3), поэтому я обычно использую только функцию" sort ". Список называется "taille" построен следующим образом:

taille [i] = abs (liste [i] - liste [i + 1])

liste [-1] = liste [0]

1 Ответ

0 голосов
/ 14 января 2020

Из того, что я понимаю в вашем описании, это действительно проблема TSP. Это хорошо известная проблема NP-hard , и как таковой эффективный алгоритм ее решения не существует (даже если он существует, мы еще не знаем о нем) , Это одна из известных открытых проблем в области компьютерных наук.

Действительно, попробуйте решить ее, но не задерживайте дыхание:)

Общее прочтение: https://en.wikipedia.org/wiki/Travelling_salesman_problem

Вы также можете быстро прочитать: https://en.wikipedia.org/wiki/P_versus_NP_problem

...