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 ,...

Links between family and community are essential for children's well-being. Provide examples and research findings from our discussion that support this idea.

Westmiller Construction Company purchased a new truck on December 31, 2009, for $48,000. The truck has an estimated useful life of three years and an estimated salvage value of $12,000. When the...

The approximate length of the "honeymoon period" for an employee who starts a new job is :Group of answer choies 9 months 6 months 1 2 months 3 months

Seved Help 14 Wisconsin Snowmobile Corp. is considering a switch to level production Cost efficiencies would occur under level production, and aftertax costs would decline by $31,500, but inventory...

How has Departmental Computing increased the need for HCM Professionals and Technical Staff to be skilled in Business Computing Software and Systems?

Describe the difference between Two- and Three-Tier Computing Systems.

Explain the differences between On Premises, SaaS, PaaS, IaaS, and Hybrid Computing environments.