Iterative Deepening Search: Solutions and Applications
Explore the concepts of Iterative Deepening Search, including in-depth solutions and practical applications. Gain insights into various graph traversal techniques like Breadth-First Search, Depth-First Search, and more. Learn about advantages, disadvantages, and spanning tree solutions using these algorithms.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Tutorial -1 COURSE: CS60045 Pallab Dasgupta Professor, Dept. of Computer Sc & Engg 1 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Apply DFBB on the following graph 1 E A 3 2 START 4 5 S -4 1 B G D GOAL 6 2 8 3 C
Solution C* = -> 6-> 3 OPEN (S,0) (A,3)(B,6)(C,8) (E,4)(B,6)(C,8) (G,6)(D,9)(B,6)( C,8) (D,9)(B,6)(C,8) (B,6)(C,8) (D,2)(C,8) (G,3)(C,8) (C,8) CLOSED (S,0) (S,0)(A,3) (S,0)(A,3)(E,4) Note that the best cost is 6 here. Considering a strict less than comparison with the path cost will prune all entries in OPEN including (D,9),(B,6), (C,8) without further expansion. (S,0)(A,3)(E,4)(G,6) (S,0)(A,3)(E,4)(G,6)(D,9) (S,0)(A,3)(E,4)(G,6)(B,6) (S,0)(A,3)(E,4)(B,6)(D,2) (S,0)(A,3)(E,4)(B,6)(D,2)(G,3) (S,0)(A,3)(E,4)(B,6)(D,2)(G,3)(C,8) Terminate
Apply DFBB on the following graph 1 E A 3 -2 2 START 4 5 S -4 1 B G D GOAL 6 2 8 3 C
Solution C*= ->6->3->1-> OPEN (S,0) (A,3)(B,6)(C,8) (E,4)(B,6)(C,8) (G,6)(D,9)(B,6)(C,8) (D,9)(B,6)(C,8) (B,6)(C,8) (D,2)(C,8) (A,0)(G,3)(C,8) (B,4)(E,1)(G,3)(C,8) (D,0)(E,1)(G,3)(C,8) (A,-2)(G,1)(E,1)(C,8) . . CLOSED (S,0) (S,0)(A,3) (S,0)(A,3)(E,4) (S,0)(A,3)(E,4)(G,6) (S,0)(A,3)(E,4)(G,6)(D,9) (S,0)(A,3)(E,4)(G,6)(B,6) (S,0)(E,4)(B,6)(D,2) (S,0)(D,2)(A,0) (S,0)(A,0)(B,4) (S,0)(B,4)(D,0) .. ..
Iterative Deepening Search A B D C E F G H I J K GOAL 6 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Solution Depth(level) IDS 0 A 1 A,B,C,D 2 A,B,E,C,F,G,D ,H A,B,E,C,F,G,I, D,H,J,K 3 Advantages:- 1) Always finds goal node 2) Requires less memory Disadvantages:- 1)Visits same nodes again and again 7 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Perform BFS & DFS 6 1 5 4 2 7 3 8 10 9 8 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Solution BFS Spanning Tree 1 4 2 3 5 7 8 10 9 6 1,4,2,3,5,8,7,10,9,6 9 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Solution DFS Spanning Tree 1 4 3 10 2 9 8 7 1,4,3,10,9,2,8,7,5,6 5 6 10 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Sample problem on A* search Open = {S} {A,B} {B,C} {C,D} {D,E} {D,G} {G} {F,G} {S,A} {S,A,B} {S,A,B,C} {S,A,B,C,E} {S,A,B,C,E,D} {S,A,B,C,E,D,F} Closed = {} {S} 4 4 1 3 3 A C E Select : S Select : A Select : B Select : C Select : E Select : D Select : F Select : G GOAL TERMINATE 2 2 0 6 Node S A B C D E F G g() 0 2 3 5 4 6 5 7 7 8 f() 1 1 G S 6 GOAL 1 START 3 6 7 9 8 3 2 B D 3.5 F 1 4 9.5 8.5 8 8 9 8 9 11
AO* : An Example AND NODE 14 10 16 7 18 A START 2 1 OR NODE 3 7 16 8 4 6 C B 0 SOLVED NODE 1 2 0 5 7 2 14 F G H E 7 9 1 0 0 0 I L J K 3 4 10 3 12
Adversarial Search 1. Find the value returned to the root node (i) without alpha-beta pruning and (ii) alpha-beta pruning. MAX MIN MIN MAX MAX MAX MAX 4 8 9 9 3 2 -2 -1 13 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
V= 8 MAX V= 8 V= 2 MIN MIN V= 8 V= 2 V= 9 V= 9 MAX MAX MAX MAX 4 8 9 9 3 2 -2 -1 14 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
V= 8 = 8 = 8 = = 8 8 MAX 8 8 V= 2 = 8 = 8 = = 8 8 V= 8 = =- - = 8 = 8 MIN MIN 8 8 8 8 8 8 V= 9 =9 =9 =8 =8 V= 2 = 8 = 8 = = V= 8 = 8 = 8 = = MAX MAX MAX MAX 4 8 9 9 3 2 -2 -1 15 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
2. The following game trees are for a three player game. The vector <x, y, z >in each terminal node represents the payoffs for Player-1, Player-2, and Player-3 respectively. The square nodes represent moves for Player-1, the circular nodes represent moves of Player-2 and the oval nodes represent moves for Player-3. a) The three player game may assume that the opponents are rational, that is, each player s sole motive is to maximize the payoff of that player. Under this assumption, show the preferred choice of successor at each node by marking the relevant edges. P-1 P-2 P-2 P-3 P-3 P-3 P-3 <4,4,2> <6,2,2> <3,3,4> <3,4,3> <5,3,2> <4,3,3> <3,2,5> <2,2,6> 16
b) A more conservative approach for Player-1 is to choose the move without making the assumption of rational opponents. This situation allows Player-2 and Player-3 to conspire to minimize the payoff of Player-1. If this is the case, then show the preferred choice of successor at each node by marking the relevant edges. P-1 P-2 P-2 P-3 P-3 P-3 P-3 <4,4,2> <6,2,2> <3,3,4> <3,4,3> <5,3,2> <4,3,3> <3,2,5> <2,2,6> 17 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
c) Design a cut-off criterion similar to alpha-beta-pruning for the situation where Player-2 and Player-3 conspire against Player-1 to minimize the payoff for Player-1. Show the pruning on the following game tree. You don t have to state the pruning criterion. P-1 P-2 P-2 P-3 P-3 P-3 P-3 <5,3,2> <2,2,6> <3,2,5> <4,3,3> <4,4,2> <3,4,3> <6,2,2> <3,3,4> 18 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
3. Perform alpha-beta pruning of the following tree. 19 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
