Steepest Hill Climbing

A useful variation on simple hill climbing considers all the moves from the current state and selects the best one as the next state. This method is called steepest-ascent hill climbing or gradient search.

Algorithm:

1. Evaluate the initial state. If it is also a goal state then return it and quit. Otherwise continue with the initial state as the current state.

2. Loop until a solution is found or until a complete iteration produces no change to current state:

a. Let SUCC be a state such that any possible successor of the current state will be better than SUCC.

b. For each operator that applies to the current state do:

i. Apply the operator and generate a new state.

ii. Evaluate the new state. If it is a goal state, then return it and quit. If not compare it to SUCC. If it is better, then set SUCC to this state. If it is not better, leave SUCC alone.

c. IF the SUCC is better than current state, then set current state to SUCC.

Bothe basic and steepest-ascent hill climbing may fail to find a solution. Either algorithm may terminate not by finding a goal state but by getting a state from which no better states can be generated. This will happen if the program has reached a local maximum, a plateau or a ridge.

A local maximum is a state that is better than all its neighbors but it not better than some other states farther away. At the local maximum, all moves appear to make things worse. Local maxima are particularly frustrating because they often occur almost within sight of a solution. In this case, they are called foothills.

neighboring states Direction in which to

A

plateau

is a flat area of the search space in which a whole set of has the same value. In this, it is not possible to determine the best d move by making local comparisons.

A ridge is a special kind of maximum. It is an area of the search space that is higher than surrounding areas and that itself has a slope.

There are some ways of dealing with these problems, although these methods are by no means guaranteed:

I. Backtrack to some earlier node and try going in a different direction. This is particularly reasonable if at that node there was another direction that looked as promising or almost as promising as the one that was chosen earlier. This is a fairly good way to deal with local maxima.

II. Make a big jump in some direction to try to get to a new section of the search space. This is a good way of dealing with plateaus.

III. Apply two or more rules before doing the test. This corresponds to moving in several directions at once. This is a good strategy for dealing with ridges.

Goal State:

a. We have to assign unique digit for the above specified alphabets.

Intelligence:

It is the knowledge in operation towards the solution - how to do? How to apply the solution?

Artificial Intelligence:

Artificial intelligence is the study of how make computers to do things which people do better at the moment. It refers to the intelligence controlled by a computer machine.

One View of AI is

I. About designing systems that are as intelligent as humans

II. Computers can be acquired with abilities nearly equal to human intelligence

III. How system arrives at a conclusion or reasoning behind selection of actions

IV. How system acts and performs not so much on reasoning process.

Why Artificial Intelligence?

I. Making mistakes on real-time can be costly and dangerous.

II. Time-constraints may limit the extent of learning in real world.

Task domain = Refer 4^th Question & Answer

Production System

The entire procedure for getting a solution for AI problem can be viewed as "Production System". It provides the desired goal. It is a basic building block which describes the AI problem and also describes the method of searching the goal. Its main components are:

I. A Set of Rules, each consisting of a left side (a pattern) that determines the applicability of the rule and right side that describes the operation to be performed if the rule is applied.

II. Knowledge Base - It contains whatever information is appropriate for a particular task. Some parts of the database may be permanent, while the parts of it may pertain only to the solution of the current problem.

III. Control Strategy - It specifies the order in which the rules will be compared to the database and the way of resolving the conflicts that arise when several rules match at one.

a. The first requirement of a goal control strategy is that it is cause motion; a control strategy that does not cause motion will never lead to a solution.

b. The second requirement of a good control strategy is that it should be systematic.

IV. A rule applier: Production rule is like below if(condition) then consequence or action

Algorithm for Production System:

1. Represent the initial state of the problem

2. If the present state is the goal state then go to step 5 else go to step 3

3. Choose one of the rules that satisfy the present state, apply it and change the state to new state.

4. Go to Step 2

5. Print "Goal is reached " and indicate the search path from initial state to goal state 6. Stop

Classification of Production System:

Based on the direction they can be

1. Forward Production System

a. Moving from Initial State to Goal State

b. When there are number of goal states and only one initial state, it is advantage to use forward production system.

2. Backward Production System

a. Moving from Goal State to Initial State

b. If there is only one goal state and many initial states, it is advantage to use backward production system.

Production System Characteristics

Production system is a good way to describe the operations that can be performed in a search for solution of the problem.

Two questions we might reasonably ask at this point are:

a. Can production systems, like problems, be described by a set of characteristics that shed some light on how they can easily be implemented?

b. If so, what relationships are there between problem types and the types of production systems best suited to solving the problems?

The answer for the first question can be considered with the following definitions of classes of production systems:

A monotonic production system is a production system in which the applications of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was selected.

A non-monotonic production system is one which this is not true.

Refer 1^st Question & Answer OR CLICK HERE