python - BFS and UCS algorithms. My BFS implementation works but my UCS doesn't. Can't figure out why -

as long not mistaken, ucs same bfs difference instead of expanding shallowest node, expands node lowest path cost. (also using priorityqueue instead of queue that)so copied bfs code, created map keep track of each node's path cost , changed way items being pushed/popped in queue/priority queue.

note: getsuccessors(state) returns list of triples (state, action, cost)

these both of implementations:

bfs:

def breadthfirstsearch(problem):     """search shallowest nodes in search tree first."""     queue=queue()     objectqueue=queue()     visited=set()     actions=[]     flag=0     objectmap={}     actionmap={}     start=problem.getstartstate()     objectmap[start]=start     queue.push(start)     objectqueue.push(start)     if problem.isgoalstate(start):         return actions     while queue:         parent=queue.pop()         object=objectqueue.pop()         if parent in visited: continue         visited.add(parent)         if problem.isgoalstate(parent):                  while object!=start:                         action=actionmap[object]                         actions.append(action)                         object=objectmap[object]                  return actions[::-1]         children=problem.getsuccessors(parent)         child in children:                 queue.push(child[0])                 objectqueue.push(child)                 objectmap[child]=object                 actionmap[child]=child[1]         flag=1     util.raisenotdefined() 

ucs:

def uniformcostsearch(problem):     """search node of least total cost first."""     queue=priorityqueue()     objectqueue=priorityqueue()     visited=set()     actions=[]     flag=0     objectmap={}     actionmap={}     costmap={}     start=problem.getstartstate()     costmap[start]=0     objectmap[start]=start     queue.push(start, 0)     objectqueue.push(start, 0)    if problem.isgoalstate(start):         return actions    while queue:         parent=queue.pop()         object=objectqueue.pop()         if parent in visited: continue         visited.add(parent)         if problem.isgoalstate(parent):                 while object!=start:                         action=actionmap[object]                         actions.append(action)                         object=objectmap[object]                 return actions[::-1]         children=problem.getsuccessors(parent)         child in children:                 costmap[child]=costmap[object]+child[2]                 queue.update(child[0], costmap[child])                 objectqueue.update(child, costmap[child])                 objectmap[child]=object                 actionmap[child]=child[1]         flag=1      util.raisenotdefined() 

according autograder i'm provided bfs works ucs fails. here test fails @ , results:

        b1          e1        ^  \        ^  \       /    v      /    v     *a --> c --> d --> f --> [g]       \    ^      \    ^        v  /        v  /         b2          e2      start state, g goal.  arrows mark      possible state transitions.  graph has multiple     paths goal, nodes same state      added fringe multiple times before     expanded.  following section specifies search problem , solution. graph specified first set of start states, followed set of goal states, , lastly state transitions of form:   <start state> <actions> <end state> <cost>   start_state: goal_states: g 0:a->b1 b1 1.0 1:a->c c 2.0 2:a->b2 b2 4.0 b1 0:b1->c c 8.0 b2 0:b2->c c 16.0 c 0:c->d d 32.0 d 0:d->e1 e1 64.0 d 1:d->f f 128.0 d 2:d->e2 e2 256.0 e1 0:e1->f f 512.0 e2 0:e2->f f 1024.0 f 0:f->g g 2048.0  student solution:       ['1:a->c', '0:c->d', '0:e1->f'] student expanded_states:    ['a', 'b1', 'c', 'b2', 'd', 'e1', 'f', 'e2']  correct solution:       ['1:a->c', '0:c->d', '1:d->f', '0:f->g'] correct expanded_states:    ['a', 'b1', 'c', 'b2', 'd', 'e1', 'f', 'e2'] 

you update costmap regardless of current values. repeatedly increase cost not yet visited common successor of visited , current child.

consider example: start a, end in c. there nodes chain cost 1 each transition: a->a1->a2->a3->a4->a5->a6->a7->a8->a9->a10. each of nodes leads b cost 3. , b leads c. current implementation update b's cost several times @ least 3 nodes (a, a1, a2), though it's real cost 3 (a->b).

you should check if child in costmap, compare current costmap value new 1 , push queue if new value better. if costmap doesn't contain child, add costmap , queues.