際際滷

際際滷Share a Scribd company logo

Ai (new)

B
brokenz_lung

The document describes a problem of a farmer transporting a fox, goose, and grains across a river using a small boat that can only carry one item at a time, outlines the initial state and constraints of not leaving the fox and goose or goose and grains alone together, and proposes using breadth-first search to find the optimal solution path to transport all items across the river.

1 of 17
FUNDAMENTALS OF ARTIFICIAL INTELLIGENCE PROJECT (CSC463) Document Reference No: REPORT/1.0/2011 Group member : Mohd Nazri Bin Ismail Muhammad Ibrahim Bin Haji Mohamed Soid Nor Azura Binti Mohamed Salim
Farmer and his three possessions PROJECT (B)
Outline 1) Introduction 2) Problem formulation - State space - Well-defined problem 3) Solution 4) Conclusion
1.0 Introduction A farmer wants to transport himself along with a fox, a goose, and some grains across a river. The boat could only take at most one of his possessions any trip. The constraints of this problem are the fox must not be left unattended with the goose, and the goose must not be left unattended with the grains.
Farmer, fox, goose, grains 2.1 State Space B A Farmer, grains Fox, goose Farmer Fox, goose, grains B A A 2. Problem Formulation B Farmer, goose Fox, grains Farmer, fox Goose, grains B A B A Goose Farmer, fox, grains B A Farmer, goose, Fox Farmer, fox, Grains grains goose B A B A Grains Farmer, fox, Fox Farmer, goose, goose grains B A B A Goose, grains Farmer, fox Fox, goose Farmer, grains B A B A Farmer, fox, Goose grains B A Initial State Fox, grains Farmer, goose Terminate Goal B A Farmer, fox, goose, grains B A
2.2 Well-Defined Problem Initial State - At A there is a farmer with a fox, a goose and some grains - At B there is no one. B A RIVER Farmer with a fox, a goose and some grains
Possible Action Farmer need to bring along with him a fox first or a goose first or some grains first or brings himself only Farmer must also consider constrains that is do not left behind the fox and the goose together or left the goose and the grains together Transition Model If the farmer chooses to bring a fox first then he will leave a goose and some grains at place A then goose will eat the grains If the farmer chooses to bring the grains first, then the fox will eat the goose Thus, farmer only has one choice that is bring the goose first and left the fox together with the grains
Goal - The goal of this problem is to transfer the entire farmer possessions that is a fox, a goose, and some grains to place B. B A RIVER Farmer with a fox, a goose and some grains
All the farmer action can be summarized as follow: 1) First, the farmer brings the goose from place A to place B. 2) Second, the farmer return back to place A. 3) Third, from place A the farmer brings a fox or some grains to place B. 4) Fourth, from place B the farmer brings back a goose to place A. 5) Fifth, from place A the farmer brings a fox or some grains to place B. (The one that the farmer does not bring in step 3) 6) Sixth, the farmer return back to place A. 7) Lastly, the farmer brings goose to place B. Step Cost o Step Cost = number of crossing that the farmer must make in order to bring all of his possessions to place B. o There are 7 crossing, that is 4 forward and 3 backward o Thus, the step cost is 7 Path Cost o Path cost=number of animal & farmer has crossed the river o That is from 4 to 0.
3. Search Algorithm One algorithm from blind search that is Breadth First Search (BFS) BFS is the shortest solution path from initial state to goal compare to Depth First Search (DFS) BFS proceed searching all the way across one level before going to the next level
3.1 Search Strategies Space Complexity Is proportional to the number of nodes at the deepest level Space complexity for BFS at worst case is exponential Thus, BFS is often impractical for large problems on systems with bounded space Time Complexity Time complexity of BFS is O(bd) or exponential since every vertex and every edge will be explored in the worst case
Completeness BFS is complete, thus BFS will find solution regardless of the kind of graph But, if the graph is infinite and there is no solution and BFS will diverge Optimality For unit-step cost, BFS is optimal In general BFS is not optimal since it always returns the result with the fewest edges between the start node and the goal node If the graph is not weighted, and therefore all step costs are equal, BFS will find the nearest and the best solution BFS use 2 lists that are Open list and Close list
3.2 B F S BFS TRAVERSAL: A B C D E F G H I J K L M N O P Q
STATE OPEN CLOSE 0 [A] [ ] BFS TRAVERSAL: 1 [B, C, D, E] [A] A B C D E F G H I J K L M N O P Q 2 [C, D, E] [B, A] 3 [D, E, F] [C, B, A] 4 [E, F] [D, C, B, A] 5 [F] [E, D, C, B, A] 6 [G, H] [F, E, D, C, B, A] 7 [H, I, J] [G, F, E, D, C, B, A] 8 [I, J, K, L] [H, G, F, E, D, C, B, A] 9 [J, K, L] [I, H, G, F, E, D, C, B, A] 10 [K, L, M] [J, I, H, G, F, E, D, C, B, A] 11 [L, M, N] [K, J, I, H, G, F, E, D, C, B, A] 12 [M, N] [L, K, J, I, H, G, F, E, D, C, B, A] 13 [N, O] [M, L, K, J, I, H, G, F, E, D, C, B, A] 14 [O, P] [N, M, L, K, J, I, H, G, F, E, D, C, B, A] 15 [P, Q] [O, N, M, L, K, J, I, H, G, F, E, D, C, B, A] 16 [Q, R] [P, O, N, M, L, K, J, I, H, G, F, E, D, C, B, A]
SOLUTION PATH: A C F G J M O Q
Conclusion BFS is complete, optimal search strategy with exponential time and space complexity Problem size is small BFS is easier to implement
- Nazri - Ibrahim - Azura - Question??

More Related Content

Ai (new)

  • 1. FUNDAMENTALS OF ARTIFICIAL INTELLIGENCE PROJECT (CSC463) Document Reference No: REPORT/1.0/2011 Group member : Mohd Nazri Bin Ismail Muhammad Ibrahim Bin Haji Mohamed Soid Nor Azura Binti Mohamed Salim
  • 2. Farmer and his three possessions PROJECT (B)
  • 3. Outline 1) Introduction 2) Problem formulation - State space - Well-defined problem 3) Solution 4) Conclusion
  • 4. 1.0 Introduction A farmer wants to transport himself along with a fox, a goose, and some grains across a river. The boat could only take at most one of his possessions any trip. The constraints of this problem are the fox must not be left unattended with the goose, and the goose must not be left unattended with the grains.
  • 5. Farmer, fox, goose, grains 2.1 State Space B A Farmer, grains Fox, goose Farmer Fox, goose, grains B A A 2. Problem Formulation B Farmer, goose Fox, grains Farmer, fox Goose, grains B A B A Goose Farmer, fox, grains B A Farmer, goose, Fox Farmer, fox, Grains grains goose B A B A Grains Farmer, fox, Fox Farmer, goose, goose grains B A B A Goose, grains Farmer, fox Fox, goose Farmer, grains B A B A Farmer, fox, Goose grains B A Initial State Fox, grains Farmer, goose Terminate Goal B A Farmer, fox, goose, grains B A
  • 6. 2.2 Well-Defined Problem Initial State - At A there is a farmer with a fox, a goose and some grains - At B there is no one. B A RIVER Farmer with a fox, a goose and some grains
  • 7. Possible Action Farmer need to bring along with him a fox first or a goose first or some grains first or brings himself only Farmer must also consider constrains that is do not left behind the fox and the goose together or left the goose and the grains together Transition Model If the farmer chooses to bring a fox first then he will leave a goose and some grains at place A then goose will eat the grains If the farmer chooses to bring the grains first, then the fox will eat the goose Thus, farmer only has one choice that is bring the goose first and left the fox together with the grains
  • 8. Goal - The goal of this problem is to transfer the entire farmer possessions that is a fox, a goose, and some grains to place B. B A RIVER Farmer with a fox, a goose and some grains
  • 9. All the farmer action can be summarized as follow: 1) First, the farmer brings the goose from place A to place B. 2) Second, the farmer return back to place A. 3) Third, from place A the farmer brings a fox or some grains to place B. 4) Fourth, from place B the farmer brings back a goose to place A. 5) Fifth, from place A the farmer brings a fox or some grains to place B. (The one that the farmer does not bring in step 3) 6) Sixth, the farmer return back to place A. 7) Lastly, the farmer brings goose to place B. Step Cost o Step Cost = number of crossing that the farmer must make in order to bring all of his possessions to place B. o There are 7 crossing, that is 4 forward and 3 backward o Thus, the step cost is 7 Path Cost o Path cost=number of animal & farmer has crossed the river o That is from 4 to 0.
  • 10. 3. Search Algorithm One algorithm from blind search that is Breadth First Search (BFS) BFS is the shortest solution path from initial state to goal compare to Depth First Search (DFS) BFS proceed searching all the way across one level before going to the next level
  • 11. 3.1 Search Strategies Space Complexity Is proportional to the number of nodes at the deepest level Space complexity for BFS at worst case is exponential Thus, BFS is often impractical for large problems on systems with bounded space Time Complexity Time complexity of BFS is O(bd) or exponential since every vertex and every edge will be explored in the worst case
  • 12. Completeness BFS is complete, thus BFS will find solution regardless of the kind of graph But, if the graph is infinite and there is no solution and BFS will diverge Optimality For unit-step cost, BFS is optimal In general BFS is not optimal since it always returns the result with the fewest edges between the start node and the goal node If the graph is not weighted, and therefore all step costs are equal, BFS will find the nearest and the best solution BFS use 2 lists that are Open list and Close list
  • 13. 3.2 B F S BFS TRAVERSAL: A B C D E F G H I J K L M N O P Q
  • 14. STATE OPEN CLOSE 0 [A] [ ] BFS TRAVERSAL: 1 [B, C, D, E] [A] A B C D E F G H I J K L M N O P Q 2 [C, D, E] [B, A] 3 [D, E, F] [C, B, A] 4 [E, F] [D, C, B, A] 5 [F] [E, D, C, B, A] 6 [G, H] [F, E, D, C, B, A] 7 [H, I, J] [G, F, E, D, C, B, A] 8 [I, J, K, L] [H, G, F, E, D, C, B, A] 9 [J, K, L] [I, H, G, F, E, D, C, B, A] 10 [K, L, M] [J, I, H, G, F, E, D, C, B, A] 11 [L, M, N] [K, J, I, H, G, F, E, D, C, B, A] 12 [M, N] [L, K, J, I, H, G, F, E, D, C, B, A] 13 [N, O] [M, L, K, J, I, H, G, F, E, D, C, B, A] 14 [O, P] [N, M, L, K, J, I, H, G, F, E, D, C, B, A] 15 [P, Q] [O, N, M, L, K, J, I, H, G, F, E, D, C, B, A] 16 [Q, R] [P, O, N, M, L, K, J, I, H, G, F, E, D, C, B, A]
  • 15. SOLUTION PATH: A C F G J M O Q
  • 16. Conclusion BFS is complete, optimal search strategy with exponential time and space complexity Problem size is small BFS is easier to implement
  • 17. - Nazri - Ibrahim - Azura - Question??