Regne ut lengste rute mellom 5-10punkt(gps kordinater)

[Richard87]

Hei,

 

Har noen en idee til hvordan jeg elegant kan regne ut den lengste mulige avstanden mellom 5-10 punkter?

[avo]

Regn ut korteste, og legg til så mye du vil...

Lengste vil jo altid være mulig å få opp i mot uendelig

[Richard87]

hehe, det er en måte å gjøre det på... jeg så for meg å bruke svaret fra google maps(kjørelengden) mellom 2 punkt, og så finne den kombinasjonen av punkt som er lengst... men avlikevel ha en så rett sum mulig linje mellom punktene...

[GeirGrusom]

Du er vel inne på travelling salesman problemet.

[etse]

regner med du kun kan gå innom et punk en gang? Dette høres ut som enkel graf-teori. Sett opp en vektet graf som beskriver problemet; og siden det er så få punkter kan man da gjøre et enkelt breddeførst eller dybdeførst søk gjennom grafen og ta den veien som var lengst. Vil selv anbefale dybde-først-søk her.

 

http://en.wikipedia.org/wiki/Depth-first_search

http://www.algolist.net/Algorithms/Graph/Undirected/Depth-first_search

 

Om det hadde vært flere punkter ville andre graf-algoritmer vært bedre.

 

Jeg ser du la dette i .NET delen, men du får gjøre den delen selv. Kan gi deg et eksempel skrevet i python.

La oss forutsette at du har følgende punkter hvor tallet i mellom dem er avstanden mellom punktene. Dette kan beskrive f.eks. mulige kjøreruter mellom forskjellige byer.

 

Setter opp en nabo-matrise som beskriver denne grafen:

 

# -*- coding: cp1252 -*-
matrix = [
[0,7,0,5,0,0,0],
[7,0,8,9,7,0,0],
[0,8,0,0,5,0,0],
[5,9,0,0,15,6,0],
[0,7,5,15,0,8,9],
[0,0,0,6,8,0,11],
[0,0,0,0,9,11,0]]

# Finner den lengste stien fra et gitt startpunkt
def dfs(start):
   fringe = [(start,0,[])]
   longest = ([], -1)
   while len(fringe) > 0:
       node, length, path = fringe.pop()
       if length > longest[1]:
           longest = (path+[node], length)

       neighbours = get_neighbours(node)
       for vertex,distance in neighbours:
           if vertex not in path:
               fringe.append( (vertex, length+distance, path+[node]) )
   return longest

# Gir alle naboene til en gitt node, og avstanden
def get_neighbours(vertex):
   neighbours = list()
   for x in xrange(len(matrix)):
       if x == vertex:
           continue
       if matrix[vertex][x] != 0:
           neighbours.append((x, matrix[vertex][x]))
   return neighbours

def print_path(path):
   for x in xrange(len(path[0])):
       print chr(path[0][x]+65),
       if x < len(path[0])-1:
           print " -> ",
   print
   print "Total length:",path[1]

if __name__ == '__main__':
   longest_path = ([], 0) # ([path], length)

   # Vi prøver alle mulige veier fra alle mulige startpunkter
   for x in xrange(len(matrix)):
       path = dfs(x)
       if path[1] > longest_path[1]:
           longest_path = path
   print_path(longest_path)

 

Output:

C -> B -> A -> D -> E -> G -> F

Total length: 55

Endret 25. mai 2011 av etse

[Richard87]

Wow, nøyaktig hva jeg hvar ute etter takker for svar!