Effective branching rate - heuristic searches, Computer Engineering

Assignment Help:

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.


Related Discussions:- Effective branching rate - heuristic searches

Compare the memory devices ram and rom, Compare the memory devices RAM and ...

Compare the memory devices RAM and ROM. Ans. Comparison of Semi-conductor Memories RAM ands ROM The advantages of ROM are: 1. This is cheaper than RAM. 2. This is non-volatil

Evaluation stack architecture, Q. Evaluation Stack Architecture? A stac...

Q. Evaluation Stack Architecture? A stack is a data structure which implements Last-In-First-Out (LIFO) access policy. You can add an entry to the with a PUSH(value) as well as

Characteristics of magnetic disk, Q. Characteristics of Magnetic disk? ...

Q. Characteristics of Magnetic disk? Tracks and Sectors: Disk is divided in concentric rings known as tracks. Thus a track is one complete rotation of disk underneath read/wr

What is concurrent control, What is concurrent control? Control resides...

What is concurrent control? Control resides concurrently in various independent objects, every a separate task. A task can wait for input but other task continues implementatio

Define variants of turing machine, Define variants of Turing Machine?  ...

Define variants of Turing Machine?  Variants are  Non deterministic turing machine.  Mutlitape turing  machine.  Enumerators

Multi-threaded processors, The use of distributed shared memory in parallel...

The use of distributed shared memory in parallel computer architecture however the use of distributed shared memory has the problem of accessing the remote memory that results in l

Syntax errors and logical errors, Syntax errors and logical errors: Syn...

Syntax errors and logical errors: Syntax errors also called as compilation errors are caused by violation of the grammar rules of the language. The compiler detects, isolate th

Explain differences between folded and non-folded network, Explain differen...

Explain differences between folded and non-folded network. Folded network: While all the inlets/outlets are connected to the subscriber lines, the logical connection shows as

Properties for of static ram, a) Give eight properties for each of static R...

a) Give eight properties for each of static RAM (SRAM) and DRAM (dynamic RAM) and provide the low-level structure of each type of memory. b) Assume a system with 16 Megabytes o

Illustrate when are intermolecular forces the strongest, Q. Illustrate when...

Q. Illustrate when are intermolecular forces the strongest? Answer:- Intermolecular forces dispersion and dipole-dipole and hydrogen bonds. These forces are feeble than ch

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