CS638 Artificial Intelligence MidSem
Exam
Max marks = 45 Weightage
= 20% Be
Concise
“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>
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 
[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)
[Marks 14]
See graph for solution showing
CLOSED (shaded with order of expansion and f and gvalues), OPEN (with f and g
values), back pointers.
[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.