Assessing heuristic searches-artificial intelligence, Computer Engineering

Assignment Help:

Assessing Heuristic Searches

Given a specific problem you want to create an agent to solve, there can be more than one way of specifying it as a search problem, more than one option for the search strategy and different possibilities for heuristic measures. To a large extent, it is hard to predict what the best option will be, and it will require some experimentation to find out them. In some kind of cases, - if we calculate the effective branching rate, as described below - we may tell for sure if one heuristic measure is always being out-performed by another.

The Effective Branching Rate

Assessing heuristic functions is an essential part of Artificial Intelligence research: a specific heuristic function can sound like a good idea, but in practice give no discernible increase in the quality of the search. Search quality may be determined experimentally  in  terms  of  the  output  from  the  search,  and  by  using  sevral measures likewise  the effective branching rate. Imagine  a specific  problem P has been solved by search strategy S by expanding N nodes, and the solution lay at depth D in the space. Then the effective branching value of S for P is calculated by comparing S to a uniform search U. An example of a uniform search is a breadth first search where many branches from any node are always the same (as in our baby naming example). We then suppose the (uniform) branching rate of U is like  that, on exhausting its search to depth D, it too would have expanded defiantly N nodes. This 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 value for b*. For an example (taken from  Norvig and Russell )imagine S finds a solution at depth 5 having expanded 52 nodes. In this type of case:

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

and it turns out that b*=1.91. To calculate its value , we use the well known mathematical identity:

 

This make us enables to write a polynomial for which b* is a 0, and we may solve this using numerical techniques such as Newton's method.

581_Assessing Heuristic Searches.png 
It is typically the case that the effective branching rate of a search strategy is same  over all the problems it is used for, because of this it is suitable to average b* over a small set of problems to give a valid account. If a heuristic search has a branching rate near to 1, then it is a good sign.  We say that 1 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 obviously desirable because it means a quicker search.


Related Discussions:- Assessing heuristic searches-artificial intelligence

Compact disc - computer storage, Compact Disc; Compact Disc ( CD)   i...

Compact Disc; Compact Disc ( CD)   is an optical disc  which is used to  store digital data. It was initially developed to store sound recordings completely, but later it als

Describe about modem language, Q. Describe about Modem Language? Modems...

Q. Describe about Modem Language? Modems understand a set of instructions known as Hayes Command Set or AT Command Set. These commands are used to communicate with Modem. At ti

How can we use metropolitan area network, Q. How can we use Metropolitan Ar...

Q. How can we use Metropolitan Area Network? A MAN, essentially a bigger versions of a LAN is designed to extend over an entire city. It may be single network like a cable tele

What is deadlock in operating system, Explain Deadlock in operating system ...

Explain Deadlock in operating system ? Deadlock: all process in a set of processes is waiting for an event which only a process in the set can cause.

Write a program to input an address, Write a program to input an address i....

Write a program to input an address i.e. 20 Hex and read the byte (char) contents of that address   Answer   include void main() { char prompt; Date: 26th August 2012

Determine the hardware for multiplication, Determine the hardware for multi...

Determine the hardware for multiplication The hardware for multiplication consists of equipment given in Figure. The multiplier is stored in register and its sign in Q . The se

Functions of an operating system, Question a) In multitasking Operatin...

Question a) In multitasking Operating Systems, there are two kinds of multitasking such as the "Preemptive Multitasking" and the "Cooperative Multitasking". Explain the two me

Explain routing tone in strowger telephony, Explain routing tone in strowge...

Explain routing tone in strowger telephony with waveforms and the timings. The call-in-progress tone or routing tone is a 400 Hz or 800 Hz intermittent pattern. In electromec

Address phase timing - computer architecture, Address phase timing: On...

Address phase timing: On the rising edge of clock 0, the initiator notes IRDY # and FRAME# both high, and GNT# low, so it drives the command, address and asserts FRAME# in tim

Define race condition, Define race condition.  When several process acc...

Define race condition.  When several process access and manipulate similar data concurrently, then the outcome of the implementation depends on particular order in which the ac

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