Transcript Assignment

Artificial Intelligence
Problem solving by searching
CSC 361
Prof. Mohamed Batouche
Computer Science Department
CCIS – King Saud University
Riyadh, Saudi Arabia
[email protected]
Problem Solving by Searching
Search Methods :
Uninformed (Blind) search
Tutorial II
Search Methods

Consider the River Problem:
A farmer wishes to carry a wolf, a duck and corn across a river, from the south to the
north shore. The farmer is the proud owner of a small rowing boat called Bounty
which he feels is easily up to the job. Unfortunately the boat is only large enough to
carry at most the farmer and one other item. Worse again, if left unattended the wolf
will eat the duck and the duck will eat the corn.
River
boat
Farmer, Wolf,
Duck and Corn
How can the farmer safely transport the wolf, the duck and the corn to the opposite
shore? Solve this problem using BFS. Do not expand repeated stated.
3
Search Methods

Problem 2:
Given the following state space (tree search), give the sequence of
visited nodes when using BFS, DFS, and IDS.
Initial state
A
B
C
D
E
F
Goal state
G H
I
J
K
L
M N
O
P
Q
S
T
U V
W X
Y
Z
R
4
Consider the following problem…
A
10
1
5
S
5
B
G
5
15
C
We wish to find the shortest route from node S to node G; that is, node S is the initial
state and node G is the goal state. In terms of path cost, we can clearly see that the
route SBG is the cheapest route. However, if we let breadth-first search loose on the
problem it will find the non-optimal path SAG, assuming that A is the first node to be
expanded at level 1. Solve this problem using UCS.
5