Skip to content

Lab 3: Uniform-Cost Search

Objective

To create Python script to execute uniform cost search algorithm.

Problem to be solved

We will revisit Nick’s route-finding problem in Romania, starting in Arad to reach Bucharest, and implement uniform-cost search to solve the problem.

75 71 151 140 118 111 70 75 120 146 80 99 97 138 101 211 90 85 98 86 142 92 87 Arad Zerind Oradea Sibiu Fagaras Rimnicu Vilcea Pitesti Craiova Drobeta Mehadia Lugoj Timisoara Bucharest Giurgiu Urziceni Hirsova Eforie Vaslui Iasi Neamt

Uniform cost search changes the sorting of the frontier by ordering it with its path cost up to the leaf node and expanding the leaf node with the lowest cost.

  1. Based on the code from previous lab, add the code to sort the frontier following the path cost up to the leaf node.

  2. If a latter-found node has the same state as a previous node and the previous node has been expanded, what should be done?

  3. What happens when a latter-found node has the same state as a previous node and have a shorter path cost? How do we implement this in our code?

  4. Note also, the goal test should be applied during expansion, not generation.

Execute the program and investigate if the program is working correctly.