Python R2


Buscando caminos con python


Uno de los problemas que me enfrente hoy era aun pequeño mapa donde yo tenía que pasarle la ciudad origen y destino  y mi py tenia que contestar con el camino mas corto posible. buscando en google encontre este link:
http://www.cruzrojaguayas.org/inteligencia/B%FAsqueda%20respaldados%20con%20informaci%F3n.htm

y basándome en el ejemplo de Algoritmo A* hice esto.

Mapa

Mapa

Acá un mapa con las ciudades. (Perdón por mi ignorancia geográfica) 🙂

Y acá el script.

#!/usr/bin/env python
#Archivo: buscadorDecaminos.py
from mapa import Puntos, Mapa

mapa    = Mapa()
mapa.add(Puntos("Capital Federal"))
mapa.add(Puntos("Santa Fe"))
mapa.add(Puntos("Rosario"))
mapa.add(Puntos("Parana"))
mapa.add(Puntos("San Luis"))
mapa.add(Puntos("Cordoba"))
mapa.add(Puntos("Mendoza"))
mapa.add(Puntos("Tucuman"))

mapa.puntos["Capital Federal"].add(mapa.puntos["Rosario"],320)
mapa.puntos["Capital Federal"].add(mapa.puntos["Cordoba"],716)
mapa.puntos["Rosario"].add(mapa.puntos["Parana"],175)
mapa.puntos["Rosario"].add(mapa.puntos["Santa Fe"],150)
mapa.puntos["Rosario"].add(mapa.puntos["Cordoba"],398)
mapa.puntos["Santa Fe"].add(mapa.puntos["Parana"],29)
mapa.puntos["Cordoba"].add(mapa.puntos["Tucuman"],534)
mapa.puntos["Cordoba"].add(mapa.puntos["Mendoza"],617)
mapa.puntos["Cordoba"].add(mapa.puntos["San Luis"],413)

print "Capital Federal -> Parana:",mapa.camino("Capital Federal","Parana")
print "Capital Federal -> San Luis:",mapa.camino("Capital Federal","San Luis")
print "Tucuman         -> Capital Federal:",mapa.camino("Tucuman","Capital Federal")
print "Tucuman         -> Mar del plata  :",mapa.camino("Tucuman","MDQ")

y aca el modulo mapa

#!/usr/bin/env python
#Archivo: mapa.py
class Puntos:
    def __init__(self,nombre):
        self.relaciones = {}
        self.nombre = nombre
        self.max = 0

    def add(self,p,d,b = True):
        self.relaciones[p.nombre] = [p,d]
        if b: p.add(self,d,False)

    def caminoA(self,hasta,recorrido=0,recorridas=[],camino=[]):

        minimo = None;

        if hasta == self.nombre:
            return  [recorrido,[self.nombre]] # estoy en la ciudad wiiiiiii

        recorridas.append(self.nombre)      # pase por aca
        nodosHijos = filter(lambda x:not x in recorridas, self.relaciones) #mis hijos por los cuales no pase son
        if nodosHijos == []: return ["Fallo","Fallo"] # 😦 no llegue a ningun lado

        for p in nodosHijos:
            datos = self.relaciones[p][0].caminoA(hasta,self.relaciones[p][1],recorridas)
            if (datos[0] != "Fallo") and  (datos[0] < minimo or minimo == None):
                minimo = datos[0]
                nodoElegido = datos[1]

        try: # si no existe nodoElegido
            nodoElegido.insert(0, self.nombre)
        except: # Fallo
            return ["Fallo","Fallo"]

        return [recorrido + minimo,nodoElegido]

class Mapa:
    def __init__(self):
        self.puntos = {}

    def add(self,p):
        self.puntos[p.nombre]=p

    def camino(self,desde,hasta):
        return self.puntos[desde].caminoA(hasta,0,[],[])

La salida es:

>>>
Capital Federal -> Parana: [495, ['Capital Federal', 'Rosario', 'Parana']]
Capital Federal -> San Luis: [1129, ['Capital Federal', 'Cordoba', 'San Luis']]
Tucuman         -> Capital Federal: [1250, ['Tucuman', 'Cordoba', 'Capital Federal']]
Tucuman         -> Mar del plata  : ['Fallo', 'Fallo']
>>>

Como siempre espero que les guste y les sirva

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: