[Tutor] please!!!!!!!!!!!!!!
MUSAJADAKISS@aol.com
MUSAJADAKISS@aol.com
Sat, 30 Dec 2000 13:48:15 EST
can you help me in debugging this to do an a* search although there is no
heuristic distance measured but just put any figure there on the textfile
pleasee happy newyear
"""An implementation of A*.
Given a start state and a goal state, as well as a heuristic function
h(m), return the shortest path between start and goal.
In the algorithm, we keep a priority queue, and continuously look at
the element with the lowest heuristic cost f(m).
We define f(m) = g(m) + h(m), where g(m) is the cost from the start
state to m, and h(m) is the heuristic from m to the goal state.
"""
def myMin(L, f):
"""Return the index of the minimal element, using f to calculate
the cost."""
if len(L) == 0: return None
index = 0
minCost = f(L[index])
for i in range(1, len(L)):
if f(L[i]) < minCost:
index = i
mincost = f(L[i])
return index
class Node:
def __init__(self, name, distance_func):
self.name = name
self.distance_func = distance_func
self.predecessor = None
self.neighbors = []
def f(self):
return self.g() + self.h()
def g(self):
if self.getPred() in [None, self]: return 0
return (self.distance_func(self, self.getPred())
+ self.getPred().g())
def h(self):
return 0 # the heuristic cost from self to the goal
def __str__(self):
return self.name
def __repr__(self): return str(self)
def getName(self): return self.name
def getPred(self): return self.predecessor
def setPred(self, value): self.predecessor = value
def getNeighbors(self): return self.neighbors
def setNeighbors(self, neighbors): self.neighbors = neighbors
class DistanceDictWrapper:
def __init__(self, dict):
self.dict = dict
def __call__(self, m, n):
"""Return the distance between m and n. Since distance is symmetric,
we'll try from m->n, or n->m"""
if m == n: return 0
if self.dict.has_key((m.name, n.name)):
return self.dict[(m.name, n.name)]
if self.dict.has_key((n.name, m.name)):
return self.dict[(n.name, m.name)]
return None
def aStarSearch(nodes, start, goal):
start.predecessor = start
pqueue = [start]
while 1:
next_choice_index = myMin(pqueue, lambda n: n.f())
next_choice = pqueue[next_choice_index]
## print "queue:", pqueue # debug
## print "choosing", next_choice, next_choice.f() # debug
del pqueue[next_choice_index]
if next_choice == goal: break
_updatePqueue(next_choice, pqueue)
path = _resultHelper(nodes, start, goal)
_resetPredLinks(nodes)
return path
def zeroFunc(): return 0
def _resultHelper(nodes, start, goal):
result = [goal]
node = goal
while node != start:
node = node.predecessor
result.append(node)
result.reverse()
return result
def _resetPredLinks(nodes):
for x in nodes: x.setPred(None)
def _updatePqueue(parent, pqueue):
children = parent.getNeighbors()
for x in children:
if (x.predecessor is None or
parent.g() + x.distance_func(parent, x) < x.g()):
x.predecessor = parent
pqueue.append(x)
def main():
"TUBEREAD : Main line!"
global citysign, NL
args = sys.argv[:] ## gets command-line arguments
na = len(args)
print args[0],"[version 1.0]"
print "command-line args. =",na
if na < 2:
print "normal usage: python tuberead.py <textfile>"
args.append(raw_input("please give input textfile name: "))
na = len(args)
textname = args[1]
textfile = open(textname,"r")
if textfile == None:
print "Can't open file:",textname
lc = 0 ; sc = 0
lines = {} ## empty dictionary (station names)
citylist = [] ## empty list (line names)
thisline = "Zonk"
citydic = {}
while 1:
textline = textfile.readline()
if not textline: break
name = string.capwords(string.strip(textline))
sc = sc + 1
if citysign in name:
newline = 1
print "city = ", name
thiscity = string.replace(name,citysign,'')
if not citydic.has_key(thiscity):
citydic[thiscity] = []
## citylist.append(thiscity)
else:
x = string.split(name,',')
##print x
c = x[0]
##print c
if not citydic.has_key(c):
lc = lc + 1
citydic[c] = []
d = eval(x[1])
t1 = (c,d)
citydic[thiscity].append(t1)
## also append symmetric link :
t2 = (thiscity,d)
citydic[c].append(t2)
citylist = citydic.keys()
citylist.sort()
print citylist
print
print
print len(citylist),"distinct cities read."
print
##print citydic
while 1:
sn = raw_input("Enter city name: ")
sn = string.strip(sn)
if len(sn) < 1: break ## user hits CRLF to quit loop
sd = raw_input("Enter destination city name: ")
if len(sd) < 1: break ## user hits CRLF to quit loop
sl = citydic.get(sn,[])
ra = len(sl)
st = citydic.get(sd,[])
mu = len(st)
print sn,sl,ra
print sd,st,mu
citylist = textfile.readline()
dfunc = DistanceDictWrapper(citylist)
sq = Node(sn, dfunc)
sq.setNeighbors([sn,sd])
node = {}
print aStarSearch(sq,sn,node)
return 0
if __name__ == '__main__':
try:
main()
except KeyboardInterrupt:
sys.exit(1)
this is the textfile
just put any second figure as the hueristic distance
Amsterdam:123
Berlin,650
Brussels,197
Calais,367
Cologne,256
Edinburgh,1093
Hamburg,447
Paris,510
Athens:123,124
Sofia,828,857
Belfast:
cork,416
Dublin,167
Kilkenny,277
Berlin:
Edinburgh,1696
Hamburg,285
Prague,345
Rostock,222
Stuttgart,629
Warsaw,606
Budapest:
Burcharest,852
Prague,537
Sofia,790
Vienna,242
Cork:
Kilkenny,148
Dublin:
Cork,259
Kilkenny,119
Edinburgh,346
Edinburgh:
Copenhagen,479
Hamburg:
Rostock,175
Stuttgart,659
Istanbul:
Athens,1145
Burcharest,690
Sofia,550
London:
Brussele,333
Dublin,430
Cologne,508
Edinburgh,608
Paris,399
Madrid:
Bercelona,617
Lisbon,651
Paris,1280
Munich:
Berlin,594
Cologne,580
Frankfurt,398
Paris,810
Parague,388
Vienna,430
Oslo:
Copenhagen,590
Hamburg,900
stocholm,530
Paris:
Brussels,320
Cologne,495
Prague:
Frankfurt,512
Hamburg,652
Oslo,1350
Warsaw,616
Vienna,295
Rome:
Athens,1140
Milan,606
Vienna:
Berlin,640
Warsaw,727
Warsaw:
Moscow,1245
Zurich:
Milan,292
Munich,303
Paris,592
Vienna,743