Assessing heuristic searches-artificial intelligence, Computer Engineering

Assignment Help:

Assessing Heuristic Searches

Given a specific problem you want to create an agent to solve, there can be more than one way of specifying it as a search problem, more than one option for the search strategy and different possibilities for heuristic measures. To a large extent, it is hard to predict what the best option will be, and it will require some experimentation to find out them. In some kind of cases, - if we calculate the effective branching rate, as described below - we may tell for sure if one heuristic measure is always being out-performed by another.

The Effective Branching Rate

Assessing heuristic functions is an essential part of Artificial Intelligence research: a specific heuristic function can sound like a good idea, but in practice give no discernible increase in the quality of the search. Search quality may be determined experimentally  in  terms  of  the  output  from  the  search,  and  by  using  sevral measures likewise  the effective branching rate. Imagine  a specific  problem P has been solved by search strategy S by expanding N nodes, and the solution lay at depth D in the space. Then the effective branching value of S for P is calculated by comparing S to a uniform search U. An example of a uniform search is a breadth first search where many branches from any node are always the same (as in our baby naming example). We then suppose the (uniform) branching rate of U is like  that, on exhausting its search to depth D, it too would have expanded defiantly N nodes. This imagined branching rate, written b*, is the effective branching rate of S and is calculated thus:

N = 1 + b* + (b*)2 + ... + (b*)D.

Rearranging this equation will give a value for b*. For an example (taken from  Norvig and Russell )imagine S finds a solution at depth 5 having expanded 52 nodes. In this type of case:

 52 = 1 + b* + (b*)2 + ... + (b*)5.

and it turns out that b*=1.91. To calculate its value , we use the well known mathematical identity:

 

This make us enables to write a polynomial for which b* is a 0, and we may solve this using numerical techniques such as Newton's method.

581_Assessing Heuristic Searches.png 
It is typically the case that the effective branching rate of a search strategy is same  over all the problems it is used for, because of this it is suitable to average b* over a small set of problems to give a valid account. If a heuristic search has a branching rate near to 1, then it is a good sign.  We say that 1 heuristic function  h1 dominates another h2 if the search using h1 always has a lower effective branching rate than h2. Having a lower effective branching rate is obviously desirable because it means a quicker search.


Related Discussions:- Assessing heuristic searches-artificial intelligence

Classification based on grain size, Classification Based On Grain Size ...

Classification Based On Grain Size  This classification is based on identifying  the parallelism in a program to be implemented on a multiprocessor system. The plan is to recog

What is the mips assembly code, Question: (a) Using an appropriate dia...

Question: (a) Using an appropriate diagram, illustrate the structure of an instruction used for branching purposes and state the purpose of each part. (b) Given the number

Where time synchronization is necessary, Time synchronization is necessary ...

Time synchronization is necessary in? Time synchronization is essential in TDM.

Explain time switching, Explain Time Switching. Time Switches: The ...

Explain Time Switching. Time Switches: The principle of a time switch is demonstrated in figure. This connects an incoming n channel PCM highway to an outgoing n channel PC

Write an xpath expression, Question: (a) Explain the five different t...

Question: (a) Explain the five different types of element content defined by DTDs. (b) Compare XML schema's against DTDs. (c) Consider the following two element decla

Explain in detail about the random scan display, Explain in detail about th...

Explain in detail about the Random Scan Display   This device using CRT directs the electron beam only to the parts of the screen where a picture is to be drawn. This kind of d

State the datatypes of verilog, State the datatypes of Verilog Verilog....

State the datatypes of Verilog Verilog. Compared to VHDL, Verilog data types are very simple, easy to use and very much geared towards modeling hardware structure as opposed to

Reading decision trees, Reading Decision Trees: However we can justifi...

Reading Decision Trees: However we can justified by see that a link between decision tree representations and logical representations that can be exploited to make it easier t

Determine the decimal equivalent of binary number, The decimal equivalent o...

The decimal equivalent of Binary number 11010 is ? Ans. 11010 = 1 X 2 4 + 1 X 2 3 + 0 X 2 2 + 1 X 2 1 = 26.

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