Cos3761 assignment 1 2022 100% pass
List the 5 components that can be used to define a problem.
1. Initial state
2. Actions
3. Transition model
Question 1. 22 Marks
(2.1) List the 5 components that can be used to define a problem.
1. Initial state
2. Actions
3. Transition model
4. Goal test
5. Path cost
, 2.2) Differentiate between search space and goal space. The search space is the set of states that have
to be searched for a solution, whereas a goal space is a set of goal states
(2.3) Differentiate between search space and goal space. The search space is the set of states that have
to be searched for a solution, whereas a goal space is a set of goal states. What is the purpose of the
explored set? Avoids infinite loops since it holds the list of nodes that have already been explored
2.4 List and discuss three types of queues that may be employed in a search. 1. FIFO: usedin
DFSsearches, nodes are added in reverse order to ensure that the last node added will be the first node
to be explored. 2. LIFO: Typically used in BFS searches: nodes are added in the order they are generated.
3. Priority queue: Nodes are added and sorted based on some key, this ensures that certain states take
priority over others during the expansion phase.
2.5 List and explain the measures used to determine problem solving performance. 1. Completeness:
Will the algorithm find a solution if it exists? 2. Optimality: Will the algorithm find the best solution
(optimal path cost among all solutions)? 3. Time complexity: How long does the algorithm take to find a
solution? 4. Space complexity: How much memory is needed to perform the search for a solution?
Question 3: 23 Marks Three (3) hikers (Andile, Barbara, and Ch´e) have just descended down a valley to
find themselves confronted by a river they cannot get across. After walking downstream for a while they
find two young boys with a boat and ask them if they would help them get across the river. The boys
agree, but inform the hikers that since their boat is so small, it can only hold only the two boys or one of
the hikers at a time. We can assume that everyone knows how to row the boat.
(3.1) DefineastateDefine a state using amathematical notation (pictures or any form of graphical
notation will not be accepted). Discuss the appropriateness of your choice, and provide an example to
show that it will be suitable to be employed during a search. Wecan abbreviate the hikers with the
labels A, B, and C. The boys we could label b1 and b2. There are many possible answers. We need not
distinguish between the boys as it would not make a difference to the solution, however, set theory
dictates that sets do not contain duplicates, thus we need to properly indicate that the boys are two
unique entities. State {A,B,C,b1,b2}{}(for hikers, for boys –if boys are unique) represents the two sidesof
the river and the people on that side. We can use a more compact representation {A,B,C,b1,b2}, since if
a person is not on the one side he/she will be on the other side.
3.2 Define the start and goal states using your representation. Start state: {A,B,C,b1,b2}2 There are 3
possible goal states! (I show the state representing the left (beginning) side of the river –the
complement is also correct) 1. {} 2 2. {bi} with I ∈ {1,2} 3. {b1,b2}
3.3 Define an appropriate cost function or functions for this problem. Cost function: A cost function is
not relevant here, since it would not impact which solution would be used(if more than one exists).
3.4Provide a formal definition of a valid action function for this problem –you need not provide a formal
definition for the operation of the function. Discuss the operation of the function and provide an
example to illustrate its use. Successor: move 1 hiker, 1 boy, or 2 boys to the other side. Mathematically
we either remove one or two of the existing elements from our state representation when we move
these people to the other side, or we add one or two missing elements to the set when we move these
List the 5 components that can be used to define a problem.
1. Initial state
2. Actions
3. Transition model
Question 1. 22 Marks
(2.1) List the 5 components that can be used to define a problem.
1. Initial state
2. Actions
3. Transition model
4. Goal test
5. Path cost
, 2.2) Differentiate between search space and goal space. The search space is the set of states that have
to be searched for a solution, whereas a goal space is a set of goal states
(2.3) Differentiate between search space and goal space. The search space is the set of states that have
to be searched for a solution, whereas a goal space is a set of goal states. What is the purpose of the
explored set? Avoids infinite loops since it holds the list of nodes that have already been explored
2.4 List and discuss three types of queues that may be employed in a search. 1. FIFO: usedin
DFSsearches, nodes are added in reverse order to ensure that the last node added will be the first node
to be explored. 2. LIFO: Typically used in BFS searches: nodes are added in the order they are generated.
3. Priority queue: Nodes are added and sorted based on some key, this ensures that certain states take
priority over others during the expansion phase.
2.5 List and explain the measures used to determine problem solving performance. 1. Completeness:
Will the algorithm find a solution if it exists? 2. Optimality: Will the algorithm find the best solution
(optimal path cost among all solutions)? 3. Time complexity: How long does the algorithm take to find a
solution? 4. Space complexity: How much memory is needed to perform the search for a solution?
Question 3: 23 Marks Three (3) hikers (Andile, Barbara, and Ch´e) have just descended down a valley to
find themselves confronted by a river they cannot get across. After walking downstream for a while they
find two young boys with a boat and ask them if they would help them get across the river. The boys
agree, but inform the hikers that since their boat is so small, it can only hold only the two boys or one of
the hikers at a time. We can assume that everyone knows how to row the boat.
(3.1) DefineastateDefine a state using amathematical notation (pictures or any form of graphical
notation will not be accepted). Discuss the appropriateness of your choice, and provide an example to
show that it will be suitable to be employed during a search. Wecan abbreviate the hikers with the
labels A, B, and C. The boys we could label b1 and b2. There are many possible answers. We need not
distinguish between the boys as it would not make a difference to the solution, however, set theory
dictates that sets do not contain duplicates, thus we need to properly indicate that the boys are two
unique entities. State {A,B,C,b1,b2}{}(for hikers, for boys –if boys are unique) represents the two sidesof
the river and the people on that side. We can use a more compact representation {A,B,C,b1,b2}, since if
a person is not on the one side he/she will be on the other side.
3.2 Define the start and goal states using your representation. Start state: {A,B,C,b1,b2}2 There are 3
possible goal states! (I show the state representing the left (beginning) side of the river –the
complement is also correct) 1. {} 2 2. {bi} with I ∈ {1,2} 3. {b1,b2}
3.3 Define an appropriate cost function or functions for this problem. Cost function: A cost function is
not relevant here, since it would not impact which solution would be used(if more than one exists).
3.4Provide a formal definition of a valid action function for this problem –you need not provide a formal
definition for the operation of the function. Discuss the operation of the function and provide an
example to illustrate its use. Successor: move 1 hiker, 1 boy, or 2 boys to the other side. Mathematically
we either remove one or two of the existing elements from our state representation when we move
these people to the other side, or we add one or two missing elements to the set when we move these
