Recherche de chemin optimum

Soyez le premier à donner votre avis sur cette source.

Snippet vu 6 576 fois - Téléchargée 32 fois

Contenu du snippet

ça recherche le meillieur chemin. ça peut toujours servir.

Source / Exemple :

#! /usr/bin/env python
from math import sqrt, sin, cos
from Tkinter import *

def Distance(a, b):
    x = (a.x-b.x)
    y = (a.y-b.y)
    return sqrt(x*x+y*y)

def Path2Str(path):
    flag = 0
    spath = ""
    for town in path:
        if flag: spath = spath + " => "
        else: flag = 1
        spath = spath + town.name
    return spath

def Cost2Str(cost):
    t_s = int(cost*3600.0)
    s = t_s % 60
    m = (t_s / 60) % 60
    h = (t_s / 3600)
    return str(h)+":"+str(m)+":"+str(s)


class Road:
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.speed = 70.0
        self.holdup = 0.0
        a.road_list.append(self)
        b.road_list.append(self)
    def get_end(self, start):
        if self.a == start: return self.b
        if self.b == start: return self.a
    def set_holdup(self, holdup):
        self.holdup = float(holdup)
    def cost(self):
        return Distance(self.a,self.b)/(self.speed/(self.holdup+1.0))

class BigRoad(Road):
    def __init__(self, a, b):
        Road.__init__(self, a, b)
        self.speed = 90.0

class HighRoad(Road):
    def __init__(self, a, b):
        Road.__init__(self, a, b)
        self.speed = 150.0


class Node:
    def __init__(self, x, y, name):
        self.x = x
        self.y = y
        self.name = name
        self.road_list = []


class Node2D(Node):
    def __init__(self, x, y, map2d):
        Node.__init__(self, x, y, "("+str(x)+":"+str(y)+")")
        self.x = x
        self.y = y
        self.map2d = map2d
        self.road_list = map2d.get_next(self)

class Road2D(Road):
    def __init__(self, a, d, s, map2d):
        self.a = a
        self.d = d
        self.map2d = map2d
        self.speed = s
        self.holdup = 0.0
    def get_end(self, start):
        x = self.a.x
        y = self.a.y
        if d%2 == 0: y = y + (d-1)
        else: x = x + (2-d)
        return self.map2d.get_node(x,y)
    def cost(self):
        return (self.holdup+1.0)/self.speed

class Map2D:
    def __init__(self, x, y, fct):
        self.x = x
        self.y = y
        self.fct = fct
    def get_node(self, x, y):
        return Node2D(x, y, self)
    def get_next(self, node):
        road_list = []
        if node.x > 0:
            road_list.append(Road2D(node,3,(self.fct(node.x,node.y)+self.fct(node.x-1,node.y))/2,self))
        if node.x < (self.x-1):
            road_list.append(Road2D(node,1,(self.fct(node.x,node.y)+self.fct(node.x+1,node.y))/2,self))
        if node.y > 0:
            road_list.append(Road2D(node,0,(self.fct(node.x,node.y)+self.fct(node.x,node.y-1))/2,self))
        if node.y < (self.y-1):
            road_list.append(Road2D(node,2,(self.fct(node.x,node.y)+self.fct(node.x,node.y+1))/2,self))
        return road_list
        
def get_path(start, end, path=[]):
    if start in path: return (-1, [])
    path.append(start)
    if start == end:
        return (0, path)
    road_cost = []
    flag = 1
    best = None
    for road in start.road_list:
        new_road = get_path(road.get_end(start), end, path[:])
        (c, l) = new_road
        if c == -1: continue
        if flag or new_road[0] < best[0]:
            best = (c+road.cost(), l)
            flag = 0
    if not best: return (-1,[])
    return best

def get_all_path(nodes):
    path = (0,[])
    if len(nodes) ==0: return path
    (cp,lp) = path
    lp.append(nodes[0])
    path = (cp,lp)
    for i in range(len(nodes)-1):
        (c,l) = get_path(nodes[i],nodes[i+1],[])
        (cp,lp) = path
        lp.extend(l[1:])
        cp = cp + c
        path = (cp,lp)
    return path

def cmpfct(a,b):
    (an,ac,ap) = a
    (bn,bc,bp) = b
    if ac-bc < 0.0: return -1
    if ac-bc > 0.0: return 1
    return 0

def get_path_dijkstra(start, end):
    item = (start,0,0)
    open = [item]
    close= []
    while len(open) != 0:
        open.sort(cmpfct)
        i = open.pop(0)
        (n,c,p) = i
        close.append(i)
        if n == end: break
        for r in n.road_list:
            n2 = r.get_end(n)
            if n2 in [x for (x,y,z) in close]: continue
            cost = c+r.cost()
            t = (n2, cost, n)
            try: o = [x for (x,y,z) in open].index(n)
            except: o = -1
            if o==-1: open.append(t)
            else: open[o] = t
    try: f = [x for (x,y,z) in close].index(end)
    except: return (-1,[])
    (n, cost, p) = close[f]
    path = [n]
    while p != 0:
        f = [x for (x,y,z) in close].index(p)
        (n, c, p) = close[f]
        path.insert(0, n)
    return (cost, path)
        
    
                
            
            
        

class RoadMap(Frame):
    def createWidgets(self):
        self.canvas = Canvas(self, bg="white",width="640",height="480")
        self.canvas.pack()
    def DrawRoad(self, road):
        id = self.canvas.create_line((road.a.x+self.x)*self.zoom,(road.a.y+self.y)*self.zoom,(road.b.x+self.x)*self.zoom,(road.b.y+self.y)*self.zoom)
        if isinstance(road, BigRoad):
            self.canvas.itemconfigure(id,width=2*self.zoom,fill="#AAF")
        elif isinstance(road, HighRoad):
            self.canvas.itemconfigure(id,width=4*self.zoom,fill="#FAA")
        else:
            self.canvas.itemconfigure(id,width=1*self.zoom,fill="#AFA")
    def DrawTown(self, town):
        w = 6
        id = self.canvas.create_oval((town.x-w+self.x)*self.zoom,(town.y-w+self.y)*self.zoom,(town.x+self.x+w)*self.zoom,(town.y+self.y+w)*self.zoom,fill="#F77")
        
    def DrawMap(self,town,road):
        for r in road:
            self.DrawRoad(r) 
        for t in town:
            self.DrawTown(t)
    def DrawPath(self, town):
        for i in range(len(town)-1):
            id = self.canvas.create_line((town[i].x+self.x)*self.zoom,(town[i].y+self.y)*self.zoom,(town[i+1].x+self.x)*self.zoom,(town[i+1].y+self.y)*self.zoom)
        
    def SetPos(self, x, y, zoom):
        self.x = x
        self.y = y
        self.zoom = zoom
    def __init__(self, master=None):
        Frame.__init__(self, master)
        self.pack(fill=BOTH, expand=1)
        self.createWidgets()
        self.x = 0
        self.y = 0
        self.zoom = 2

def mapfct(x, y):
    sin(x)+cos(y)

a = Node(20 ,  0,"a")
b = Node(20 , 20,"b")
c = Node(40 , 10,"c")
d = Node(40 , 40,"d")
e = Node(10 , 30,"e")
f = Node(0  , 10,"f")
g = Node(70 , 10,"g")
h = Node(100, 40,"h")
i = Node(130, 20,"i")
j = Node(110,  0,"j")
k = Node(140, 40,"k")
town = [a,b,c,d,e,f,g,h,i,j,k]
road = []
road.append(Road(a,b))
road.append(Road(a,c))
road.append(Road(a,f))
road.append(BigRoad(b,c))
road.append(Road(b,f))
road.append(Road(b,e))
road.append(Road(b,d))
road.append(HighRoad(b,i))
road.append(BigRoad(c,g))
road.append(Road(e,f))
road.append(Road(g,j))
road.append(BigRoad(g,h))
road.append(BigRoad(h,i))
road.append(Road(i,j))
road.append(Road(i,k))

print "-------------"
#bestroad = get_all_path([a,j])
bestroad = get_path_dijkstra(a,j)
#bestroad = get_path(b,i)
(cost, list) = bestroad
print "cost : " + Cost2Str(cost)
print "path : " + Path2Str(list)

app = RoadMap()
app.SetPos(50,50,3)
app.DrawMap(town,road)
app.DrawPath(list)
app.mainloop()

##    sroad = "road "+start.name+": "
##    for road in start.road_list:
##        sroad = sroad + road.get_end(start).name + ","
##    print sroad
##    spath = "path : "
##    for town in path:
##        spath = spath + town.name + " => "
##    print spath

Conclusion :

j'ai la meme chose en mieux en C, mais comme d'hab, faut que je prenne le temps d'aller le deposer sur cppfrance.

A voir également

Ajouter un commentaire

Commentaires

Messages postés
179
Date d'inscription
mercredi 13 octobre 2004
Statut
Membre
Dernière intervention
21 mai 2014
1
LOL, c'est vrai, ca fait déjà deux ans que l'on traine sur pythonfrance.... :D
Messages postés
95
Date d'inscription
mercredi 5 décembre 2001
Statut
Membre
Dernière intervention
27 juin 2006

je n'avais pas vu cette source depuis 2ans, j'viens de la relire et ça me parait toujours transparent a quelques exception prés :
- dans la classe road apparement holdup ne sert à rien si ce n'est à vous empecher de comprendre la source trop facilement :P
- vous faites pas avoir par les couleurs "open" n'est pas un mot clé (dans l'algo de dijkstra, c'est la liste des chemins que l'on est en train de parcourir)
Messages postés
6
Date d'inscription
mardi 23 mars 2004
Statut
Membre
Dernière intervention
4 novembre 2008

Slt!

Il est vrai que ce code pourrait etre utile s'il était commenté...
Tu aurais pu au moins mettre à quoi corresponde les classes et leurs méthodes.

Au final, ton code aurait été plus simplement lisible...
Messages postés
179
Date d'inscription
mercredi 13 octobre 2004
Statut
Membre
Dernière intervention
21 mai 2014
1
creer un topic sur le forum ce n'est pas le bon endroit pour poser ta question
Messages postés
188
Date d'inscription
mercredi 9 avril 2003
Statut
Membre
Dernière intervention
10 août 2009

bonjour, je debute en python. Je viens du monde C/C++ (plutot C++) et je cherche a savoir s'il est possible de surcharger le constructeur __init__.
A premiere vue oui vu que le parser ne me detecte aucune erreur. Seulement a l'execution, j'ai des problemes : il m'appelle toujours la derniere fonction declarée... Comment qu'on fait svp ?
Afficher les 9 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.