User Account

All Pages

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

Assignment Help Data Structure & Algorithms
Reference no: EM13347544

Problem 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. Determine the size of the state space as a function of n.

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

c. Consider that vehicle i is at (xi, yi); write a nontrivial admissible heuristic hi for the number of moves it will need to get to its goal location (n - i + 1, n), considering 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?Illustrate.

2154_Determine the branching factor.png

Problem 2. Expalin 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: EM13347544

Questions Cloud

Write an essay on fdi in nehterlandsthe essay should : write an essay on fdi in nehterlands.the essay should critically anlayze why fdi in nehterlands is attractive or not.
Electricity modellingit deals with electricity usage data : electricity modellingit deals with electricity usage data for 241 households in new zealand that was collected in
Write a research paper in relation to a software design : write a research paper in relation to a software design related topic. diagrams and drawing of attention to key points
The study found 87 per cent of 1500 australians surveyed : the study found 87 per cent of 1500 australians surveyed would support colour-coding on packaged food to indicate
Problem 1 n vehicles occupy squares 1 1 through n 1 ie the : problem 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
Proposal aproposal a envisages generation of electricity : proposal aproposal a envisages generation of electricity from water - a hydro-electric project. the useful economic
Question 1suppose the system shown below initially the gas : question 1suppose the system shown below. initially the gas is at 200 kpa and occupies a volume of 0.1 m3. the spring
Part-11 mutually exclusive events are also independent : part-11. mutually exclusive events are also independent. false2. if events a and b are independent then the probability
Consider the following questionsdespite low valuable brands : consider the following questionsdespite low valuable brands pepsico has done very-well in comparison to coca-cola. what

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  Give time algorithm that outputs satisfying assignment

Find out  whether there is an assignment of true/false values to the literals such that at least a*m clauses will be true. Note that 3-SAT(1) is exactly the 3-SAT problem. Give an O(m*n)-time algorithm that outputs a satisfying assignment for 3-S..

  Sql based question

In order to make the SQL select statements that would manufacture running summary files for reports of the above; how would you answer the questions below?

  Calculate shortest path-djkstra-s shortest path algorithm

With indicated link costs, use Djkstra's shortest path algorithm to calculate shortest path from E to all network nodes. Illustrate how algorithm works by computing table.

  Create algorithm to calculte and print average earnings

Create the algorithm to calculte and print average earnings, lowest earnings, and highest earnings of group of employees. Each input record will contain name and earnings of one employee.

  Professional codes of ethics

Select one of the Professional Codes of Ethics associated with IT. If you were to complete a assignment related to securing the connectivity in your firm and its business partners.

  System analyst

A huge, well regarded supplier of key raw materials to your corporation's production process requires a year-end summary report of totals purchased from it.

  Question about data model

Create a simple data model that outlines a database management system. This model requires to track people's participation in several fitness activities at a fitness center.

  Design a divide-and-conquer algorithm

Design a divide-and-conquer algorithm for the Motif Finding problem and estimate its running time. Have you improved the running time of the exhaustive search algorithm?

  The time delay of a long-distance

The time delay of a long-distance call can be determined by multiplying a small fixed constant by the number of communication links on the telephone network between the caller and callee

  Determine the branching factor

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

  Time n-processor common crcw pram algorithm

present an O(1) time n-processor common CRCW PRAM algorithm for computing the boolean AND of n bits.

  Write control structure-pseudocode algorithm for simple task

Three simple control structures which could be used to make this algorithm. What do you believe is most difficult part of creating algorithm?

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!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +1-415-670-9521

Phone: +1-415-670-9521

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

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