Question: General Description For this assignment you will implement two algorithms to the BUDGETED PURCHASE problem. The first algorithm is to use iterative deepening, using the

General Description

For this assignment you will implement two algorithms to the BUDGETED PURCHASE problem.

The first algorithm is to use iterative deepening, using the state space described in problem set

1,

problem

1 .

The second algorithm is to use the hill climbing method described in problem set

2,

problem

1,

together with random restart. To create a random starting point, just go through the objects and assign each one to be in or out of the state, with probability

1 / 2 .

Input

The input is a plain text file.

For the iterative deepening program, the first line is the target value and the budget, as integers, followed by a flag for the type of output:

'

'

for verbose or

'

'

for compact.

For the hill climbing program, the first line has additionally the number of restarts to try.

Each subsequent line has an object name

(

an alphabetic character string

)

and value and cost as integers.

For instance, one possible input for iterative deepening would be this: the input would be

20 10

10 8

8 4

7 3

6 3

4 1

For hill climbing it would be the same, except that the first lie would be

20 10

3

if you were doing three random restarts.

Output

Compact output is just the names of the objects in the solution separated by spaces; or

"

No Solution" if no solution is found.

Verbose output shows a trace of the search, in the forms illustrated below for the above input.

Iterative deepening

Depth

= 1 .

{

} .

Value

= 10 .

Cost

= 8 .

{

} .

Value

= 8 .

Cost

= 4 .

{

} .

Value

= 7 .

Cost

= 3 .

{

} .

Value

= 6 .

Cost

= 3 .

{

} .

Value

= 4 .

Cost

= 1 .

Depth

= 2

{

} .

Value

= 10 .

Cost

= 8 .

{

U Z

} .

Value

= 14 .

Cost

= 9 .

{

} .

Value

= 8 .

Cost

= 4 .

{

V W

} .

Value

= 15 .

Cost

= 7 .

{

V X

} .

Value

= 14 .

Cost

= 7 .

{

V Z

} .

Value

= 12 .

Cost

= 5 .

{

} .

Value

= 7 .

Cost

= 3 .

{

W X

} .

Value

= 13 .

Cost

= 7 .

{

W Z

} .

Value

= 11 .

Cost

= 4 .

{

} .

Value

= 6 .

Cost

= 3 .

{

X Z

} .

Value

= 10 .

Cost

= 4 .

{

} .

Value

= 4 .

Cost

= 1 .

Depth

= 3

{

} .

Value

= 10 .

Cost

= 8 .

{

U Z

} .

Value

= 14 .

Cost

= 9 .

{

} .

Value

= 8 .

Cost

= 4 .

{

V W

} .

Value

= 15 .

Cost

= 7 .

{

V W X

} .

Value

= 21 .

Cost

= 10 .

Found solution

{

V W X

} .

Value

= 21 .

Cost

= 10 .

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

General Description For this assignment you will implement two algorithms to the BUDGETED PURCHASE problem. The first algorithm is to use iterative deepening, using the state space described in...

Write two programs that solves the Best Vertex Cover problem, as described in Problem Set 1. The first will use iterative deepening; the second will use simple hill climbing with random restart....

Implement a C program to solve the 15-puzzle problem using theA* search algorithm. 1. Objectives ? To gain more experience on using pointers and linkedlists in C programs. ? To learn how to solve...

A creative engineer suggests structuring the TLB so that not all the bits of the presented address need match to result in a hit. Suggest how this might be achieved, and what might be the costs and...

Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...

Task 1: Distance Map Requires: knowing how to design and implement a class In file distance_map.py, use the Class Design Recipe to define a class called DistanceMap that lets client code store and...

Objectives Assignment 04: Recursion COSC 2336: Data Structures and Algorithms Fall 2020 Practice writing functions Practice writing recursive functions. Compare iterative vs. recursive implementation...

Subaru Motors Corporation (SMC) today announced plans to revise its organisational structure. The changes will see the company's structure slim down from 230 departments to 131, which will hopefully...

Microkernel operating systems aim to address perceived modularity and reliability issues in traditional "monolithic" operating systems. (i) Describe the typical architecture of a microkernel...

tudy of an innovative method based on complementarity between ARIZ, lean management and discrete event simulation for solving warehousing problems Fatima Zahra Ben Moussa a, , Roland De Guiob ,...

Nazmi bought a bond for RM1,000 five years ago. That has a 20-year maturity and a 12 percent of coupon rate. Now he wishes to sell his bond to finance his small business considering the market price...

Whitefish Machine Shop is a manufacturer of motorized carts for vacation resorts. Pat Cruz, the plant manager of Whitefish, obtains the following information for Job #10 in August 2013. A total of 40...

7 How are dolphins A and B different from C?

Compared with half a century ago, adoption has become _ _ _ _ _ _ _ _ _ common, but it is more open and acceptabl e , so we probably discuss it _ _ _ _ _ _ _ . fill in the blanks more or much less or...

LO6 Summarize various ways to manage retention.

LO3 Define the difference between job satisfaction and engagement.

4. You have recently assumed the role of Human Resource Manager in your company. In reviewing the company records, you note that the job descriptions were last updated five years ago.