BFS Algorithm (Step-Wise, Simple Explanation)
Goal:
To explore all nodes of a graph level-by-level starting from a given start node.
Algorithm Steps
1. Start with the initial node.
o Mark it as the starting point.
2. Create an empty queue.
o This queue will store nodes to be visited.
3. Enqueue (insert) the start node into the queue.
o Also mark it as visited so you don’t visit it again.
4. Repeat the following until the queue becomes empty:
a. Dequeue (remove) a node from the queue.
o Call this node the current node.
b. Process the current node.
o (Processing can be printing, checking, or storing the node.)
c. Visit all unvisited neighbors of the current node:
o For each neighbor:
1. If it is not visited:
Mark it as visited.
Enqueue it into the queue.
5. Stop when the queue is empty.
o All reachable nodes have been visited in BFS order.
Key Idea
BFS explores level by level (first neighbors, then neighbors of neighbors).
DFS Algorithm (with “Successors” wording)
Steps:
1. Start at the initial state (start node).
2. Mark the initial state as visited.
3. Process the state
(example: print it, record it, or check if it’s the goal).
4. For each successor of the current state:
o If the successor is not visited:
Apply DFS recursively on that successor.
5. Backtrack when a state has no unvisited successors.
Bidirectional Search
1. Start two searches at the same time:
o One from the initial state
o One from the goal state
2. Expand nodes forward from the start.
3. Expand nodes backward from the goal.
4. After each expansion, check if the two searches meet.
5. If they meet at any node → solution is found
(the path is start → meeting point → goal).
6. Stop when the frontiers meet.
Hill Climbing
1. Start with an initial state.
2. Look at all neighboring states (successors).
3. Pick the neighbor that has the best value.
4. If the neighbor is better than the current state → move to it.
5. If no neighbor is better → stop.
(You reached a peak/local maximum.)
6. Repeat steps 2–4 until you cannot improve.
Steepest-Ascent Hill Climbing
1. Start with an initial state.
2. Generate all successors (neighbors).
3. Evaluate each successor’s value.
4. Choose the successor with the highest value
(the steepest upward climb).
5. If the best successor is better than the current state → move to it.
6. If none of the successors are better → stop.
7. Repeat steps 2–5 until no improvement is possible.
Best-First Search
1. Start with the initial node and put it into OPEN list.
2. Keep OPEN list sorted by heuristic value h(n)
(the node with lowest h(n) is considered best).
3. Repeat the following steps:
a. Select the node from OPEN with the lowest heuristic value.
b. Move it to CLOSED (already explored).
c. If this node is the goal, stop — solution found.
d. Generate all successors of the selected node.
e. For each successor:
o Compute its heuristic value h(n).
o If not in OPEN or CLOSED → add it to OPEN.
o If already present → keep the one with better (smaller) h(n).
4. Continue until the goal is found or OPEN list becomes empty.
A* Algorithm
1. Initialize OPEN list with the start node.
(OPEN = nodes to be explored)
2. Initialize CLOSED list as empty.
(CLOSED = nodes already explored)
3. Repeat until goal is found:
a. Pick the node from OPEN with the smallest f(n).
b. Move it to CLOSED.
c. If this node is the goal, stop (solution found).
d. Generate all of its successors.
e. For each successor:
o Compute g(n), h(n), and f(n)
o If successor is not in OPEN or CLOSED → add it to OPEN
o If already present → keep the one with the lower f(n)
4. Continue until the goal is selected for expansion.
5. Reconstruct the path from start to goal.
AO* Steps
1. Start at the initial node.
2. Expand (open) nodes using heuristic values (like A*).
3. If the node is:
o OR node: choose the child with the lowest cost
o AND node: add the costs of all children
4. Update costs of parents.
5. Mark the current best solution path (the solution graph).
6. Repeat until the best path leads only to goal nodes.
Minimax Algorithm
1. Start at the current game state (root).
2. Generate all possible moves for both players
→ MAX player (tries to win)
→ MIN player (opponent tries to reduce MAX’s score)
3. Go down the game tree until you reach terminal states
(win / lose / draw or leaf nodes).
4. Assign values to terminal states
(example: win = +1, lose = –1, draw = 0).
5. Backtrack upward:
o At MAX nodes → choose the maximum value.
o At MIN nodes → choose the minimum value.
6. Propagate the chosen values upward to the root.
7. The root’s final value tells the best move.
Choose the move that leads to that value.
Alpha–Beta Pruning
1. Alpha–Beta pruning works like the Minimax algorithm but cuts o unnecessary
branches.
2. Keep two values:
o Alpha (α): best value found for MAX so far
o Beta (β): best value found for MIN so far
3. At a MAX node, update α whenever a larger value is found.
4. At a MIN node, update β whenever a smaller value is found.
5. If α ≥ β at any point, stop exploring the remaining branches because they cannot
influence the final decision.
6. Continue until all useful nodes are evaluated, and return the best value.
Algorithm for Solving a Constraint Satisfaction
1. Choose a variable that is not yet assigned a value.
2. Select a value from the variable’s domain.
3. Check consistency:
o If the chosen value does not violate any constraint with already-assigned
variables → accept it.
o If it violates a constraint → try the next value.
4. Assign the value to the variable.
5. Repeat Steps 1–4 for the next variable.
6. If no value works:
o Backtrack to the previous variable and try a di erent value.
7. Stop when all variables have legal values → solution found.