Dynamic programming

Explain why underestimates are likely to result in better solutions.

a. What is the notion of dynamic programming?

b. Describe the Principle of Optimality.

Why should the A* algorithm be better than branch and bound with underestimates or branch and bound with dynamic programming?

Explain how AND/OR trees can be used to divide a search problem.

Describe how the bidirectional search works.

a. How is it different from the other techniques discussed in the chapter?

b. Describe the frontiers problem and the Missiles Metaphor. c. What are wave-shaping algorithms?

Explain the ideas behind the constraint satisfaction search and how it might apply to the Donkey Puzzle. Give three examples of heuristics and explain how they play a significant role in a. your day-to-day life, and b. the problem-solving process for some challenge that faces you.

Explain why hill climbing is called a “greedy algorithm.”

a. Describe some other algorithms that you know that are “greedy.”

b. Explain how steepest-ascent hill climbing is an improvement over simple hill climbing.

c. How does the best first search improve over hill climbing?

Solution: