### Determine the branching factor

Assignment Help Data Structure & Algorithms
##### Reference no: EM131477

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.

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.

#### Questions Cloud

 Write an essay on fdi in nehterlands : Write an essay on FDI in Nehterlands Examine the boxplot : Examine the boxplot and briefly discuss the overall pattern of electricity usage for the households. Write a research paper in relation to a software design : Research paper in relation to a Software Design related topic Statistical interpretation on junk food : Support colour-coding on packaged food to indicate healthier options 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. Evaluation of project proposals : The atmospheric pressure of 100k Pa acts on the other side of the piston. The gas is heated until the volume is doubled and the final pressure is 500 kPa. Calculate the work done by the gas. Evaluate the work done by the gas : The atmospheric pressure of 100k Pa acts on the other side of the piston. The gas is heated until the volume is doubled and the final pressure is 500 kPa. Calculate the work done by the gas. Questions based on binomial distribution : Questions based on binomial distribution, variance of the binomial distribution, discrete random variable and continuous random variables. Questions regarding the cola wars : Strategies of Pepsi as well of Coke contributed to the situation of cola war

### Write a Review

#### Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

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

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

#### Survey of fault tolerance policy for load balancing scheme o

This paper investigates about fault-tolerance in load balancing schemes in distributed environment. There are some more parameters influencing QOS but our main focus is on fault tolerance and load balancing.

#### Use a search tree to find the solution

Explain how will use a search tree to find the solution.

#### How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

#### Data structures for a single algorithm

Data structures for a single algorithm

#### Describe sorting algorithms and how they work

Describe sorting algorithms and how they work

#### Write the selection sort algorithm

Write the selection sort algorithm

#### Different applications of data structure

What are the different applications of Data Structure

#### Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

#### Write a c++ program to find the intersection

Write a C++ program to find the intersection, A set is a collection of distinct entities regarded as a unit, being either individually specified or (more usually) satisfying specified conditions.

#### Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.