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>,
saptari,saptari>,…….}
#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
ans:-

carry={0,1}
variable={S,E,N,D,M,O,R,Y}
numbers={0………………9)

constraints:
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;
M=C4
Assuming that MSD can not be 0, hence c4=1
.·. M=1

Solving equation 4;
S+M+C3=0+10*1
S+c3+1=0+10
Here, to get C4=1
S=9(maximum value)
Then,
If C3=1, 0=1
If C3=0 , O=0
As 1 has already been mapped, O=0
So, equation 4 becomes:
S+C3+1=10………….(6)

Solving equation (3)
E+O+C3=N+10C3
.·.E+c2=N+10C3
As E and N can not have same value, it must differ by 1 so , C2=1
.·.E+1=N+10c3..(7)
To have c3=1, E must be 9, then :
N=0 (not possible)
So, c3=0
.·.E+1=N……..(8)

From equation (6)
S+0+1=10
.·. S=9

From equation 2:
N+R+c1=E+10C2
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;
D+E=Y+10C1
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:
Y=2

From equation 8;
N=6

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

---

RIGHT + RIGHT =WRONG
ANS

Carry ={0,1}
Variables={R,I,G,H,T,W,O,N}
Numbers ={0,1,2,…………..9}

Constraints:
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,
C2+2C1=0+10C3
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;
2T=G+10C1
Or, 2T=7+10C1(not possible)
Here 10C1+7 yield odd number

Again,
Assume G-6 and C2=1;
0=3
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;
2h+c1=n+10c2
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
.·.h=7

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.