CS638             Artificial Intelligence                 MidSem Exam                        September 27, 2007

Max marks =   45                    Weightage = 20%                               Be Concise

 

 

 

  1. Your response to the advertisement that for the fifteenth time blanks out a TV action replay is to
    1. Rush out to buy the advertised product
    2. Resolve to buy only that product in the future
    3. Send frantic emails to all you know urging them to buy only that product
    4. None of the above                                                                  [Marks 1]

 

 

 

  1. What is the Physical Symbol System Hypothesis?                          [Marks 5]

 

“The physical symbol system hypothesis was formulated by Newell and Simon (1963) as the result of success of GPS (General Problem Solver) and subsequent programs as models of cognition.

It states that "a physical symbol system has the necessary and sufficient means of general intelligent action."

What this means is that any system (human or machine) exhibiting intelligence must operate by taking physical patterns (symbols), combining them into structures (expressions) and manipulating them (using processes) to produce new expressions.”

                        from: <http://en.wikipedia.org/wiki/Physical_symbol_system>

 

 

  1. Describe one probabilistic constructive method and one deterministic perturbative method for solving the TSP.                                        [Marks 10]

 

 

Probabilistic Constructive : Start with some city. Randomly choose a neighbour and move to it with a probability inversely proportional to the distance.

 

Deterministic Perturbative method : Hill climbing or Tabu Search in solution space.

 

 

 

 

 

 

 

A

B

C

D

E

A

0

70

20

50

60

B

70

0

40

10

30

C

20

40

0

30

40

D

50

10

30

0

70

E

60

30

40

70

0

  1. Given the cost matrix in the accompanying table, determine the estimated cost of a TSP tour that contains the segment DE but excludes the segment AC. Describe your estimating function. What properties should the estimating function have to devise a good TSP solver?

 

[Marks 10]

 

            Estimating function : 

From every row choose two smallest costs

                                                Exclude costs of excluded segments

                        Include costs of included segments even if not smallest

            Add up costs for all rows and divide by two

 

 

            Estimate = ((50+60) + (10+30) + (30+40) + (10+70) + (30+70)) / 2

                                    = (110 + 40 + 70 + 80 + 100) /2

                                    = 400/2 = 200

 

            The estimating function should

(1)   be a lower bound on actual cost (for admissibility)

(2)   be as high as possible (for better pruning)

 

  1. In the problem graph given overleaf, the numbers on the edges represents costs of moves. S is the start node and G is the goal node. Show the graph after algorithm A* has expanded 8 nodes, including S. Use Manhattan distance as the heuristic function. The cities are placed on a grid of size 10.

[Marks 14]

See graph for solution showing CLOSED (shaded with order of expansion and f and g-values), OPEN (with f and g values), back pointers.

 

 

  1. What can you say about the Manhattan distance heuristic function for the given problem of question 5?

[Marks 5]

 

The heuristic function is (1) a lower bound on h*(n) and (2) satisfies the consistency or monotone condition (because it underestimates cost of each arc).

End.