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

Categorize the cpu scheduling algorithms, Categorize the CPU scheduling alg...

Categorize the CPU scheduling algorithms? The various CPU scheduling algorithms are categorized as given below:

Sorting using interconnection networks, The combinational circuits employ t...

The combinational circuits employ the comparators for comparing the numbers and storing them on the basis of maximum and minimum functions. Likewise in the interconnection networks

Virtual memory - computer architecture, Virtual memory: Virtual memory...

Virtual memory: Virtual memory is a technique which realized an application program the idea that it has contiguous working memory (an address space), whereas in fact it may b

What is a size category, What is a Size Category? The Size category ve...

What is a Size Category? The Size category verifies the probable space needs of the table in the database.

What is guard bits, What is guard bits? Guard bits are extra bits which...

What is guard bits? Guard bits are extra bits which are produced while the intermediate steps to yield maximum accuracy in the final results.

Handling multiple devices - computer architecture, Handling Multiple Device...

Handling Multiple Devices Interrupt Priority   Continue to accept interrupt requests from higher priority components   Disable interrupts from component at the sa

Will case infer priority register if yes how give an example, Will case inf...

Will case infer priority register if yes how give an example? Yes case can infer priority register depending on coding style reg r; // Priority encoded mux, always @

E-r diagrams, for ticket reservation in trains for payroll processing for i...

for ticket reservation in trains for payroll processing for insurance database

How e-commerce works for the customer, The customers visit the website and ...

The customers visit the website and browse through the products, looking at pictures and products details. When the customer finds his desired product, he usually adds it to his ca

Low level language program, The commands (instructions) are native instruct...

The commands (instructions) are native instructions to the 68HC11 and therefore it is termed a low level language program. Examining the program the instructions (mnemonics) they a

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