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 a deadlock, What is a Deadlock? Deadlock is a situation, in th...

What is a Deadlock? Deadlock is a situation, in that processes never complete executing and system resources are tied-up, preventing another job form starting. If the resou

Explain file transfer protocol, Explain File Transfer Protocol . FTP is ...

Explain File Transfer Protocol . FTP is utilized to exchange files among computer accounts, to transfer files among an account and a desktop computer (upload) or to access softw

Find the average of two values, Q. Find the average of two values? Find...

Q. Find the average of two values? Find the average of two values which are stored in  ; Memory locations named FIRST and SECOND  ; And puts result in memory location AVG

State the term- $display and $write, State the term- $display and $write ...

State the term- $display and $write $display and $write two are the same except which $display always prints a newline character at the end of its execution.

What is normal form, What is normal form? A normal form is a guideline ...

What is normal form? A normal form is a guideline for relational database tables that enhances data consistency. As tables satisfy higher levels of normal forms, they are less

What is parallel balance point, Q. What is Parallel Balance Point? In ...

Q. What is Parallel Balance Point? In order to execute parallel algorithm on parallel computer K processors are necessary. It should be noted that given input is allocated to

Determine about selective set- logic micro operations, Selective set Th...

Selective set The selective-set operation sets to 1 bits in register A where there can corresponding 1's  in  register  B.  It  does  not  affect  bit  positions  which  have

How to convert binary to octal and hexadecimal, Q. How to convert Binary to...

Q. How to convert Binary to Octal and Hexadecimal? Rules for these conversions are simple. For converting binary to octal binary number is splitted in groups of three, that are

What is jmx, JMX is native to the Java programming language. As a result, i...

JMX is native to the Java programming language. As a result, it offers natural, efficient, and lightweight management extensions to Java-based functions. It has of a set of specifi

K map explanation, K map explanation for mod 5 up synchronous counter ?

K map explanation for mod 5 up synchronous counter ?

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