Accueil > > > RECHERCHE DE CHEMIN OPTIMUM
RECHERCHE DE CHEMIN OPTIMUM
Information sur la source
Description
ça recherche le meillieur chemin. ça peut toujours servir.
Source
- #! /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
#! /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.
Sources du même auteur
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Recherche de chaine [ par DoudouBidou ]
Bonjour, je souhaite faire une recherche de chaine dans un texte et je pense que le module a utilisé est re mais j'ignore comment. Je voudrais
Comment créer des screenshots sous un dédié ? [ par Chrisvip ]
Bonsoir,Comme je fais un moteur de recherche, j'ai besoin de faire des screens, malgré qu'il y a des services sur le web (toujours un défaut), j'aimer
Développement particulier [ par davidoff73 ]
Bonjour, <p class="MsoNormal" st
Module de recherche de Yahoo [ par Jideone ]
Salut tout le monde,Y'a t-il quelqu'un dans ce forum qui a deja utilise le module de recherche de yahoo "pYsearch"?merci
Afficher l'explorateur windows pour recup chemin dans variable [ par stephane70 ]
Bonjour à tous, je cherche à placer un chemin de fichier dans une variable python à partir de l'explorateur windows. En gros, j'utilise Tkinter et un
Recherche développeur Python [ par jmvl ]
Nous sommes une société d'informatique spécialisé dans le développement d'application pour grandes entereprises. Dans le cadre d'une de nos missions,
decompression dossier comprenant quatres fichiers et les concaténé [ par yyouce ]
Bonjourje suis le néant dans python, je commence juste a m'interesser et je suis amateur.mon problème est le suivant:je télécharge depuis internet un
Nulle en python ,je vous prie de m'aider [ par sawulia ]
Salut! Je suis très nulle en prog, et j'ai un devoir à rendre en progra, il faut faire le jeux master mind.Est ce que quelqu'un peux corriger ma fonc
chemin le plus court dans un graphe [ par molly59 ]
Bonjour, j'ai besoin de quelques conseils pour un travail en python sur un graphe. Nous devions faire une fonction qui donner tous les chemins qui
recherche pour connexion à un site + telechargement [ par newss ]
bonjour je debute dans la programmation, recherche pour apprendre a acceder à un site via python et pouvoir telecharger un texte ci trouvant, voir me
|
Derniers Blogs
IMAGINE CUP 2012, MAKE A SIGN EN FINALEIMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg
Voilà qui est fait, la nouvelle est officielle ! L'équipe belge "Make a Sign" va au pays des kangourous défendre son projet dans la catégorie Software Design. http://www.imaginecup.com/CompetitionsContent/Competition/WorldwideFinalists.aspx V...
Cliquez pour lire la suite de l'article par junarnoalg KINECT 1.5 IS OUT !KINECT 1.5 IS OUT ! par Vko
La version 1.5 du Kinect For Microsoft vient tout juste de sortir ! Plein de nouveautés: Tracking de squelette en Near Mode Détection en position assise Détection faciale avec un SDK dédié Documentation et des guideline (enfin) Un out...
Cliquez pour lire la suite de l'article par Vko LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc
Mise à jour des Web API du 14 Mai
Réservez dès maintenant votre journée du 20 juin pour le Windows Azure Dev Camp 2012 à Paris
Mise à jour de Team Foundation Service
MechCommander 2 sur Windows 8
Entity Framework 5 Release Candidate e...
Cliquez pour lire la suite de l'article par richardc REACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITERREACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITER par Groc
Une mauvaise utilisation de rx lors de l'écriture d'une couche d'accès à des services peut conduire à des cas embarassants avec des erreurs mal gérées, des appels qui ne partent lorsqu'ils le devraient, et même des résultats incorrects . le tout nuis...
Cliquez pour lire la suite de l'article par Groc SHAREPOINT BLOG SITE, PROBLèME D'ARCHIVESSHAREPOINT BLOG SITE, PROBLèME D'ARCHIVES par junarnoalg
Dernièrement, nous avons migré le site
myTIC
vers un nouveau serveur SharePoint 2010. Dans les contenus que nous vouloins récupérer, nous avions un certain nombre de blogs.
Nous avons utilisé les commandes Power...
Cliquez pour lire la suite de l'article par junarnoalg
Logiciels
974 Application Server (12.2.4.0)974 APPLICATION SERVER (12.2.4.0)Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc... Cliquez pour télécharger 974 Application Server vPicture (1.4.2.1)VPICTURE (1.4.2.1)Avec vPicture, hébergez vos images facilement et rapidement.
vPicture est un utilitaire simple, ... Cliquez pour télécharger vPicture Easy-Planning (2.2.1.6)EASY-PLANNING (2.2.1.6)Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au... Cliquez pour télécharger Easy-Planning COM-BACKUP (2.0)COM-BACKUP (2.0)
COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...
Cliquez pour télécharger COM-BACKUP mySongBook Player (1.0.0)MYSONGBOOK PLAYER (1.0.0)mySongBook Player est un logiciel gratuit permettant l'accès à une archive de tablatures/partitio... Cliquez pour télécharger mySongBook Player
|