[SOLVED] 41040 Introduction to Artificial Intelligence – Spring 2025 Lab 2 Classic Search Algorithms C/

Lab 2. Classic Search Algorithms

Aims: This lab provides an opportunity for you to understand how typical classic search algorithms (which are BFS, DFS, UCS, GBFS and A*) work in solving a simple navigational problem.

Tasks:

Task 1. Download the student lab2 pack from the Lab2 page, unpack the files locally and upload them to your lab2 folder in your own google drive.

Task 2. Learn from your tutor about how to “mount drive” in your notebook in order to access files in your google drive.

Task 3. Learn from your tutor about how to upload local csv files for defining the navigational problem with focus on how to find the path to these files.

Task 4. Learn from your tutor’s demo of how to create required data structure from the given data files for using the classic search algorithms.

Task 5. Learn from your tutor’s demo of how the greedy best first search (GBFS) algorithm works in solving the given navigational problem. You should be able to trace how the frontier changes in the search process and understand how the result is produced.

Task 6.  Work in a small group (pair) to do the following:

（1）Choose one from the following four algorithm:

· Breadth first search (BFS)

· Depth first search (DFS)

· Uniform. cost (UCS) search,

· A* search algorithm

（2）Run the code segments for the chosen algorithm, and

(3)   Explain how the frontier changes during the search process using the outputs, you can compare the frontier states with the ones in the illustrative examples in the file “student task.xlsx” used in the workshop 2.

Task 7. Give presentation of how your chosen algorithm solves the given problem, including your understanding of how the problem is presented, how it is passed to the algorithm function, how the algorithm works from the initialization, through looping to generate the solution or result. Explain what happens in an iteration, including the updates on the frontier, tests performed and updates on the explored set.  

Note: A heuristic function is needed when you use an informed search algorithm with heuristics, such as greedy best first and A start algorithms.

The Euclidean distance (or the line distance, or the airline distance) between a given node and the goal node is used for the heuristic function in this lab.

The Euclidean distance between two city nodes A(x₁,y₁) and B(x₂,y₂) can be calculated by using the Pythagorean Theorem, as follows: