CS212: Data Structures and Algorithms

Homework 12: AI

1. Explain informally, in a paragraph or so, how you would design a program to solve Calculus 171 problems using the techniques of symbolic AI/state space search.  What would the nodes and edges of the graph you search be? Start and end nodes? What kind of search algorithm would you run?

1. Given the following tree, compute the minimax value of the root (i.e. Node A).  Limit your search to depth two.

Value of node

Node                     [evaluate()]            Type       Children

A                                          18                          max            B, C, D

B                                          24                          min             E, F, G

C                                           -8                          min             H

D                                           6                           min             I, J, K

E                                          20                          max

F                                          13                          max

G                                          17                          max            L,M

H                                           -5                          max

I                                           25                          max

J                                           19                          max            N, O

K                                          30                          max

L                                          25                          min

M                                          28                          min

N                                          17                          min

O                                          20                          min

3. Show the sequence of cities and the cost estimates that A* search would use in finding the best path from Oradea to Bucharest in the lecture powerpoints, ch7+AI.ppt. Explain why the heuristic suggested there for that problem is admissible.