rumania.py · GitHub
Skip to content

Instantly share code, notes, and snippets.

@jdayllon

jdayllon/rumania.py

Created March 28, 2024 09:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jdayllon/af5385c39f470025512bf17085065c6d to your computer and use it in GitHub Desktop.
Save jdayllon/af5385c39f470025512bf17085065c6d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
rumania.py
"""
Problema de todos los caminos posibles para las ciudades de Rumania
Este código resuelve el problema de encontrar todos los caminos posibles desde una ciudad de origen hasta una ciudad de destino en Rumania.
Utiliza algoritmos de búsqueda en profundidad, búsqueda de costo uniforme y A* (A-star) para encontrar los caminos y determinar la ruta menos costosa y la ruta óptima.
El código original se encuentra en: https://github.com/syntnc/Artificial-Intelligence/blob/81029936ac3136324eac98f58fec5fc5dc8f77c9/IIIT-A%20Lab%20(IAIN532C)/Lab%202/romanian_paths.py
Escrito por el usuario de GitHub Sayantan @syntnc
"""
from queue import PriorityQueue
import typer
"""Problema de todos los caminos posibles para las ciudades de Rumania"""
GRAPH = {
'Arad': {'Sibiu': 140, 'Zerind': 75, 'Timisoara': 118},
'Zerind': {'Arad': 75, 'Oradea': 71},
'Oradea': {'Zerind': 71, 'Sibiu': 151},
'Sibiu': {'Arad': 140, 'Oradea': 151, 'Fagaras': 99, 'Rimnicu': 80},
'Timisoara': {'Arad': 118, 'Lugoj': 111},
'Lugoj': {'Timisoara': 111, 'Mehadia': 70},
'Mehadia': {'Lugoj': 70, 'Drobeta': 75},
'Drobeta': {'Mehadia': 75, 'Craiova': 120},
'Craiova': {'Drobeta': 120, 'Rimnicu': 146, 'Pitesti': 138},
'Rimnicu': {'Sibiu': 80, 'Craiova': 146, 'Pitesti': 97},
'Fagaras': {'Sibiu': 99, 'Bucharest': 211},
'Pitesti': {'Rimnicu': 97, 'Craiova': 138, 'Bucharest': 101},
'Bucharest': {'Fagaras': 211, 'Pitesti': 101, 'Giurgiu': 90, 'Urziceni': 85},
'Giurgiu': {'Bucharest': 90},
'Urziceni': {'Bucharest': 85, 'Vaslui': 142, 'Hirsova': 98},
'Hirsova': {'Urziceni': 98, 'Eforie': 86},
'Eforie': {'Hirsova': 86},
'Vaslui': {'Iasi': 92, 'Urziceni': 142},
'Iasi': {'Vaslui': 92, 'Neamt': 87},
'Neamt': {'Iasi': 87}
}
def dfs_paths(source, destination, path=None):
"""Todos los caminos posibles desde la fuente hasta el destino utilizando la búsqueda en profundidad
:param source: Nombre de la ciudad de origen
:param destination: Nombre de la ciudad de destino
:param path: Ruta actual recorrida (Valor predeterminado = None)
:yields: Todos los caminos posibles desde la fuente hasta el destino
"""
if path is None:
path = [source]
if source == destination:
yield path
for next_node in set(GRAPH[source].keys()) - set(path):
yield from dfs_paths(next_node, destination, path + [next_node])
def ucs(source, destination):
"""Ruta más económica desde la fuente hasta el destino utilizando la búsqueda de costo uniforme
:param source: Nombre de la ciudad de origen
:param destination: Nombre de la ciudad de destino
:returns: Costo y ruta para el recorrido más económico
"""
priority_queue, visited = PriorityQueue(), {}
priority_queue.put((0, source, [source]))
visited[source] = 0
while not priority_queue.empty():
(cost, vertex, path) = priority_queue.get()
path_string = " ↣ ".join(path)
build_output(path)
print(f"| {path_string} ({cost})")
if vertex == destination:
return cost, path
for next_node in GRAPH[vertex].keys():
current_cost = cost + GRAPH[vertex][next_node]
if not next_node in visited or visited[next_node] >= current_cost:
visited[next_node] = current_cost
priority_queue.put((current_cost, next_node, path + [next_node]))
def build_output(path):
"""Construye una cadena de salida a partir del camino
:param path: Camino hacia el destino
:returns: Cadena de salida
"""
if len(path) == 1:
print(f"{path[0]} ➡ (0)", end="")
else:
for i in range(0,len(path)-1):
print(f"[({path[i]}, {path[i+1]}) ➡ {GRAPH[path[i]][path[i+1]]}]", end="")
if i < len(path)-2:
print(" ➡ ", end="")
def a_star(source, destination):
"""Ruta óptima desde la fuente hasta el destino utilizando la heurística de distancia en línea recta
:param source: Nombre de la ciudad de origen
:param destination: Nombre de la ciudad de destino
:returns: Valor heurístico, costo y ruta para el recorrido óptimo
"""
# Valores para el Heurístico de Distancia en Línea Recta usado en la A*
straight_line = {
'Arad': 366,
'Zerind': 374,
'Oradea': 380,
'Sibiu': 253,
'Timisoara': 329,
'Lugoj': 244,
'Mehadia': 241,
'Drobeta': 242,
'Craiova': 160,
'Rimnicu': 193,
'Fagaras': 176,
'Pitesti': 100,
'Bucharest': 0,
'Giurgiu': 77,
'Urziceni': 80,
'Hirsova': 151,
'Eforie': 161,
'Vaslui': 199,
'Iasi': 226,
'Neamt': 234
}
priority_queue, visited = PriorityQueue(), {}
priority_queue.put((straight_line[source], 0, source, [source]))
visited[source] = straight_line[source]
while not priority_queue.empty():
(heuristic, cost, vertex, path) = priority_queue.get()
print("A💫", heuristic, cost, vertex, path)
if vertex == destination:
return heuristic, cost, path
for next_node in GRAPH[vertex].keys():
current_cost = cost + GRAPH[vertex][next_node]
heuristic = current_cost + straight_line[next_node]
if not next_node in visited or visited[next_node] >= heuristic:
visited[next_node] = heuristic
priority_queue.put((heuristic, current_cost, next_node, path + [next_node]))
app = typer.Typer()
@app.command()
def main(source: str = typer.Argument(..., help=f"Nombre de la ciudad de origen : {', '.join(GRAPH.keys())}"),
target: str = typer.Argument(..., help=f"Nombre de la ciudad de destino: {', '.join(GRAPH.keys())}")):
"""
Función principal que muestra los caminos posibles, la ruta menos costosa y la ruta óptima.
:param source: Nombre de la ciudad de origen
:param target: Nombre de la ciudad de destino
"""
if source not in GRAPH or target not in GRAPH:
typer.echo("Por favor, introduce una ciudad de origen y una ciudad de destino validas.")
typer.echo("Lista de ciudades disponibles:")
for city in GRAPH.keys():
typer.echo(city)
else:
print('\nCAMINOS:')
paths = dfs_paths(source, target)
for path in paths:
print(' ➡ '.join(city for city in path))
print('\nRUTA MENOS COSTOSA:')
cost, cheapest_path = ucs(source, target)
print('COSTE DE LA RUTA =', cost)
print(' ➡ '.join(city for city in cheapest_path))
print('\nRUTA OPTIMA:')
heuristic, cost, optimal_path = a_star(source, target)
print('HEURISTICA =', heuristic)
print('COSTE DE LA RUTA =', cost)
print(' ➡ '.join(city for city in optimal_path))
if __name__ == '__main__':
app()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment