Recherche de chemin optimum

Commenter

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

S'inscrire maintenant

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.

Du même auteur (Croqmort)