Notice: Exam Form BE IV/II & BAR V/II (Back) for 2076 Magh
Routine: BE IV/II & BAR V/II - 2076 Magh
Result: BCE I/II exam held on 2076 Bhadra
Result: All (except BCE & BEI) I/II exam held on 2076 Bhadra
Notice: Exam Center for Barrier Exam (2076 Poush), 1st Part
View All
View Old Questions
Computer Engineering(BCT)
Electrical Engineering(BEL)
Electronics and Communication(BEX)
View All
View Syllabus
Computer Engineering(BCT)
Electrical Engineering(BEL)
Electronics and Communication(BEX)
View All

Notes of Artificial Intelligence [CT 653]

Problem Solving


Defining Problem as a State Space Search

- A state space consists of a set of nodes representing each state of the problem, arc between nodes representing the legal moves from one state to another, an initial state and a goal state.
- A problem as a state space can be defined by:
a) initial state
b) actions
c) goal test
d) path cost
- The state space is represented as tree or graph
- A solution is a path from initial state to goal state
- A problem is called well defined problem if defined with a state space components.

Example: consider a problem given as:

- On holidays in Nepal ; currently in dharan.
- Flight leaves tomorrow from Kathmandu.

This problem can be well defined by defining it as a state space:
#initial state: Dharan
#actions : s(x)=set of action – state pairs
i.e s(dharan)= {itahari,itahari>,
#goal test: x=Kathmandu
#path cost: sum of distances
#solution : sequence of actions leading from initial state to goal state.

Problem Types; Well Defined Problems

1) Single state problem deterministic,accessible)
- Agent knows about the world
- Can calculate optional action sequence solution
- Playing chess

2) Multi state problem (deterministic, inaccessible)
- Agent does not know exact state.
- State assumption to reach goal.
- Eg: walking in dark room
a) If you are at door, go straight leads to kitchen
b) If you are at kitchen, turn left leads to bedroom

3) Contingency problem(non-deterministic, inaccessible)
- Solution is tree of policy
- Interleave search
- Eg: new skater in an arena.
a) sliding problem
b) Other skaters

4) Exploration problem
- Unknown stare space
- Discover and learn about environment while acting
- Eg:maze

Constraint Satisfaction Problem

Constraint satisfaction problem is a search procedure that operates in a space of constraints.
Constraints are added by making a guess about something t. the problem can be defined as a set of variables(x1,x2…..)and constraints(c1,c2,……)constraint propagation terminates if no solution is consistent with known constraints and no further changes can be made based on current knowledge .
E.g.: crypto-arithmetic problems.

Q) solve the following crypto – arithmetic problems:

send more= money


1) D+E= Y+10C1……………(1)
2) N+R+C1=E+10C2…………..(2)
3) R+O+C2=N+10C3……..(3)
4) S+M+C1=O+1C4………(4)
5) C4=M…….(5)
6) Every variable should have unique value.

Solving equation 5;
Assuming that MSD can not be 0, hence c4=1
.·. M=1

Solving equation 4;
Here, to get C4=1
S=9(maximum value)
If C3=1, 0=1
If C3=0 , O=0
As 1 has already been mapped, O=0
So, equation 4 becomes:

Solving equation (3)
As E and N can not have same value, it must differ by 1 so , C2=1
To have c3=1, E must be 9, then :
N=0 (not possible)
So, c3=0

From equation (6)
.·. S=9

From equation 2:
Or, N+R+C1=E+10
Or, (E+1)+R+C1=E+10(from 8)
Or , R+C1=9
If C1=0 , R=9 but 9 is already mapped
So, C1=1 and R=8

From equation 1;
Or, D+E=Y+10………(9)

Here D and E sums up to give a number greater than 10, but, the minimum value for Y is 2. Since, 8 and 9 are already mapped and for Y to be at least 2, one of two D or E must be &.
If E=7, then N=8 (from 8), but * is already mapped.
So, D=7

The value of E most be or 6 for Y to be at least 2.
If E=6, y=3 and N =7 . but 7 is already mapped .
.·. E=5

From equation 9:

From equation 8;

Hence , the solution is
9 5 6 7
+1 0 8 5
1 0 6 5 2


Carry ={0,1}
Numbers ={0,1,2,…………..9}

1) 2T=G +10C1………..(1)
2) 2H+C1=N+10C2………(2)
3) 2G+C2=0+10C3……..(3)
4) 2I+C3=R+10C4……..(4)
5) 2R + C4=W……..(5)
6) Every variable should have unique value.

Solving equation (5)
2R+ C4=W
As 2R+C4 do not result in carry i.e. carry=0, the value of R may be 0,1,2,3 and 4
R Cy W
0 0 0
0 1 1
1 0 2
1 1 3
2 0 4
2 1 5
3 0 6
3 1 7
4 0 8
4 1 9

As MSB can not be 0; R can be 1,2,3 and 4.
Let R-1,Cy=0;W=2
2I + C3=1(from 4)
I=0 and C3=1

Solving equation 3,
Or, C2+2C1=0+10

Here, the value of G must ranges from 5 to 9

G Cy W
5 0 0
5 1 1
6 0 2
6 1 3
7 0 4
7 1 5
8 0 6
8 1 7
9 0 8
9 1 9

Assume, G=7 and C20; => O=4
Solving equation 1;
Or, 2T=7+10C1(not possible)
Here 10C1+7 yield odd number

Assume G-6 and C2=1;
Solving equation 1;
2T=G +10C1
Or, 2t=6=10c1
If C1=0;T=3[·.· not possible]
If c1=1;t=8

Solving equation 2;
Or 2h+1=n+10
Or 2h=n+9………(6)
Here, n must be odd for validity
So the possible values of n are 5,7 and 9

If n=5,2h=5+9

The solution is :
1 0 6 7 8
1 0 6 7 8
2 1 5 5 6

Game playing and Production System

- A production system is a system that consists of a set of rules. Each rule consists of a pattern on left side that determines applicability of rules and operation to be performed on right side if rule is applied.

- E.g.: for a vacuum world, assume a be the environment, then:
[a, clean]=>move right
[a, dirt]=>clean

- It also have control strategy that specifies order which rules will be selected and a way to resolve conflicts.

Sponsored Ads