Many problems in AI can be reduced to search problems, uninformed search algorithms like BFS, DFS, Dijkstra's algorithms are not efficient for complex problems, here informed or heuristic search algorithms come to play. They can be used to find a complex solution from a really large state space and they will reach the goal much faster and optimally.
With broad search spaces, the knowledgeable search algorithm is more efficient. The informed search algorithm uses the heuristic idea, so the heuristic search is also used to name it.
The two major informed search algorithms are : Best First Search Algorithm(Greedy search), A* Search Algorithm
Artificial Intelligence: Informed Search Algorithms
With broad search spaces, the knowledgeable search algorithm is more efficient. Informed search algorithm uses the heuristic idea, so heuristic search is also used to name it.
Heuristic: Heuristic is a task used in Informed Search and identifies the most promising course. It takes the agent's current state as its source and calculates how near the agent is from the target. Nevertheless, the heuristic approach may not always provide the best solution, but in a reasonable time it promised to find a good answer.
The simplest form of heuristic search algorithms is pure heuristic search. Based on their heuristic value, it extends nodes h(n). It has two lists, the list OPEN and the list CLOSED. It places the nodes that have already expanded in the CLOSED list, and it places nodes that have not yet been expanded in the OPEN list.
Each n node with the lowest heuristic value is expanded on each iteration, generating all its successors and placing n on the closed list. The algorithm moves on unit seeking a target condition.
The two major informed search algorithms are :
- Best First Search Algorithm(Greedy search)
- A* Search Algorithm
Best First Search:
Best first search is a graph search algorithm instance where a node is selected for expansion-based evaluation function f(n). Traditionally, because the measurement tests distance to the target, the node that is the lowest evaluation is chosen for the clarification. In general search frame work, the best first search can be done via a priority queue, a data structure that holds the fringe in ascending f value order. This search algorithm serves as the first search algorithm combining depth and breadth.
// This pseudocode is adapted from below
// source:
Best-First-Search(Grah g, Node start)
1) Create an empty PriorityQueue
PriorityQueue pq;
2) Insert "start" in pq.
pq.insert(start)
3) Until PriorityQueue is empty
u = PriorityQueue.DeleteMin
If u is the goal
Exit
Else
Foreach neighbor v of u
If v "Unvisited"
Mark v "Visited"
pq.insert(v)
Mark u "Examined"
End procedure
A* Search:
A * is a graph and path search algorithm that is commonly used in computer science due to its completeness, optimality, and maximal performance. A big technical disadvantage is the complexity of its storage, as it stores all nodes generated in memory. A* is the most common pathfinding option because it is quite versatile and can be used in a wide variety of contexts. A* is like other graph-searching algorithms because it is capable of theoretically looking for a large map region. It's like the algorithm of Dijkstra in that finding a shortest path can be used. It's like Greedy Best-First-Search because it can be driven by a heuristic.
A* search is the best-first search form most commonly known. It uses heuristic h(n) function, and costs the g(n) starting state to reach node n. It has combined UCS and greedy best-first search features to effectively solve the problem. A* search algorithm uses the heuristic function to find the shortest path through the search space. This search algorithm expands less search tree and delivers faster optimum results. A* algorithm is identical to UCS when g(n)+h(n) is used instead of g(n).
Algorithm
Step 1: Place the starting node in the OPEN list.
Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure and stops.
Step 3: Select the node from the OPEN list which has the smallest value of evaluation function (g+h), if node n is goal node then return success and stop, otherwise
Step 4: Expand node n and generate all of its successors, and put n into the closed list. For each successor n', check whether n' is already in the OPEN or CLOSED list, if not then compute evaluation function for n' and place into Open list.
Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the back pointer which reflects the lowest g(n') value.
Step 6: Return to Step 2.
Many problems in AI can be reduced to search problems, uninformed search algorithms like BFS, DFS, Dijkstra's algorithms are not efficient for complex problems, here informed or heuristic search algorithms come to play. They can be used to find a complex solution from a really large state space and they will reach the goal much faster and optimally.
