ai

 

Every problem is a graph search problem, as long as we can figure out the right graph to search”
So, there is a set of Possible Solutions and connections between the Possible Solutions.

Classical Search Algorithms are Depth First Search, Breadth First Search, Hill Climbing

Evaluation of search strategies is based on completeness, time complexity, space complexity and optimality.

Search Problems:

General Problem Solving is done using Blind Search, Heuristic Search and Combinatorial Search.

Blind Search:

– do not use any extra information regarding the problem, typically visit all of the nodes of a tree, no cleverness to decide where to look next, may never find the goal state.

Path finding problem can be solved using depth search and breadth first search.

Graph Searching Problems maintain a frontier of paths from the start node that have been explored to unexplored nodes until a goal node is encountered.

Water Jug Problem:

x = gallons in the 4 gallon jug

y = gallons in the 3 gallon jug

state space = (x,y)

start state = (0,0)

Blind Search Methods:

1. Depth First Search – dive into a graph and follow a single path as far as possible, uses stack to keep track of nodes.

2. Breadth First Search – slow descent method, uses queues to keep track of nodes. weakness is exponential growth.

 

Informed Search :

– uses domain specific information to improve the search pattern, define a heuristic function h(n) that estimates the goodness of a node n.

h(n) >= 0 for all nodes n, h(n) = 0 implies n is a goal node and h(n) = infinity implies n is a dead end from which a goal cannot be reached.

Hill Climbing Search (type of informed search) – is a depth first search, which uses some knowledge such as estimates of distance of each node from the goal to improve the search. These estimates are called heuristics.

Beam Search – is a breadth first search using knowledge of the search problem(heuristic), do sorting based on heuristics, follow only the best w nodes to the next level.

Optimal Search Methods:

– find the best path between two nodes.

Branch and Bound Search – at each step find the best path so far and extend it to the next level.

A* algorithm is a B&B with both improvements added. thee total distance value at each stage is

f*(n) value of the path = g*(n) cost of the path from the root to n + h*(n) estimate of the cost from n to the goal.

g*(n) is breadth first component and h*(n) is depth first component.

Simulated Annealing:

– select random solution point x and evalute y, next pick adjacent point x1 at random and evaluate y1 with probability p = 1 /(1+ e(y1-y)/T) and set T = rT, if T >Tmin go to step 2 otherwise to step 1.

 

 

 TABU Search:

– remember the best move, neighborhood search algorithm like simulated annealing.

– consists an initial state, a search neighbourhood, a move evaluator(fitness function), tabu criteria, aspiration criteria and one or more tabu lists.

Ant Colony Search:

– swarm intelligence

-TSP, routing and telecommunication uses this.

– decision based on amount of pheromones along the trails