Water Jug problem and TSP (Artificial intelligence Approach)

                                    Water Jug problem(production rules )

Now lets move upon water jug problem. In that ultimately we will have a amount of Water to play with and a jug.

Lets begin.

we have 2 jug say 

1st -->a liters of water.

2nd-->b liters of water.

target volume is say t liters of water.

whats the problem now ..? what is our aim..?

• Our Aim is that we should fill the either of the Jug with t liters of water .
• Target is to achieve t liters of water either in jug 1 or Jug 2. 
• Problem is solvable when t is the multiple of gcd(a,b) and that can be modeled as a search through state space (explained in previous post what is state space).
• The state space search for this search procedure to work can be describe as the set of ordered pair of integers (x,y)such as x belongs to {0,1,2,3..a} and y belongs to {0,1,2,3,b}.
• The initial value is (0,0) and the goal value is (t,y) and(x,t) for all x ,y.
• Now the key is to generate the new state from the existing state or the previous state .
• (x,y)->(a,y) if x<a fill the first jug if is not already full.
• (x,y)->(x,b) id y<b fill the second jug if not already full.
• (x,y)->(0,y)->if x>0 that is empty the 1st jug.
• (x,y)->(x,0)->if y>0 that is empty the  2nd jug.
• (x,y)->min(x+y),a),max(0,x+y-a) if y>0 that is pour from second jug to first jug and vice versa 

The above rules states the production rules for water jug problem.

TSP(Travelling sales man problem different Heuristics )

Statement of a problem-In a Tsp a salesman is to find the Shortest tour of a finite number of cities by visiting each city exactly once and returning to starting city.

Different Heuristic  APPROACHES

1. Nearest neighbor heuristic.

• It is a simple concept 
• Randomly selects a city as the starting node of the path.The next city for inclusion is the city is the unvisited city which is nearest to the last city.
• The process is repeated until all cities have been included .
• finally the last city is joined to the first city to form a tour.
• the running time of this heuristic is found to be n square .

2. Insertion heuristic

• There are three important consideration in insertion Heuristic .

1.Random

2.nearest

3.Farthest

All the above three varies in the way the city is inserted in the tour.

Nearest:- starts with tour of the two cities that are nearest to one other .Than an unvisited city which is selected is nearest to the other to get minimum distance.

Same logic Stands for the farthest and random cities.