A* search - artificial intelligence, Computer Engineering

Assignment Help:

A* Search - artificial intelligence:

A* search in the combines is the best parts of uniform cost search, namely the fact that it's optimal and complete, and the other best parts of greedy search, namely its speed. This kind of searching strategy simply combines the path cost function g(n)  and the heuristic function  h(n)  by summing them to form a new heuristic measure f(n): 

f(n) = g(n) + h(n) 

Remembering that g(n) gives the path cost from the start state to state  n and h(n) estimates the path cost from n to a goal state, we see that f(n) estimates the cost of the cheapest solution that passes through n. 

The most important aspect of A* search is that, given only one restriction on h(n), it is possible to prove the search strategy there which is complete and optimal. The restriction to h(n) is that it must all the time underestimate the cost to reach a goal state from n. Such heuristic measures are called admissible. Look at Russell and Norvig for proof that A* search with an admissible heuristic is complete and optimal.


Related Discussions:- A* search - artificial intelligence

Avoiding over fitting in decision trees, A v o iding Over fitting - Arti...

A v o iding Over fitting - Artificial intelligence As  we  discussed  in  the last  lecture,  over fitting  is  a  normal  problem  in machine learning. Decision trees suffe

Explain procedure level of parallel processing, Procedure Level Here, p...

Procedure Level Here, parallelism is obtainable in the form of parallel executable procedures. In that case, design of algorithm plays a key role. E.g. every thread in Java is

Basic need of random access memory, Q. Basic need of Random Access Memory? ...

Q. Basic need of Random Access Memory? Main memory is Random access memory. It is generally organised as words of fixed length. Length of a word is termed as word length. Every

Explain the necessary conditions for deadlock to occur, Explain the necessa...

Explain the necessary conditions for deadlock to occur. Conditions for deadlock to arise are: i. Mutual exclusion: At least one resource must be held in a non-sharable mo

Connectives - first-order logic , Connectives - first-order logic: We ...

Connectives - first-order logic: We can string predicates all together in a sentence by using connectives into the same way to conduct that we did for propositional logic. We

What is delegation, What is Delegation? A delegate acts like a strongly...

What is Delegation? A delegate acts like a strongly type function pointer. Delegates can raise the methods that they reference without making explicit calls to those methods. D

Develop a regular expression for integer and identifier, Develop a regular ...

Develop a regular expression for Integer and Identifier (i) A regular expression for integer is [+ | -] (d)+ (ii) A regular expression for identifier is l(l | d)*

Show the properties of text box, Q. Show the properties of Text Box? Th...

Q. Show the properties of Text Box? The tag is used to specify where user input is expected. It has several attributes, of which TYPE attribute is used to specify th

Illustarte basic flip-flops, Q. Illustarte Basic Flip-flops? Let's firs...

Q. Illustarte Basic Flip-flops? Let's first see a ordinary latch. A latch or flip-flop can be created employing two NOR or NAND gates. Figure (a) presents logic diagram for S-R

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