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
Q. How to input to circuit? Register A bits as a0, a1, a2 and a3 in the corresponding X bits of the Full Adder (FA). Register B bits as given in the Figure above as in

Problem: a) Authoring tools consist of two basic features. First, an authoring facility for creating and editing, and second, a presentation vehicle for delivery. The authorin

Which is more efficient, a switch statement or an if else chain? Ans) The differences, if any, are likely to be small. The switch statement was designed to be efficiently impl

What is reduction?  A reduction is a way of changing one problem into another in such a way that a solution to the second problem can be used to explain the first problem.

Computer Concepts & C Programming 1. Write a program to read four floating point numbers and find their sum and average. 2. What is the difference between string constants a

What are Addressing Modes Many of instructions that a computer actually executes during running of a program concern movement of data to and from memory. It is not possible sim

What is the need of MODEM in data communication? Need of Modem: Modems are utilized to interface computer networks, computers and other terminal equipment for radio channels

And-Elimination rule: In generally English says that "if you know that lots of things are all true, so you know like any one of them is also true". Because you can specify a c

How does one arrive at the probability of availability of free lines during the busy hour? One can arrive at the possibility of free lines throughout busy hour using the delay

This unit introduces the most important ID terminology, explains why ID is important, and gives a description of the main ID activities and the characteristics of the ID process. I