COS3751
Techniques of Artificial Intelligence

Assignment 3 - Q4

1. What is the difference between a tree and a graph search?

2. How does a Breadth First Search (BFS) differ from the general tree search algorithm? What is the major reason for implementing the algorithm in this way? Provide an example to aid your discussion.

3. Consider a state space where the start state is number 1, and each state k has two successors: numbers 2k and 2k + 1.

a. Draw the portion of the state space for states 1 to 15.

b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth-first search, depth-limited search with limit 3, and iterative deepening search.

c. How well would bidirectional search work on this problem? What is the branching factor in each direction of the bidirectional search?

4. Consider Figure 1 below and answer the following questions:

a. Provide the minimax values for all the nodes

b. Which move should MAX make? Explain your answer.

Figure 1 for Assignment 3 - Q4 — Figure 1

Concepts

Posts on this question's concepts

Alpha Beta Pruning

Links

https://www.youtube.com/watch?v=4E3vXPNiEG8

youtube.com 18 Nov

https://www.youtube.com/watch?v=eyXynZTshP0&t=2s

youtube.com 17 Nov

https://www.youtube.com/watch?v=-Xx0QSFYfIQ&t=3s

youtube.com 16 Nov

https://www.youtube.com/watch?v=zaBhtODEL0w

youtube.com 13 Jun

https://www.youtube.com/watch?v=TYcfywsqHgk

youtube.com 13 Jun

https://www.youtube.com/watch?v=5qr9T3w_1Tc

youtube.com 13 Jun

https://www.youtube.com/watch?v=-Xx0QSFYfIQ&t=3s

youtube.com 11 Apr

CS461 Artificial Intelligence CH03 Lecture Part 3/5: Solving Problems by Searching

youtube.com 1:11:39 Professor Hank Stalica 26 Mar

All Questions

Assignment 3 - Q4

1. What is the difference between a tree and a graph search?

2. How does a Breadth First Search (BFS) differ from the general tree search algorithm? What is the major reason for implementing the algorithm in this way? Provide an example to aid your discussion.

3. Consider a state space where the start state is number 1, and each state k has two successors: numbers 2k and 2k + 1.

a. Draw the portion of the state space for states 1 to 15.

b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth-first search, depth-limited search with limit 3, and iterative deepening search.

c. How well would bidirectional search work on this problem? What is the branching factor in each direction of the bidirectional search?

4. Consider Figure 1 below and answer the following questions:

a. Provide the minimax values for all the nodes

b. Which move should MAX make? Explain your answer.

Concepts

Posts on this question's concepts

Alpha Beta Pruning

Links

Minimax Search Algorithm

Links

Adversarial Search

Links

Uninformed Search

Links

Add Concept

Add Post

Assignment 3 - Q4

1. What is the difference between a tree and a graph search?

2. How does a Breadth First Search (BFS) differ from the general tree search algorithm? What is the major reason for implementing the algorithm in this way? Provide an example to aid your discussion.

3. Consider a state space where the start state is number 1, and each state k has two successors: numbers 2k and 2k + 1.

a. Draw the portion of the state space for states 1 to 15.

b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth-first search, depth-limited search with limit 3, and iterative deepening search.

c. How well would bidirectional search work on this problem? What is the branching factor in each direction of the bidirectional search?

4. Consider Figure 1 below and answer the following questions:

a. Provide the minimax values for all the nodes

b. Which move should MAX make? Explain your answer.

Concepts

Posts on this question's concepts

Alpha Beta Pruning

Links

Minimax Search Algorithm

Links

Adversarial Search

Links

Uninformed Search

Links