CSE5360 Homework 1-Uninformed Search Solved

1. For the following tree, show the lists of open and visited nodes (i.e. nodes to which the goal test and the successor function have been applied) for each cycle of the listed search algorithms. The goal nodes are X and Z, and the numbers next to the edges indicate the associated cost.

 

a)    Breadth-first search

b)    Depth-first search

c)    Uniform cost search ( ties should be broken alphabetically )

For each node in the open and visited lists also indicate the associated cost.

Informed Search
2. Consider the following problem: You are working in a shop and have to put 1kg of rice into a container (initially empty) from a rice store (with unlimited amounts of rice). To weigh the rice you have a scale that can only measure two weights, namely 3kg and 5kg and you can move rice between the rice store, the scale, and the container (both the rice store and the container can hold an unlimited amount of rice). To know how much rice you have in the container, you can therefore move the rice only in quantities of 3kg or 5kg. Assume that we want to move as little rice as possible and thus the cost of every move is proportional to the amount of rice that is moved.

a)    Formulate the problem as an informed search problem by designing a state space, a successorfunction, a goal test, and an admissible heuristic for this problem.

b)   Show the operation of Greedy Best-first search on this problem by listing the open list and thevisited list (including the cost value used) for each iteration of the search.

2020 Manfred Huber        Page 1 CSE 5360 - Artificial Intelligence I Homework 1: Problem Solving Using Search

c)    Show the operation of A∗ search on this problem by listing the open list and the visited list (including the cost value used) for each iteration of the search.

d)   Show the operation of IDA∗ search on this problem by listing the open list and the visited list (including the cost value used) for each iteration of the search.

Problem Solving Using Search
3. Consider an extension of the problem in part 2 where the scale can measure 3 different weight, i, of size ci, and you should fill rice into two containers, j, where the amount of rice put in each container is xjkg. Again you can move rice between the rice store, the scale, and the containers. As previously, the cost of each move is equal to the amount of rice that is moved and rice can only be weighted on the scale.

Write a program which solves this problem using A∗ search (make sure that the values for the weights that the scale can measure and the goal amount for each container are easy to change in the code). You have to implement your own A∗ search and can thus not use any prior implementations of search functions. Your search should return the correct sequence of rice moves, including the total cost. In addition, it should output the sequence in which nodes were added to the open list and how they were visited.