This article provides an Artificial Intelligence midterm exam study guide for students. The contents are summarized concisely with detailed algorithm illustrations.

Artificial Intelligence Midterm Exam Study Guide

What is a Heuristic Function?

Heuristic is an evaluation function estimating the likelihood of reaching a solution. Denoted as h.

1. Breadth-First Search (BFS)

Breadth-first search uses the FIFO (First In, First Out) mechanism — QUEUE — First in, First out.

Executing BFS Algorithm

2. Depth-First Search (DFS)

LIFO (Last In, First Out) — STACK — Last in, First out.

Why can Depth-First Search potentially get stuck in infinite loops?

-> Because child states are generated continuously, increasing depth infinitely. Resolved by capping maximum search depth.

Executing DFS Algorithm

3. Iterative Deepening Search (IDS)

Like DFS but with depth limit boundaries.

Example:

1. Depth limit = 0

2. Depth limit = 1

3. Depth limit = 2

4. Hill-Climbing Search

Hill-climbing search is a specialized variant of depth-first search without backtracking. The next state is chosen using a Heuristic evaluation function.

Unlike depth-first search, hill climbing does not store all child nodes, saving only a single chosen state if available.

• Better state choice: Simple Hill Climbing
• Best state choice: Steepest-Ascent Hill Climbing

4.1 Simple Hill Climbing

Simple hill climbing selects the very first successor state found that evaluates better than the current state.

Steps of Simple Hill Climbing:

Step 1: If initial state (T0) is goal state: exit and report success.
Otherwise, set current state (Ti) to initial state (T0).

Step 2: Loop until goal state is reached or no valid next state (Tk) exists from current state:

a) Set Tk as a valid successor state of current state Ti.

b) Evaluate new state Tk:

• If it is goal state, return it and exit.
• If it is not goal state but evaluates better than current state, set it as current state.
• If it is not better than current state, continue loop iteration.

4.2 Steepest-Ascent Hill Climbing

Similar to simple hill climbing, except steepest-ascent hill climbing evaluates all valid outgoing branches and selects the single best state among available successors.

Sample Problem:

H(n) = |Goal x-coord – n x-coord| + |Goal y-coord – n y-coord|
n:=S
h(S)=|4-1|+|4-1|= 6 (min)
h(A)=|4-2|+|4-3|= 3 (min) < h(S)
NextS = A
n:=A
h(B)=|4-2|+|4-4|=2 (min) h(C)=|4-2|+|4-2|=4
h(B)<h(A)
NextA = B
n:=B
h(E)=|4-3|+|4-4|=1 (min) < h(B)
NextB = E
n:=E
h(G)=|4-4|+|4-4|=0 (min) h(H)=|4-3|+|4-3|=2
h(G)<h(E)
NextE = G (Goal - Stop)

5. GTS Algorithm (Greedy-Traveling Salesman)

5.1 GTS1

Find path with lowest cost traversing n vertices given a cost matrix starting from a specified vertex v.

Sample Problem:

5.2. GTS2

Similar to GTS1, but this algorithm evaluates paths starting from all vertices v, then selects the best overall path.

6. Graph Coloring Optimization Algorithm

Algorithm: Repeat the following steps until all vertices are colored:

Step 1: Choose uncolored vertex with highest degree and paint with color i.
Step 2: Degree reduction:
Colored vertex: degree = 0
Adjacent vertices: degree := degree – 1
Step 3: Mark adjacent vertices (whose degree was decremented) as forbidden from taking color i.

Example: Task assignment, work schedule, tournament scheduling:

A scientific conference has 9 different topic sessions, each taking 1 time slot.
The following topic pairs/sets cannot run concurrently: AE, BC, CD, ED, ABD, AHI, BHI, DFI, DHI, FGH.
Construct a schedule minimizing total required time slots. Hint: color count = required time slots.

=> Solution:
Conclusion:
Slot 1: G, D; Slot 2: C, E, H; Slot 3: A, F; Slot 4: B; Slot 5: I

7. AT Algorithm (Algorithm for Tree)

Steps of AT Algorithm:

Step 1:

• For all vertices n, all cost values g(n) are initially unknown.
• Open starting vertex, call it S. Set g(S) = 0.

Step 2: Choose open vertex with smallest corresponding cost g, call it N.

• If N is goal: path from initial node to N is shortest path with cost g(N). Stop (Success).
• If no open vertices remain: problem tree has no path to goal. Stop (Fail).
• If tie occurs (multiple vertices N share identical minimum g(N)): check if any of them is goal.
  If yes: path from initial node to node N is shortest with cost g(N). Stop (Success).
  If no: arbitrarily pick one of those vertices and call it N.

Step 3: Close vertex N and expand outgoing successor nodes from N. For every successor node S from N calculate:
g(S) = g(N) + cost(N->S)
Step 4: Return to Step 2.

8. AKT Algorithm – Search with Knowledge (Algorithm for Knowledgeable Tree Search)

Example:

Tower of Hanoi Problem with n = 2

Let n be total number of disks to move, m be number of disks correctly placed on 3rd peg, k be number of disks incorrectly placed on 3rd peg.

You must move misplaced disks out of peg 3 (k disks), then move incorrectly placed disks into correct position (n-m-k disks), and finally place k misplaced disks back.

Thus the formula is: h = k + (n-m-k) + k = n-m+k.

9. A* Search Algorithm – Pathfinding on General Graphs

Steps of A* Algorithm:
Step 1:
– Initial state: g, h, f values unknown for vertices.
– Open initial node S, set g(S) = 0
– Estimate heuristic h(S)
– Set f(S) = h(S) + g(S)
Step 2: Choose open vertex with smallest f(S), call it N.

• If N is goal: path from initial node to node N is shortest with cost g(N). Stop (Success).
• If no open nodes exist: graph has no valid path to goal. Stop (Fail).
• If tie occurs with multiple nodes sharing minimum f(S): check if any is goal node.

• If yes: path from initial node to N is shortest with cost g(N). Stop (Success).
• If no: pick one arbitrarily and call it N.

Step 3:
– Close node N, and for each successor node S from N calculate:
– g'(S) = g(N) + cost(S->N)
– If node S is already open and g(S) <= g'(S), ignore S
– Otherwise open S and set g(S) = g'(S), compute h(S) and f(S) = g(S) + h(S)
Step 4: Return to Step 2.

Download complete AI Midterm Study Guide: AI Midterm Review