Entfernungsermittlung

[Mawilo]

Hallo,

ich möchte gerne eine Entfernungsermittlung mit Python durchführen. Leider fehlt mir noch der "rote Faden" und bitte deshalb um ein paar Tips, wie ich das am besten angehen kann.
Ziel ist, dass ich den Anfangsort und den Endort angebe und das Programm mir die Entfernung ermittelt. Die Daten liegen aber nur von Ort zu Ort vor. Das Programm muss sich den richtigen Weg selbst suchen. Es sind maximal 30 Orte für eine Entfernungsberechnung zu addieren.

Wie sollten am besten die Daten zur Verfügung stehen? Ich habe Versuche mit einem Dictionary und einer Liste gemacht (mit wenig Erfolg ).

Code: Alles auswählen

km_dic = {'a-b':'3,123','b-c':'5,689','b-x':'20,687','c-d':'4,456'}

km_list = [['a','b','3,123'],['b','c','5,689'],['b','x','20,687'],['c','d','4,456']]

Oder gibt es noch andere (bessere) Möglichkeiten für die Datenhaltung?

Wenn ich von a nach d eingebe, müsste das Programm den Wert 13,268 ausgeben (von a nach x ist es der Wert 23,81) .

Ich bin für jeden Hinweis dankbar.

Stephan

[Milan]

Hi. Die Idee mit dem Dict ist schon nicht so schlecht, aber du musst sie anders ansetzen. Dann kann man mittels Rekursion ziemlich gut durchkommen. Eine Verbindung von a nach b ist genau dann möglich, wenn es eine direkte Verbindung gibt oder es einen Ort c gibt, der von a und b aus zu erreichen ist (oder mehrere Orte daziwschen halt). Und genau in der Form formuliert man das dann auch. Allerdings kann es ja sein, dass es verschiedene Strecken gibt. Deswegen lass ich hier in der Version immer alle Möglichkeiten raussuchen und gebe die Entfehrnung mit an:

Code: Alles auswählen

m_dict = {("a","b"):3123,("b","c"):5689,("b","x"):20687,("c","d"):4456,("x","c"):100}
def entfehrnung(von,nach,m_dict,zwischenstationen=(),_distanz=0):
    """Liste von Routen [[(von,...,nach),distanz],[...]]"""
    if zwischenstationen:
        letzer_ort=zwischenstationen[-1]
    else:
        zwischenstationen=(von,)
        letzer_ort=von
    if letzer_ort == nach:
        return [zwischenstationen,_distanz]
    erg=[]
    for (ort1,ort2),distanz_1_2 in m_dict.iteritems():
        if ort1 == letzer_ort and ort2 not in zwischenstationen:
            erg.extend(entfehrnung(von,nach,m_dict,zwischenstationen+(ort2,),_distanz+distanz_1_2))
    return erg
print entfehrnung("a","c",m_dict)

hth Milan

[Dookie]

Hi Stephan,

zur Ergänzung. Solche Probleme sind im Allgemeinen mittels Graphentheorie beschreib und lösbar: http://de.wikipedia.org/wiki/Graphentheorie


Gruß

Dookie

[Milan]

Interessante Sache, wusste ich auch noch nicht... schätze das würde man beim Studium auseinanderkauen (was ich aber nicht vorhabe).

[mawe]

Hi!

Dazu gibts auch ein recht nettes Modul: graph 0.2.

Gruß, mawe

[Mawilo]

Uff, ihr seit eben Häuptlinge und ich nur Indianer

Das ist genau, was ich suche. Ich werde mir den Code noch etwas auseinandernehmen, damit ich das auch verstehe.

@Dookie:
... da war ich in der Vorlesung bestimmt gerade Kreide holen .
Das klingt ganz interessant. Da ich mich beruflich mit einem Optimierungsprogramm beschäftige (ich muss es nur bedienen - nicht programmieren) und in dem Umfeld einige solche Probleme wie beschrieben habe, werde ich mich auch mal mit der Graphentheorie beschäftigen.

Vielen Dank

Stephan

[mawe]

Hi!

Hab gerade im Cookbook das gefunden: Dijkstra's algorithm for shortest paths. Vielleicht interessiert/hilft Dir das auch.

Gruß, mawe

[Mawilo]

Hallo,

ich habe doch noch zwei Fragen

1. Zur Angabe der Gesamtentfernung benötige ich noch eine Aufteilung nach Gebieten. D.h., es werden für verschiedene Verbindungen Gebiete definiert. Nach dem der Weg und die Gesamtentfernung feststeht, soll die Entfernung anteilmäßig für die Gebiete ausgegeben werden.
Gebiete:

Code: Alles auswählen

vvo = [('a','b'),('b','c')]
vms = [('b','x'),('c','d')]
tpt = [('x','c')]

Ich habe den Code leicht modifiziert:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-


m_dict = {("a","b"):3123,("b","c"):5689,("b","x"):20687,("c","d"):4456,("x","c"):100}

vvo = [('a','b'),('b','c')]
vms = [('b','x'),('c','d')]
tpt = [('x','c')]
       

def entfernung(von,nach,m_dict,zwischenstationen=(),_distanz=0):
    """Liste von Routen [[(von,...,nach),distanz],[...]]"""
    if zwischenstationen:
        letzer_ort=zwischenstationen[-1]
    else:
        zwischenstationen=(von,)
        letzer_ort=von
    if letzer_ort == nach:
        return [zwischenstationen,_distanz]
    erg=[]
    for (ort1,ort2),distanz_1_2 in m_dict.iteritems():
        if ort1 == letzer_ort and ort2 not in zwischenstationen:
            erg.extend(entfernung(von,nach,m_dict,zwischenstationen+(ort2,),_distanz+distanz_1_2))
    return erg

von = 'a'
bis = 'd'

routen = entfernung(von,bis,m_dict)
anz_rout = len(routen)/2
z = 0

print 'mögliche Routen: %s'%anz_rout
for i in range(0,len(routen),2):
    z = z + 1
    print 'Route %s:' % (z)
    print 'von %s nach %s über ' % (von,bis),
    for x in routen[i][1:-1]:
        print x,
    print 'Entfernung: %7.3f km' % (routen[int(i) + 1]/1000.0)

2. Kann man Verbindungen definieren, die ausgeschlossen werden sollen?

Ich habe mir verschiedene Dokumente über den Dijkstra-Algorithmus (Graphentheorie, Link von mawe) ausgedruckt. Aber bis ich das alles begriffen habe, dauert es noch eine Weile.


Stephan

[Mawilo]

Hallo,

ich glaube, ich hab ne Lösung für die Aufteilung nach Gebieten gefunden:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-

#from km_verzeichnis import m_dict,zvoe,zvms,zvon     
m_dict = {("a","b"):3123,("b","c"):5689,("b","x"):20687,("c","d"):4456,("x","c"):100}
zvoe = [('a','b'),('b','c')]
zvms = [('b','x'),('c','d')]
zvon = [('x','c')]

def entfernung(von,nach,m_dict,zwischenstationen=(),_distanz=0):
    """Liste von Routen [[(von,...,nach),distanz],[...]]"""
    if zwischenstationen:
        letzer_ort=zwischenstationen[-1]
    else:
        zwischenstationen=(von,)
        letzer_ort=von
    if letzer_ort == nach:
        return [zwischenstationen,_distanz]
    erg=[]
    zvoel = []
    for (ort1,ort2),distanz_1_2 in m_dict.iteritems():
        if ort1 == letzer_ort and ort2 not in zwischenstationen:
            erg.extend(entfernung(von,nach,m_dict,zwischenstationen+(ort2,),_distanz+distanz_1_2))
    return erg

def gebiet(strecke):
    m_zvoe = 0
    m_zvms = 0
    m_zvon = 0
    m_nn = 0
    x = 0
    try:
        for abschnitt in strecke:
            if (strecke[x],strecke[x+1]) in zvoe:
                m_zvoe = m_zvoe + m_dict[(strecke[x],strecke[x+1])]
            elif (strecke[x],strecke[x+1]) in zvms:
                m_zvms = m_zvms + m_dict[(strecke[x],strecke[x+1])]
            elif (strecke[x],strecke[x+1]) in zvon:
                m_zvon = m_zvon + m_dict[(strecke[x],strecke[x+1])]
            else:
                m_nn = m_nn + m_dict[(strecke[x],strecke[x+1])]
            x = x + 1           
    except:
        pass
    print 'Gebiet ZVOE: %s km'%(m_zvoe/1000.0)
    print 'Gebiet ZVMS: %s km'%(m_zvms/1000.0)
    print 'Gebiet ZVON: %s km'%(m_zvon/1000.0)
    print 'Ohne Gebiet: %s km'%(m_nn/1000.0)
    
von = 'a'
bis = 'd'

routen = entfernung(von,bis,m_dict)
anz_rout = len(routen)/2
z = 0
for i in range(0,len(routen),2):
    z = z + 1
    print 'Route %s:' % (z)
    print 'von %s nach %s über ' % (von,bis),
    for x in routen[i][1:-1]:
        print x,
    print
    print 'Entfernung: %7.3f km' % (routen[int(i) + 1]/1000.0)
    gebiet(routen[i]) 

ist vieleicht nicht die schönste aber dafür ne eigene Lösung
Nun muss ich das irgendwie noch in eine class umwandeln, damit ich das aus einem Programm heraus aufrufen kann.

Stephan