Sorry, an error occurred while loading the content.
Browse Groups

• Look at the Java code for aima.examples.TestSearch.java. This test is solving two problems. The TwoThreeState problem is to get to a state consisting of a
Message 1 of 2 , Aug 17, 2002
View Source
Look at the Java code for aima.examples.TestSearch.java. This test is
solving two problems. The TwoThreeState problem is to get to a state
consisting of a number that is evenly divisible by 23, starting at zero. The
two operators are to add 2 or add 3. Each search prints out the path to the
goal in reverse order. So a depth-first search achieves the goal with a path
of length 23, each time applying the add2 operator. Breadth First Search
takes only 8 steps, most of them add3. A* Search takes 11 steps. Why more?
Because the costs of the operators is 2 for add2 and 4 for add3, so the
optimal solution perfers add2.

The other problem is missionaries and cannibals. The state (3,3,1) means 3
missionaries, 3 cannibals and 1 boat on the left side of the river; the goal
is to get them all to the other bank. All the search techniques shown solve
the problem in 11 steps.

-Peter

----- Original Message -----
From: "dpbatagoda" <dharshana@...>
To: <aima-talk@yahoogroups.com>
Sent: Friday, August 16, 2002 9:04 PM
Subject: [aima-talk] Pls Help Me

> Dear everybody,
> I am an instructure at Sri Lanka Institute of Information Technology.
> I really apreciate if you can explain this output from
> aima.examples.TestSearch?
>
>
>
> Trivial search space based on adding 2 or 3
> DFS:
> State: (46) Depth: 23 Cost: 46.0 by applying add2
> State: (44) Depth: 22 Cost: 44.0 by applying add2
> State: (42) Depth: 21 Cost: 42.0 by applying add2
> State: (40) Depth: 20 Cost: 40.0 by applying add2
> State: (38) Depth: 19 Cost: 38.0 by applying add2
> State: (36) Depth: 18 Cost: 36.0 by applying add2
> State: (34) Depth: 17 Cost: 34.0 by applying add2
> State: (32) Depth: 16 Cost: 32.0 by applying add2
> State: (30) Depth: 15 Cost: 30.0 by applying add2
> State: (28) Depth: 14 Cost: 28.0 by applying add2
> State: (26) Depth: 13 Cost: 26.0 by applying add2
> State: (24) Depth: 12 Cost: 24.0 by applying add2
> State: (22) Depth: 11 Cost: 22.0 by applying add2
> State: (20) Depth: 10 Cost: 20.0 by applying add2
> State: (18) Depth: 9 Cost: 18.0 by applying add2
> State: (16) Depth: 8 Cost: 16.0 by applying add2
> State: (14) Depth: 7 Cost: 14.0 by applying add2
> State: (12) Depth: 6 Cost: 12.0 by applying add2
> State: (10) Depth: 5 Cost: 10.0 by applying add2
> State: (8) Depth: 4 Cost: 8.0 by applying add2
> State: (6) Depth: 3 Cost: 6.0 by applying add2
> State: (4) Depth: 2 Cost: 4.0 by applying add2
> State: (2) Depth: 1 Cost: 2.0 by applying add2
> Starting at state: (0)
>
> Depth Bounded (depth 7):
> No solution
>
> BFS:
> State: (23) Depth: 8 Cost: 30.0 by applying add2
> State: (21) Depth: 7 Cost: 28.0 by applying add3
> State: (18) Depth: 6 Cost: 24.0 by applying add3
> State: (15) Depth: 5 Cost: 20.0 by applying add3
> State: (12) Depth: 4 Cost: 16.0 by applying add3
> State: (9) Depth: 3 Cost: 12.0 by applying add3
> State: (6) Depth: 2 Cost: 8.0 by applying add3
> State: (3) Depth: 1 Cost: 4.0 by applying add3
> Starting at state: (0)
>
>
> Uniform cost:
> State: (23) Depth: 11 Cost: 24.0 by applying add3
> State: (20) Depth: 10 Cost: 20.0 by applying add2
> State: (18) Depth: 9 Cost: 18.0 by applying add2
> State: (16) Depth: 8 Cost: 16.0 by applying add2
> State: (14) Depth: 7 Cost: 14.0 by applying add2
> State: (12) Depth: 6 Cost: 12.0 by applying add2
> State: (10) Depth: 5 Cost: 10.0 by applying add2
> State: (8) Depth: 4 Cost: 8.0 by applying add2
> State: (6) Depth: 3 Cost: 6.0 by applying add2
> State: (4) Depth: 2 Cost: 4.0 by applying add2
> State: (2) Depth: 1 Cost: 2.0 by applying add2
> Starting at state: (0)
>
> Iterated Deepening Search:
> State: (23) Depth: 8 Cost: 30.0 by applying add3
> State: (20) Depth: 7 Cost: 26.0 by applying add3
> State: (17) Depth: 6 Cost: 22.0 by applying add3
> State: (14) Depth: 5 Cost: 18.0 by applying add3
> State: (11) Depth: 4 Cost: 14.0 by applying add3
> State: (8) Depth: 3 Cost: 10.0 by applying add3
> State: (5) Depth: 2 Cost: 6.0 by applying add3
> State: (2) Depth: 1 Cost: 2.0 by applying add2
> Starting at state: (0)
>
> A* Search:
> State: (23) Depth: 11 Cost: 24.0 by applying add3
> State: (20) Depth: 10 Cost: 20.0 by applying add2
> State: (18) Depth: 9 Cost: 18.0 by applying add2
> State: (16) Depth: 8 Cost: 16.0 by applying add2
> State: (14) Depth: 7 Cost: 14.0 by applying add2
> State: (12) Depth: 6 Cost: 12.0 by applying add2
> State: (10) Depth: 5 Cost: 10.0 by applying add2
> State: (8) Depth: 4 Cost: 8.0 by applying add2
> State: (6) Depth: 3 Cost: 6.0 by applying add2
> State: (4) Depth: 2 Cost: 4.0 by applying add2
> State: (2) Depth: 1 Cost: 2.0 by applying add2
> Starting at state: (0)
>
> Greedy Search:
> State: (23) Depth: 8 Cost: 30.0 by applying add2
> State: (21) Depth: 7 Cost: 28.0 by applying add3
> State: (18) Depth: 6 Cost: 24.0 by applying add3
> State: (15) Depth: 5 Cost: 20.0 by applying add3
> State: (12) Depth: 4 Cost: 16.0 by applying add3
> State: (9) Depth: 3 Cost: 12.0 by applying add3
> State: (6) Depth: 2 Cost: 8.0 by applying add3
> State: (3) Depth: 1 Cost: 4.0 by applying add3
> Starting at state: (0)
>
> Generalized missionaries and cannibals (3,3,1)
> Breadth-first search skipping repeated states
> State: (0:3,0:3,0:1) Depth: 11 Cost: 11.0 by applying (0,2,-1)
> State: (0:3,2:1,1:0) Depth: 10 Cost: 10.0 by applying (0,1,1)
> State: (0:3,1:2,0:1) Depth: 9 Cost: 9.0 by applying (0,2,-1)
> State: (0:3,3:0,1:0) Depth: 8 Cost: 8.0 by applying (0,1,1)
> State: (0:3,2:1,0:1) Depth: 7 Cost: 7.0 by applying (2,0,-1)
> State: (2:1,2:1,1:0) Depth: 6 Cost: 6.0 by applying (1,1,1)
> State: (1:2,1:2,0:1) Depth: 5 Cost: 5.0 by applying (2,0,-1)
> State: (3:0,1:2,1:0) Depth: 4 Cost: 4.0 by applying (0,1,1)
> State: (3:0,0:3,0:1) Depth: 3 Cost: 3.0 by applying (0,2,-1)
> State: (3:0,2:1,1:0) Depth: 2 Cost: 2.0 by applying (0,1,1)
> State: (3:0,1:2,0:1) Depth: 1 Cost: 1.0 by applying (0,2,-1)
> Starting at state: (3:0,3:0,1:0)
>
> Breadth-first search with repeated states
> State: (0:3,0:3,0:1) Depth: 11 Cost: 11.0 by applying (0,2,-1)
> State: (0:3,2:1,1:0) Depth: 10 Cost: 10.0 by applying (0,1,1)
> State: (0:3,1:2,0:1) Depth: 9 Cost: 9.0 by applying (0,2,-1)
> State: (0:3,3:0,1:0) Depth: 8 Cost: 8.0 by applying (0,1,1)
> State: (0:3,2:1,0:1) Depth: 7 Cost: 7.0 by applying (2,0,-1)
> State: (2:1,2:1,1:0) Depth: 6 Cost: 6.0 by applying (1,1,1)
> State: (1:2,1:2,0:1) Depth: 5 Cost: 5.0 by applying (2,0,-1)
> State: (3:0,1:2,1:0) Depth: 4 Cost: 4.0 by applying (0,1,1)
> State: (3:0,0:3,0:1) Depth: 3 Cost: 3.0 by applying (0,2,-1)
> State: (3:0,2:1,1:0) Depth: 2 Cost: 2.0 by applying (0,1,1)
> State: (3:0,1:2,0:1) Depth: 1 Cost: 1.0 by applying (0,2,-1)
> Starting at state: (3:0,3:0,1:0)
>
> A* Search:
> State: (0:3,0:3,0:1) Depth: 11 Cost: 11.0 by applying (0,2,-1)
> State: (0:3,2:1,1:0) Depth: 10 Cost: 10.0 by applying (0,1,1)
> State: (0:3,1:2,0:1) Depth: 9 Cost: 9.0 by applying (0,2,-1)
> State: (0:3,3:0,1:0) Depth: 8 Cost: 8.0 by applying (0,1,1)
> State: (0:3,2:1,0:1) Depth: 7 Cost: 7.0 by applying (2,0,-1)
> State: (2:1,2:1,1:0) Depth: 6 Cost: 6.0 by applying (1,1,1)
> State: (1:2,1:2,0:1) Depth: 5 Cost: 5.0 by applying (2,0,-1)
> State: (3:0,1:2,1:0) Depth: 4 Cost: 4.0 by applying (0,1,1)
> State: (3:0,0:3,0:1) Depth: 3 Cost: 3.0 by applying (0,2,-1)
> State: (3:0,2:1,1:0) Depth: 2 Cost: 2.0 by applying (0,1,1)
> State: (3:0,1:2,0:1) Depth: 1 Cost: 1.0 by applying (0,2,-1)
> Starting at state: (3:0,3:0,1:0)
>
> Greedy Search:
> State: (0:3,0:3,0:1) Depth: 11 Cost: 11.0 by applying (0,2,-1)
> State: (0:3,2:1,1:0) Depth: 10 Cost: 10.0 by applying (0,1,1)
> State: (0:3,1:2,0:1) Depth: 9 Cost: 9.0 by applying (0,2,-1)
> State: (0:3,3:0,1:0) Depth: 8 Cost: 8.0 by applying (0,1,1)
> State: (0:3,2:1,0:1) Depth: 7 Cost: 7.0 by applying (2,0,-1)
> State: (2:1,2:1,1:0) Depth: 6 Cost: 6.0 by applying (1,1,1)
> State: (1:2,1:2,0:1) Depth: 5 Cost: 5.0 by applying (2,0,-1)
> State: (3:0,1:2,1:0) Depth: 4 Cost: 4.0 by applying (0,1,1)
> State: (3:0,0:3,0:1) Depth: 3 Cost: 3.0 by applying (0,2,-1)
> State: (3:0,2:1,1:0) Depth: 2 Cost: 2.0 by applying (0,1,1)
> State: (3:0,1:2,0:1) Depth: 1 Cost: 1.0 by applying (0,2,-1)
>
>
>
> To unsubscribe from this group, send an email to:
> aima-talk-unsubscribe@yahoogroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.