Skip to content

Lab 3: Informed Search

Lab learning outcomes

After completing this lab, the students are able to

  • create Python script to execute an informed search algorithm to solve a search problem.

Nick's route-finding problem in Romania

The search problem we are focusing on for this lab is Nick’s route-finding problem in Romania, starting in Arad to reach Bucharest. The road map of Romania, which is the state space of the problem is given as follows:

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

Write a Python script to solve the problem with greedy-best-first search algorithm. In the process of writing the script, answer the following quesetions.

  1. Explain the logical flow of the transition model.

  2. What is a reasonable heuristic function for this problem?

  3. What is/are the difference(s) between breadth-first search algorithm and greedy-best-first search? How would these differences be reflected in the script?

  4. Explain the logical flow of sorting the frontier for node expansion.

  5. Explain the logical flow of identifying the solution when the goal node is found.

Report

Submit a written report that describes the considerations while writing the scripts, the answers to the above questions, and the problems you encountered in the process. Include your script in the written report as an appendix.