Bfs And Ucs Algorithms. My Bfs Implementation Works But My Ucs Doesn't. Can't Figure Out Why

As long as I am not mistaken, UCS is the same as BFS with the only difference that instead of expanding the shallowest node, it expands the node with the lowest path cost. (Also us

Solution 1:

You update costMap regardless of current values. Thus you repeatedly increase cost for not yet visited common successor of previously visited and current child.

Consider this example: start from A, end in C. There are nodes chain with cost 1 for each transition: A->A1->A2->A3->A4->A5->A6->A7->A8->A9->A10. Each of A nodes leads to B with cost 3. And B leads to C. You current implementation will update B's cost several times from at least 3 nodes (A, A1, A2), even though it's real cost is 3 (A->B).

You should check if child is in costMap, compare current costMap value to new one and only push into queue if new value is better. If costMap doesn't contain child, add it to costMap and queues.

Solution 2:

it looks like you not constructing your successors correctly. you somehow got to e1 without getting there from D. i assume you are using dicts or lists. try to make your code use tuples only. this way you wont be passing around any references and muddling your code.

i would go with data that looks like below. first being the priority, second being the list of node's we have travelled and third being the next node to expand.

queue.push((2, (A, C), D))