AI Problem Solving Part 2 PDF

By Dr. Mohamed Kazim Khalil Solve problems using Breadth-First Search. Solve problems using Depth-First Search. Differentiate between BFS and DFS. Solve problems using Uniform-cost search. Breadth-First Search (BFS)  What is Breadth-First Search (BFS)? BFS is the most...

By Dr. Mohamed Kazim Khalil Solve problems using Breadth-First Search. Solve problems using Depth-First Search. Differentiate between BFS and DFS. Solve problems using Uniform-cost search. Breadth-First Search (BFS)  What is Breadth-First Search (BFS)? BFS is the most common search strategy for traversing a tree or graph. Breadth-First Search of a graph uses Queue data structure to store nodes. This algorithm searches breadthwise in a tree or graph, so it is called breadth-first search.  What is Breadth-First Search (BFS)? BFS goes through the tree level by level, visiting all of the nodes on the top level first, then all the nodes on the second level, and so on. BFS is known as a complete algorithm since no matter how deep the goal is in the tree it will always be located.  How BFS works?  Storing the frontier [‫ ]الحدودية‬nodes in a queue creates the level- by-level pattern of a breadth-first search.  Child nodes are searched in the order they are added to the frontier.  The nodes on the next level are always behind the nodes on the current level. How BFS works?  Note... What is Frontier list?  The Frontier list, also known as the Open list, is a key component in search algorithms, particularly in pathfinding and graph traversal algorithms like A*, Best-First Search, and others.  It is a collection of nodes that have been discovered but not yet fully explored. The algorithm uses this list to keep track of which nodes to evaluate next.  The Frontier list allows the algorithm to systematically explore the graph or search space by expanding nodes in a controlled manner.  It helps ensure that the search focuses on the most promising nodes first.  An example of BFS The breadth first search traversal order of the above graph is: A, B, C, D, E, F Depth-First Search (DFS) What is Depth-First Search (DFS)? Depth-first search is one of the commonly used search algorithms. Depth-first search is an algorithm for traversing or searching tree or graph data structures. Depth-First Search of a graph uses Stack data structure to store nodes.  What is Depth-First Search (DFS)? The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. So, the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally, print the nodes in the path. What is Depth-First Search (DFS)? Depth-first search: Given that one path is as good as any other, one way to find a path is to pick one of the children at every node visited, and to work forward from that child. Depth-first search follows each path to its greatest depth before moving on to the next path. What is Depth-First Search (DFS)? Depth-first search uses a method called chronological backtracking [‫الزمنى‬ ‫]التراجع التسلسلى‬ to move back up the search tree once a dead end has been found. Depth-first search is not considered a complete algorithm since searching an infinite branch in a tree can go on forever. In this situation, an entire section [‫ ]قسم كامل‬of the tree would be left un-inspected.  How DFS works?  Frontier nodes stored in a stack create the deep dive of a depth-first search.  Nodes added to the frontier early on can expect to remain in the stack while their sibling’s children (and their children, and so on) are searched. How DFS works?  An example of DFS The depth first search traversal order of the above graph is: A, B, E, F, C, D  Comparison of DFS and BFS Scenario Depth first Breadth first Some paths are extremely long, or Performs badly Performs well even infinite. All paths are of similar length. Performs well Performs well All paths are of similar length, and Performs well Wasteful of time and all paths lead to a goal state. memory High branching factor. Performance Performs poorly depends on other factors Uniform-cost search  What is Uniform-cost search? Uniform-cost search (UCS) is an uninformed search algorithm that explores nodes in a graph based on the lowest cumulative cost, aiming to find the most cost- efficient path from the source to the destination. UCS helps us find the path from the starting node to the goal node with the minimum path cost. The UCS approach uses a priority queue to facilitate its implementation.  How UCS works? Considering the scenario that C we need to move from point 3 2 A to point B. 7 A B  The path cost of going from path A to path B is 7,  and the path cost of path A to C to B is (3+2=5).  As UCS will consider the least path cost, that is, 5; hence, (A to C to B) would be selected in terms of uniform cost search.  How UCS works? Explanation:  Frontier list will be based on the priority queue. Every new node will be added at the end of the list and the list will give priority to the least cost path.  The node at the top of the frontier list will be added to the expand list, which shows that this node is going to be explored in the next step. It will not repeat any node. If the node has already been explored, you can discard it.  Explored list will be having the nodes list, which will be completely explored.  An example of a UCS Consider the following graph. Let the starting node be A and the goal node be G. 5 B A 1 4 C 3 6 2 D E 8 4 2 3 G F  An example of a UCS Implementation: Current Priority Queue Explored List [ (A,0) ] (A,0) [ (A-D,3) , (A-B,5) ] [A] (A-D,3) [ (A-B,5) , (A-D-E,5) , (A-D-F,5) ] [A, D] (A-B,5) [ (A-D-E,5) , (A-D-F,5) , (A-B-C,6) ] [A, D, B] [ (A-D-F,5) , (A-B-C,6) , (A-D-E-B,9) ] (A-D-E,5) [A, D, B, E] B is already explored (A-D-F,5) [(A-B-C,6) , (A-D-F-G,8)] [A, D, B, E, F] [(A-D-F-G,8) , (A-B-C-E,12) , (A-B-C-G,14)] (A-B-C,6) [A, D, B, E, F] E is already explored (A-D-F-G,8) - [A, D, B, E, F, G] Actual path => A - D - F - G , with Path Cost = 8 Traversed path => A - D - B - E - F - C - G ‫وباهلل التوفيق‬