graph = {
'Arad': [('Zerind', 75), ('Sibiu', 140), ('Timisoara', 118)],
'Zerind': [('Arad', 75), ('Oradea', 71)],
'Oradea': [('Zerind', 71), ('Sibiu', 151)],
'Sibiu': [('Arad', 140), ('Oradea', 151), ('Fagaras', 99), ('Rimnicu Vilcea', 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 Vilcea', 146), ('Pitesti', 138)],
'Rimnicu Vilcea': [('Sibiu', 80), ('Craiova', 146), ('Pitesti', 97)],
'Fagaras': [('Sibiu', 99), ('Bucharest', 211)],
'Pitesti': [('Rimnicu Vilcea', 97), ('Craiova', 138), ('Bucharest', 101)],
'Bucharest': [('Fagaras', 211), ('Pitesti', 101), ('Giurgiu', 90), ('Urziceni', 85)],
'Giurgiu': [('Bucharest', 90)],
'Urziceni': [('Bucharest', 85), ('Hirsova', 98), ('Vaslui', 142)],
'Hirsova': [('Urziceni', 98), ('Eforie', 86)],
'Eforie': [('Hirsova', 86)],
'Vaslui': [('Urziceni', 142), ('Iasi', 92)],
'Iasi': [('Vaslui', 92), ('Neamt', 87)],
'Neamt': [('Iasi', 87)]
}
h = {
'Arad': 366, 'Zerind': 374, 'Oradea': 380, 'Sibiu': 253,
'Timisoara': 329, 'Lugoj': 244, 'Mehadia': 241, 'Drobeta': 242,
'Craiova': 160, 'Rimnicu Vilcea': 193, 'Fagaras': 176,
'Pitesti': 100, 'Bucharest': 0, 'Giurgiu': 77, 'Urziceni': 80,
'Hirsova': 151, 'Eforie': 161, 'Vaslui': 199, 'Iasi': 226,
'Neamt': 234
}
def ida_star(graph, start, goal, h):
def dfs(node, path, g, threshold):
f = g + h[node]
if f > threshold:
return f, None
if node == goal:
return f, path
minimum = float('inf')
for neighbor, cost in graph.get(node, []):
if neighbor not in path:
t, result = dfs(neighbor, path + [neighbor], g + cost, threshold)
if result:
return t, result
if t < minimum:
minimum = t
return minimum, None
threshold = h[start]
path = [start]
while True:
t, result = dfs(start, path, 0, threshold)
if result:
return result
if t == float('inf'):
return None
threshold = t
start = 'Arad'
goal = 'Bucharest'
print("IDA* solution:", ida_star(graph, start, goal, h))
0 Comments