1.
Depth-First Search (DFS)
Algorithm:
Initialize: Place the starting node on a stack.
Loop: a. Pop: Remove the top node from the stack. b. Goal test: If it's the goal
node, return success. c. Expand: Expand the node, adding its children to the stack
in reverse order (LIFO).
Repeat: Continue until the stack is empty.
2. Breadth-First Search (BFS)
Algorithm:
Initialize: Place the starting node in a queue.
Loop: a. Dequeue: Remove the front node from the queue. b. Goal test: If it's the
goal node, return success. c. Expand: Expand the node, adding its children to the
back of the queue (FIFO).
Repeat: Continue until the queue is empty.
3. Depth-Limited Search (DLS)
Algorithm:
Similar to DFS, but with a depth limit. If the search reaches the depth limit, it
backtracks.
4. Iterative Deepening Search (IDS)
Algorithm:
Iterate: Perform DLS with increasing depth limits.
Stop: Stop when the goal is found or the depth limit exceeds the maximum possible
depth.
5. Bidirectional Search
Algorithm:
Initialize: Search from both the start and goal nodes simultaneously.
Meet: Stop when the search frontiers meet.
6. Uniform Cost Search (UCS)
Algorithm:
Initialize:
Place the start node on the open list with a path cost of 0.
Set the path cost of all other nodes to infinity.
Loop: a. Select: Choose the node with the lowest path cost from the open list. b.
Goal test: If it's the goal node, return success. c. Expand: Expand the selected
node, adding its children to the open list with their updated path costs. d.
Update: If a child node is already in the open list and the new path cost is lower,
update its path cost and parent. e. Move: Move the selected node to the closed
list.
Repeat: Continue until the goal node is found or the open list is empty.
7. Best-First Search
Algorithm:
Initialize: Place the start node on the open list.
Loop: a. Select: Choose the node with the lowest heuristic value from the open
list. b. Goal test: If it's the goal node, return success. c. Expand: Expand the
selected node, adding its children to the open list. d. Update: If a child node is
already in the open list and the new heuristic value is lower, update its heuristic
value and parent. e. Move: Move the selected node to the closed list.
Repeat: Continue until the goal node is found or the open list is empty.
Informed Search Algorithms
1. A* Search
A search* is an informed search algorithm that combines the advantages of uniform
cost search (UCS) and greedy best-first search (GBFS). It uses a heuristic function
to estimate the cost to reach the goal, while also considering the actual cost of
the path traversed so far. This combination often leads to more efficient searches
compared to UCS or GBFS alone.
Formula:
A* uses the following formula to prioritize nodes for expansion:
f(n) = g(n) + h(n)
where:
f(n): The estimated total cost of the path from the start node to the goal node
through node n.
g(n): The actual cost of the path from the start node to node n.
h(n): The estimated cost to reach the goal node from node n (heuristic function).
Algorithm:
Initialize:
Place the start node on the open list with f(n) = g(n) + h(n).
Set the path cost of all other nodes to infinity.
Loop: a. Select: Choose the node with the lowest f(n) value from the open list. b.
Goal test: If it's the goal node, return success. c. Expand: Expand the selected
node, adding its children to the open list with their updated f(n) values. d.
Update: If a child node is already in the open list and the new f(n) value is
lower, update its f(n) value and parent. e. Move: Move the selected node to the
closed list.
Repeat: Continue until the goal node is found or the open list is empty.
2. AO* Search
Algorithm:
Similar to A*, but allows for dynamic updates to the heuristic function as more
information becomes available.
