Effective branching rate - heuristic searches, Computer Engineering

Effective Branching Rate:

Assessing heuristic functions is an important part of "AI" research: a particular heuristic function may sound such a good idea, but in practice give no discernible increase in the quality of the search. Search quality can be estimated experimentally in terms of the output from the search, so by using various measures such as the effective branching rate. Let suppose a particular problem P has been solved by search strategy S by expanding N nodes, and the solution play at depth D in the space. Then the effective branching rate of S for P is calculated by comparing S just to a uniform search U. The other example of a uniform search is a breadth first search where the number of branches from any node is always the same (as in our baby naming example). After that we suppose the (uniform) branching rate of U is like that, on the exhausting its search to depth D, it too would have expanded exactly N nodes. That should be 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 proper value for b*. For example if we considered that we taken from Russell and Norvig rule, suppose S finds a solution at depth 5 having expanded 52 nodes. As in the above this case:

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

and it turns out that b*=1.91. To calculate this, we can use the very well known mathematical character:

362_Effective Branching Rate.png
This enables us to write a polynomial for which b* is a zero, and we can solve this using numerical techniques like Newton's method.
It is normally the case that the effective branching rate of a search strategy is similar over all the problems. It is may be used for, so that it is acceptable to average b* over a small set of problems to give a valid account. If there is a heuristic search has a branching rate near to 1, then this is a good sign. We state that one 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 clearly desirable because it means a quicker search.

Posted Date: 1/10/2013 4:38:13 AM | Location : United States

Related Discussions:- Effective branching rate - heuristic searches, Assignment Help, Ask Question on Effective branching rate - heuristic searches, Get Answer, Expert's Help, Effective branching rate - heuristic searches Discussions

Write discussion on Effective branching rate - heuristic searches
Your posts are moderated
Related Questions
Reprography: Reprography, as a term, has gained international recognition in 1963. It includes "photocopying , microcopying, duplicating and in-plant printing and is character

Q. Types of messages? The messages can be of many types.  A specific field of all messages may be reserved to signify message type.  The message passing primitives are like thi

A source is an object that produces an event. This happens when the internal state of that object changes in some way. A listener is an object that is notified when an event happen

Although there are no compulsory "c" compiler for this subject, but the compiler we are going to use for this example is the Mingw32 compiler. Download the source code files fro

SUPER COMPUTER The upper end of state of art mainframe machine is the supercomputer. These  are  the  fastest  machines  in  terms  of  processing  speed  and  use multiprocess

Append query can be used if you would like to add new rows of data to an already active table. The process of making an append query follows these steps they are. ? Basic step

How address resolution is performed with table lookup? Explain with the help of a suitable example. The approach of table lookup to address resolution needs a data structure wh

Write a pseudocode for a program that reads a temperature as a whole number from a user and outputs a "probable" season (winter, sprint, summer, or fall) depending on the temperatu

What are the Rules of Timescale directive Rules -  'Timescale directive, like all compiler directives, affects all modules compiled after directive,  whether  in  same  fi