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
What is bus arbitration? It is method by which the next device to become the bus master is selected and bus mastership is transferred to it. There are two ways for doing this:

Your professor wants you to fill a two-dimensional N by N matrix with some numbers by following a specific pattern. According to his explanation as in the figure below, you have to

Q. Illustrate Minimization of Gates? The generalization of Boolean expression is much useful for combinational circuit design. The subsequent three techniques are used for this

Approach to reasoning - first-order logic: The formal approach to reasoning has bigger return and disadvantages. In generally we notice, if a computer program has proved somet

Briefly explain how server form post-back works?  Post Back: The process in which a Web page sends data back to the similar page on the server. View State: View State is the m

1. Introduction to Software Metrics in Software Engineering.? 2. Role of direct and indirect measures in software process management? 3. Stance taken and justification? 4. Conclusi

What is graceful degradation? In multiprocessor systems, failure of one processor will not halt the system, but only slow it down by sharing the work of failure system by other

Explain in brief about the broadband It isn't just computers which can be linked without wires, different peripheral devices can be linked to a computer system without the need

Question : (a) "Resolution refers to the sharpness and clarity of an image" (i) Explain what you understand by the above statement. (ii) What is the difference between D

Problem Solving In Parallel Introduction to Parallel Computing This section examines how a particular task can be broken into minor subtasks and how subtasks can be answer i