Explain the state space of search problem, Computer Engineering

Assignment Help:

Question:

(a) Assume you are a taxi driver. Your taxi can hold four passengers. Passengers pay a flat fee for a ride to the airport, so your goal is to pick up four passengers and take them to the airport in the smallest number of miles. Your world will be modelled as a graph of locations with distances between them. Some, but not all, of the locations have passengers that you can pick up.

(i) Explain the state space of this search problem.

(ii) What would be a good cost function for this search problem?

(iii) Now, consider a case where passengers have to pay according to how far away they are from the airport when they are picked up (note: they don't pay according to how long a ride they take in your taxi, but according to the length of the shortest path from their pickup point to the airport). Explain the state space for this search problem.

(iv) What would be a good cost function for this version of the problem? You still have desire to save petrol.

(v) Is uniform cost search guaranteed to find the optimal solution in either or both versions of the problem? Justify your answer.

(b)

Give brief definitions of the following terms:
• Constraint satisfaction problem,
• Back-tracking search
• Forward checking
• Arc consistency


Related Discussions:- Explain the state space of search problem

What is an orthogonal base class in c++, If two base classes have no overla...

If two base classes have no overlapping methods or data they are said to be independent of, or orthogonal to each other. Orthogonal in the sense means that two classes function in

What is basic time division switching, What is Basic Time Division Switch...

What is Basic Time Division Switching? Basic Time Division Switching: The functional blocks of a memory based time division switching switch is demonstrated in figure and i

Explain about RISC architecture, Q. Explain about RISC ARCHITECTURE? Le...

Q. Explain about RISC ARCHITECTURE? Let's first list some significant considerations of RISC architecture: 1. RISC functions are kept simple unless there is a very good reas

Identify which stores most no. of bits in memory store, Which of the memori...

Which of the memories stores the most number of bits ? Ans. 5Mx8 = 5 x 220 x 8 = 40M (max).

Children''s game of rock, Design a game application that plays the children...

Design a game application that plays the children's game of rock, paper, scissors. The user enters a letter indicating a choice. The Math.random method is then used to pick a value

Internal organisation of memory chips, expplain in detail the internal orga...

expplain in detail the internal organisation of computer?

Define polling, Define Polling. A Polling process is used to recognize...

Define Polling. A Polling process is used to recognize the highest priority source by software means. In this process there is one common branch address for all interrupts.

What happens if acknowledge() is called within a transaction, As per the JM...

As per the JMS specification, when you are in a transaction, the acknowledge Mode is ignored. If acknowledge() is known as within a transaction, it is ignored.

What is the meaning of toggle in a JK flip flop, In a JK Flip-Flop, toggle ...

In a JK Flip-Flop, toggle means ? Ans. Change the output to the opposite state implies the meas of toggle, in a JK Flip-Flop.

Write Your Message!

Captcha
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