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

Find fiber distributed data interconnect is an example of, FDDI (Fiber Dist...

FDDI (Fiber Distributed Data Interconnect) is an example of? Fiber Distributed Data Interconnect is an illustration of token ring.

What is delayed branching, What is delayed branching? A method called d...

What is delayed branching? A method called delayed branching can minimize the penalty incurred as a result of conditional branch instructions. The idea is easy. The instruction

Objectives of information distribution, Objectives After studying this ...

Objectives After studying this unit you should be able to: 1. list various types of reprographic methods, 2. describe uses of various kinds of typewriters, 3. explain

Vliw architecture, Vliw Architecture Superscalar architecture was desig...

Vliw Architecture Superscalar architecture was designed to develop the speed of the scalar processor. But it has been realized that it is not easy to execute as we discussed pr

How deep does fifo require to be stop underflow or overflow, Given the subs...

Given the subsequent FIFO and rules, how deep does the FIFO require to be to stop underflow or overflow? RULES: a. frequency(clk_A) = frequency(clk_B) / 4 b. per

Multithreaded architecture, Q. Multithreaded Architecture? It is clear ...

Q. Multithreaded Architecture? It is clear at the moment if we provide a lot of contexts to multiple threads then processors with numerous contexts are known as multithreaded s

Addressing relationship for main memory and cache, Q. Addressing Relationsh...

Q. Addressing Relationship for Main Memory and Cache? In the normal case there are 2k words in cache memory and 2n words in main memory. The n-bits memory address is splitted i

Define a B- tree of order m, Define a B tree of order m. B Tree of orde...

Define a B tree of order m. B Tree of order m  A balanced multiway search tree of order m in which every non root node having at least m/2 keys is known as a B-Tree of order

What is store program control, What is store program control (SPC)?  I...

What is store program control (SPC)?  In  stored  program  control  systems,  a  set  of  instructions  or  program  to  the computer  is  stored  in  its  memory  and  instru

Transport layer, time to left (TTL) in transport layer

time to left (TTL) in transport layer

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