Applications of Search Algorithms
Uninformed Search Algorithms
For instance, DFS begins at the root node
Informed Search Algorithms
In this unit you will see some visual examples
In this numeric representation of a maze,
Given any such maze, the following function can be used to
Using BFS to Solve Maze Puzzles
# the shortest distance from the start cell to itself, zero
The function follows the standard BFS approach of
BFS successfully finds the shortest path after 10 cells visits.
This function allows the user to assign a custom weight
As expected, the BFS solver mistakenly reports the exact same path as before,
Using A* Search to Solve Maze Puzzles
The above implementation utilizes a for loop to
Similar to bfs_maze_solver( ), the above function also uses
The same happens if the neighbor has been visited before,
The results reveal that astar_maze_solver() manages to
Algorithm Comparison
BFS unweighted.
weighted version
The results are consistent with the ones reported for the small maze:
Table 2.6: Comparison of uninformed and informed algorithms
Manhattan Distance
This can be easily implemented as a python function as follows:
The results verify that the Manhattan Distance heuristic can indeed help
Table 2.7: Comparison of algorithms performance
Identify two applications of search algorithms.
Identify a difference between uninformed and informed search algorithms and mention an example of each algorithm.
Explain briefly how the A* algorithm works.
Modify your code by changing the diagonal weight from 3 to 1.5. What do you observe? Does the shortest path change for the cases of BFS and A* Search?
Modify your code by swapping the starting cell with the target cell coordinates. What do you observe? Is the path the same as before for the weighted cases of BFS and A* Search?
