CODEWITHSUNDEEP
python-3.xalgorithmsortingoptimizationbig-o
Guelque Hadrien
Guelque Hadrien

Reputation: 47

Shortest path trough a set of points

I have a set of points (represented by complex values), and I need to find the shortest path through these. It looks a bit like the travelling salesman problem, but I can't seem to find (or understand) a solution that isn't in O(n!). I know how to compute short enough solutions in O(n^3), O(n²), but I wanted to know if it was possible to have THE best one. Thank you ! There's the code I use for a "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

` Of course the "the_best" function is in O(n^3) so I usually use the "sort" function only The list called "taille" is built like this:

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

liste[-1] = liste[0]

Upvotes: 1

Views: 153

Answers (1)

small_cat_destroyer
small_cat_destroyer

Reputation: 357

From what I understand in your description, this is indeed the TSP problem. It is a well-known NP-hard problem, and as such an efficient algorithm to solve it does not exist (even if it does, we don't know of it yet). It's one of the famous open problems in Computer Science.

Indeed, do give it a try to solve it, but do not hold your breath :)

General reading: https://en.wikipedia.org/wiki/Travelling_salesman_problem

You may also want to give a quick read to: https://en.wikipedia.org/wiki/P_versus_NP_problem

Upvotes: 1

Related Questions