Hill climbing - artificial intelligence , Basic Computer Science

Assignment Help:

Hill Climbing - artificial intelligence:

As we've seen, in some particular problems, searching the search path from primly to goal state is the point of the exercise. In another problem, the path and the artefact at the end of the path are both important, and we often try to find optimal solutions. For a sure set of problems, the path is immaterial, and finding a suitable artefact is the sole purpose of the search. In these types of cases, it doesn't matter whether our agent searches a path for ten or thousand steps, so long as it finds a solution in the end.

Take an example of the 8-queens problem, where the job is to find an arrangement of 8 queens on a chess board likewise that no one can "take" another (one queen can take another if it's on the same horizontal, vertical or diagonal line). A solution to this problem is:

 

287_Hill Climbing.png

One way to describe this problem is with states where there are many queens (1 to 8) on the board, and an action is to add a queen in that kind of way that it can't take another. Depending on your method, you can find that this search requires much back-tracking, for example , towards the end, you find that you  just simply can't put the last queens on anywhere, so you have to move one of the queens you put down earlier (you go back-up the search tree).

Another way of specifying the problem is that the states are boards with eight queens already on them, and a stroke is a movement of one of the queens. In this particular case, our agent might be use an evaluation function and do hill climbing. i.e., it measures the number of pairs of queens where one can take the other and only moves a queen if that movement reduces the number of pairs. When there is an option of movements both resulting in same amount of decrease, the agent may select one arbitrarily from the option. In the 8-queens problem, there are just 8 * 56 = 448 probable ways to move one queen, so our agent only has to calculate the evaluation function 448 times at each stage. If it just selected moves where the situation with respect to the evaluation function improves, it is doing hill climbing (or gradient descent if it's better to think of the agent going downhill rather than uphill).

A general problem with this search method is local maxima: the search has not yet reached a solution, but it can just go downhill in terms of the evaluation function. I.e., we might get to the stage where only 2 queens may take each other, but moving any queen increases this number to at least three. In such a cases, the agent may do a random re-start whereby they randomly choose a state to start the complete process from again. This search scheme has the appeal of never requiring storing more than one state at any one time (the part of the hill the agent is on). Russell and Norvig make the analogy that this kind of search is like trying to climb Everest in the fog with amnesia, but they do concede that it is frequently the search strategy of option for some industrial problems.Local/Global Maxima/Minima are represented in the diagram below:

899_Hill Climbing1.png


Related Discussions:- Hill climbing - artificial intelligence

Definition of procedure, A procedure is a compilation of instructions to wh...

A procedure is a compilation of instructions to which we can express the flow of our program, and once the execution of these instructions is over power is given back to the next l

File management, File Management:   The concept of a file is central t...

File Management:   The concept of a file is central to the effective use of a computer system. A file is generally loosely defined as a collection of related information such

Algorithmic, define it #Minimum 100 words accepted#

define it #Minimum 100 words accepted#

Conditional statement, Conditional statement: An If statement is comp...

Conditional statement: An If statement is composed of three parts. The first part should be keyword w.r.t language to convey to the computer that it is if statement. And a Bo

Artificial intelligence-search in problem solving, Search in Problem Solvin...

Search in Problem Solving If Artificial Intelligence can notify the extra sciences about something, it is about trouble solving and, in exacting, how to search for solutions to

Data structures hw help, Create an implementation of the Ordered Associativ...

Create an implementation of the Ordered Associative Array API using left-leaning red-black trees. Illustrate the use of the API by refactoring your WordBench as a client of Ordered

C programming, a cloth merchant A cloth showroom has announced the followin...

a cloth merchant A cloth showroom has announced the following seasonal discounts on purchase of items: Purchase amount Discount Mill items Handloom items 0-100 - 5% 101-200 5% 7.5%

A* search-artificial intelligence, A* Search-Artificial intelligence:  ...

A* Search-Artificial intelligence:   A* search combines the best parts of uniform cost search that  called the fact that it's optimal and complete, and the best parts of gre

Definition of algorithm , Definition of  Algorithm  An algorithm is a ...

Definition of  Algorithm  An algorithm is a design or plan of obtaining a solution to a problem. The solution is presented by listing all steps in which they are carried out.

Understanding human intelligence in social, Understanding human intelligenc...

Understanding human intelligence in social AI can be taken as just the current tool in the philosopher's toolbox for answering of questions for the behaviour of human intellig

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