#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
import heapq
from linked_lists import Cons, Nil, member
from romanian_cities import graph
# horni zavora pro cenu nejlepsi cesty
biggest = 9999
def best_search(start):
heap = [(0, 0, start, Nil)]
while True:
try:
f, g, node, path = heapq.heappop(heap)
except IndexError: # fronta je prazdna
break
path1 = Cons(node, path)
if is_goal(node):
yield (f, path1)
if f <= biggest:
for m, c in move_anyYC(node):
if not member(m, path1):
heapq.heappush(heap, (g+c+h(m), g+c, m, path1))
def is_goal(x):
# zavisi na resenem problemu
return x == "Bukurest"
def move_anyYC(x):
# zavisi na resenem problemu
if x in graph:
for y, c in graph[x][0]:
yield (y, c)
def h(x):
# zavisi na resenem problemu
return graph[x][1]
# demonstracni vypis
if __name__ == "__main__":
print("Best-First Search (algoritmus A*) - implementace pomoci prioritni fronty")
print("Veskere jednoduche cesty mezi mesty Arad a Bukurest serazene vzestupne podle ceny:")
for solution in best_search('Arad'):
print(solution)
Best-First Search (algoritmus A*) - implementace pomoci prioritni fronty
Veskere jednoduche cesty mezi mesty Arad a Bukurest serazene vzestupne podle ceny:
(418, ['Bukurest', 'Pitesti', 'Rimnicu_Vilcea', 'Sibiu', 'Arad'])
(450, ['Bukurest', 'Fagaras', 'Sibiu', 'Arad'])
(575, ['Bukurest', 'Pitesti', 'Rimnicu_Vilcea', 'Sibiu', 'Oradea', 'Zerind', 'Arad'])
(605, ['Bukurest', 'Pitesti', 'Craiova', 'Rimnicu_Vilcea', 'Sibiu', 'Arad'])
(607, ['Bukurest', 'Fagaras', 'Sibiu', 'Oradea', 'Zerind', 'Arad'])
(733, ['Bukurest', 'Pitesti', 'Craiova', 'Dobreta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad'])
(762, ['Bukurest', 'Pitesti', 'Craiova', 'Rimnicu_Vilcea', 'Sibiu', 'Oradea', 'Zerind', 'Arad'])
(838, ['Bukurest', 'Pitesti', 'Rimnicu_Vilcea', 'Craiova', 'Dobreta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad'])
(1030, ['Bukurest', 'Fagaras', 'Sibiu', 'Rimnicu_Vilcea', 'Craiova', 'Dobreta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad'])
(1109, ['Bukurest', 'Fagaras', 'Sibiu', 'Rimnicu_Vilcea', 'Pitesti', 'Craiova', 'Dobreta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad'])
|