Artificial Intelligence is the study of building agents that act rationally. Most of the time, these agents perform some kind of search algorithm in the background in order to achieve their tasks.
The objective of search procedure is to discover a path through a problem spaces from an initial configuration to a goal state.
The Solution to a search problem is a sequence of actions, called the plan that transforms the start state to the goal state.
This plan is achieved through search algorithms.
No need to install anything but it is for WINDOWS OS
Eclipse IDE & JVM will be required.
Assume that above Graph will be used by User.
Also called as Blind Search or Brute Force Search.
Suitable For very limited Problem Space problems.
A blind search is a search that has no information about its domain. The only thing that a blind search can do is to distinguish a non-goal state from a goal state.
– Breadth-First search
– Depth-First search
– Uniform-Cost search
– Depth-First Iterative Deepening search
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures.
It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.
Breadth First Search explores the state space in a level by level fashion. Only when there are no more states to be explored at a given level then the algorithm move onto the next level.
BFS is complete. If there exists an answer, it will be found (b should be finite).
BFS is optimal (if cost = 1 per step). The path from initial state to goal state is shallow.
Time & Space Complexity = s O(b^d) Where "b" = Branch Factor (Number of nodes from root first expands on a set number of nodes, say b.)
& "d" = depth
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root and explores as far as possible along each branch before backtracking.
A depth first search begins at the root node (i.e. Initial node) and works downward to successively deeper levels.
An operator is applied to the node to generate the next deeper node in sequence. This process continues until a solution is found or backtracking is forced by reaching a dead end.
If you have deep search trees (or infinite – which is quite possible), DFS may end up running off to infinity and may not be able to recover.
Thus DFS is neither optimal nor complete
Time & Space Complexity = s O(b^d) {In some cases, DFS can be faster than BFS because it does not expand all nodes at a level}
Where "b" = Branch Factor (Number of nodes from root first expands on a set number of nodes, say b.)
& "d" = depth
Depth-first search will not find a goal if it searches down a path that has infinite length. So, in general, depth-first search is not guaranteed to find a solution, so it is not complete.
This problem is eliminated by limiting the depth of the search to some value l. However, this introduces another way of preventing depth-first search from finding the goal: if the goal is deeper than l it will not be found.
Regular depth-first search is a special case, for which l=∞.
Depth limited search is complete but not optimal.
If we choose a depth limit that is too small, then depth limited search is not even complete.
The time and space complexity of depth limited search is similar to depth first search.
Breadth-first search finds the shallowest goal state, but this may not always be the least-cost solution for a general path cost function.
Uniform cost search modifies the breadth-first strategy by always expanding the lowest-cost node rather than the lowest-depth node.
It maintain a "Priority Queue".
Uninformed search strategies can find solutions to problems by systematically generating new states and testing them against the goal.
Unfortunately, these strategies are incredibly inefficient in most cases.
Uninformed search uses problem-specific knowledge—can find solutions more efficiently.
Heuristics are "rules of thumb", educated guesses, intuitive judgments or simply common sense.
A heuristic function, h(n), provides an estimate of the cost of the path from a given node to the closest goal state.
Must be zero if node represents a goal state.
– Greedy-Best-First search
– A * search
Depth first search is good because it allows a solution to be found without all competing branches to be expanded.
Breadth first search is good because it does not get trapped on dead-end paths.
Best First Search combines the advantages of the two.
At each step of the best first search process, we select the most promising of the nodes we have generated so far.
This is done by applying an appropriate heuristic function to each of them.
Greedy Best-First search tries to expand the node that is closest to the goal assuming it will lead to a solution quickly.
-
f(n) = h(n)
-
f(n) = Function that gives an evaluation of the state.
-
h(n) = The cost of getting from the current state to a goal state.
The Greedy Best-First-Search algorithm works as uniform cost search, except that it has some estimate (called a heuristic) of how far from the goal any node is.
Instead of selecting the node closest to the starting point, it selects the node closest to the goal.
Greedy Best-First-Search is not guaranteed to find a shortest path.
However, it runs much quicker than uniform cost search algorithm because it uses the heuristic function to guide its way towards the goal very quickly
Greedy Search minimizes a heuristic h(n) which is an estimated cost from a node n to the goal state. However, although greedy search can considerably cut the search time (efficient), it is neither optimal nor complete.
Uniform Cost Search minimizes the cost g(n) from the initial state to n. UCS is optimal and complete but not efficient
** New Strategy: Combine Greedy Search and UCS to get an efficient algorithm which is complete and optimal. **
A search algorithm to find the shortest path through a search space to a goal state using a heuristic.
- f(n) = g(n) + h(n)
- f(n) = Function that gives an evaluation of the state.
- g(n) = The cost of getting from the initial state to the current state.
- h(n) = The cost of getting from the current state to a goal state.
It is Efficient.
It is complete.
It is Optimal.
