[Tutor] help

Sat, 30 Dec 2000 13:48:41 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
"""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)
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

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:
if not textline:  break
name = string.capwords(string.strip(textline))
sc = sc + 1
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

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
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

```