1 n vehicles occupy squares 1 1 through n 1 ie the bottom

Assignment Help Data Structure & Algorithms
Reference no: EM13347887

1. n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n × n grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n - i + 1, n). On each time step, every one of the n vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.

a. Calculate the size of the state space as a function of n.

b. Calculate the branching factor as a function of n.

c. Suppose that vehicle i is at (xi, yi); write a nontrivial admissible heuristic hi for the number of moves it will require to get to its goal location (n - i + 1, n), assuming no other vehicles are on the grid. Give a formula for hi in terms of xi, yi, and n.

d. Which of the following heuristics are admissible for the problem of moving all n vehicles to their destinations? Explain.

i) _(i=1)^n hi  

ii) max{h1, . . . , hn}

iii) min{h1, . . . , hn}

2. Describe the search algorithm that results from each of the following special cases. How does it relate to other algorithms we have discussed?

a. Local beam search with k = 1.

b. Local beam search with one initial state and no limit on the number of states retained.

c. Simulated annealing with T = 0 at all times (and omitting the termination test).

d. Simulated annealing with T = ∞ at all times.

e. Genetic algorithm with population size N = 1.

Reference no: EM13347887

Questions Cloud

Question a one of your old english lit professors has been : question a one of your old english lit professors has been elected governor of baxter a cute little new england state
Your organization city rehab has been approached by an mco : your organization city rehab has been approached by an mco looking for an exclusive arrangement for the rehabilitation
Imagine that you work for fema or the department of : imagine that you work for f.e.m.a. or the department of homeland security.in light of the problems brought up by
Genome4u is a scientific research project at a large : genome4u is a scientific research project at a large university in the united states. genome4u has recently started a
1 n vehicles occupy squares 1 1 through n 1 ie the bottom : 1. n vehicles occupy squares 1 1 through n 1 i.e. the bottom row of an n times n grid. the vehicles must be moved to
Experimentuse the transistor board provideddc analysisa1 : experimentuse the transistor board provideddc analysisa1 connect a 15 volt supply to vcc and ground and accurately set
Create a program that maintains the required book catalog : create a program that maintains the required book catalog for the circulation desk of a library. the book catalog is to
Question 1 an unanticipated demand-pulled inflation would : question 1 an unanticipated demand-pulled inflation would normally lead to all the following problems except a change
Correlation and regressionuse the subsequent hypothetical : correlation and regressionuse the subsequent hypothetical correlation matrix to answer the first two

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  What-if and goal-seeking analysis

Problem 1: What-if and Goal-seeking analysis, Problem 2: Portfolio Planning using optimization, Problem 3: A Monte Carlo Simulation Problem

  Create an er diagram

Create an E-R diagram with all appropriate notation for the following condition. In a particular fruit growing region there are a number of orchards.

  Design systems with less complexity algorithms

Complexity of the algorithms so that we can write the programs with out sacrificing the other aspects like speed, qualit y and other related thing.

  Create an algorithm to produce list of customers

Create an algorithm to produce list of customers from Glad Rags Clothing Company's customer master file. Each record on customer master file contains the customer's number

  Find out the big-o running time of bubble sort

Find out the big-O running time (tight bound) of bubble sort. Illustrtae your derivation. Count comparisons as critical operation.

  Explanation of oracle9i database

Take your current knowledge of Oracle Logs ect and project how a bank may make use of integrity control mechanisms.

  Explaining simple symmetric encryption algorithm

Consider a simple symmetric encryption algorithm as follows:Is it a problem if the first block of input happens to be the same as the key? Explain why?

  Multiple choice - high school excel 2003

Cell E23 has a date value and you want to place that date on an invoice prefaced with the text located in B15. Determine the command to do that?

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Reverse path flooding

Suppose we have a network of nodes connected via point to point links, and source S sends a message that will be broadcast to all nodes using Reverse Path Flooding.

  The provided code reads two sequences of numbers

The provided code reads two sequences of numbers. In this task, you are asked to write a function to insert these numbers into two separate doubly linked lists so that the data are in ascending order

  Question about damaged database

Suppose if you were one of the users of a damaged database, discuss how would you be affected by such a failure and what measures could you take to prevent it?

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd