Chapter-3-Cvml-part-2.pptx This is About un informed cost techniques in Artificial intelligence

This is About un informed cost techniques in Artificial intelligence

1. Uniform-cost search Unlike BFS, this uninformed search explores nodes based on their path cost from the root node. It expands a node n having the lowest path cost g(n), where g(n) is the total cost from a root node to node n. Uniform-cost search is significantly different from the breadth-first search because of the following two reasons: First, the goal test is applied to a node only when it is selected for expansion  not when it is first generated  because the first goal node which is generated may be on a suboptimal path. Secondly, a goal test is added to a node, only when a better/ optimal path is found. Thus, uniform-cost search expands nodes in a sequence of their  optimal path cost  because before exploring any node, it searches the optimal path. Also , the step cost is positive so, paths never get shorter when a new node is added in the search.

2. Depth-First Iterative Deeping

3. Introduction The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found. This algorithm performs depth-first search up to a certain " depth limit ", and it keeps increasing the depth limit after each iteration until the goal node is found. This Search algorithm combines the benefits of Breadth-first search's fast search and depth-first search's memory efficiency. The iterative search algorithm is useful for uninformed search when search space is large, and depth of goal node is unknown.

4. Example

5. Example

6. BIDIRECTIONAL SEARCHES

7. The main idea behind bidirectional searches is to reduce the time taken for search drastically . Bidirectional search algorithm runs two simultaneous searches, one form initial state called as forward-search and other from goal node called as backward-search , to find the goal node. Bidirectional search replaces one single search graph with two small subgraphs in which one starts the search from an initial vertex and other starts from goal vertex. The search stops when these two graphs intersect each other. Bidirectional search can use search techniques such as BFS, DFS, DLS, etc.

8. This can be simplified by the following example…. Step 1 : Say, 1 is the initial node and 16 is the goal node, and 9 is the intersection node. Step 2 : We will start searching simultaneously from start to goal node and backward from goal to start node. Step 3 : Whenever the forward search and backward search intersect at one node, then the searching stops.

9. Advantages: Bidirectional search is fast. Bidirectional search requires less memory Disadvantages: Implementation of the bidirectional search tree is difficult. In bidirectional search, one should know the goal state in advance.

10. Completeness:  Bidirectional Search is complete if we use BFS in both searches. Time Complexity:  Time complexity of bidirectional search using BFS is  O( b d ) . Space Complexity:  Space complexity of bidirectional search is  O( b d ) . Optimal:  Bidirectional search is Optimal.