Unit 2: Heuristic search and NLP
Artificial Intelligence & Soft Computing notes · PTU syllabus (PGCA1926)
On this page
Unit summary
Heuristics guide search towards good solutions quickly, and NLP lets computers process language. This unit covers hill climbing, simulated annealing, greedy best-first search, A* and optimal search, memory-bounded heuristic search, and NLP grammars, parsing, semantic analysis and pragmatics.
After this unit you can
- Apply local search: hill climbing and simulated annealing
- Apply greedy best-first and A* search
- Explain memory-bounded heuristic search
- Explain grammars, parsing, semantics and pragmatics in NLP
PTU syllabus topics
- Hill climbing
- simulated annealing
- greedy best-first search
- A* and optimal search
- memory-bounded heuristic search
- NLP grammars
- parsing
- semantic analysis and pragmatics
Hill climbing
Yes
No: can get stuck at local maxima
Simulated annealing
Yes
Can escape local maxima
Greedy best-first
Yes: h(n)
No
A*
Yes: f(n) = g(n) + h(n)
Yes, if h is admissible
Topic 1
Hill climbing
- Hill climbing keeps one current state and moves to the best neighbour while it improves the objective — like climbing a hill in fog.
- Local maximum
- Peak lower than the global maximum — use random restarts
- Plateau
- Flat area with no uphill move — allow sideways moves
- Ridge
- Sequence of local maxima hard to climb — use different move sets
- Variants
- Steepest ascent, stochastic, first-choice, random-restart
Example
8-Queens with h = number of attacking pairs: each move relocates one queen in its column to reduce h; steepest-ascent hill climbing solves about 14% of random starts but random restarts almost always succeed.
Topic 2
Simulated annealing
- 1Start at a random state with high temperature T
- 2Pick a random neighbour
- 3If better, move; if worse, move with probability e^(ΔE ÷ T)
- 4Lower T according to a cooling schedule
- 5Stop when T is near zero
- Early on, bad moves are often accepted, escaping local maxima; as T falls, the search becomes greedy. With slow enough cooling it finds a global optimum with high probability — used in VLSI layout and scheduling.
Topic 3
Greedy best-first search and A*
A heuristic h(n) estimates the cost from node n to the goal.
- Greedy best-first search expands the node with the smallest h(n) — fast but not optimal.
- *A search expands the node with the smallest f(n) = g(n) + h(n)*, where g(n) is the cost so far. A is optimal if h is admissible (never overestimates).
- *AO search works on AND-OR graphs**, where solving a node may require solving all of several subproblems (AND) or any one of them (OR).
Example
In route finding, h(n) = straight-line distance to the destination is admissible because the road distance is never shorter.
Topic 4
A* and optimal search
- Admissible heuristic: never overestimates the true cost — A* tree search is then optimal. Consistent (monotone) heuristic: h(n) ≤ c(n, n′) + h(n′) — A* graph search is then optimal and f never decreases along a path.
h1: misplaced tiles
Number of tiles not in their goal position
Admissible but weaker
h2: Manhattan distance
Sum of horizontal and vertical distances of tiles from their goals
Admissible and dominates h1, so A* expands fewer nodes
Example
Start state 7 2 4 / 5 _ 6 / 8 3 1 (goal _ 1 2 / 3 4 5 / 6 7 8): h1 = 8, h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18; the optimal solution has 26 moves.
Topic 5
Memory-bounded heuristic search
IDA* (iterative deepening A*)
Depth-first search with an f-cost limit raised each iteration
Linear memory; re-expands nodes
RBFS (recursive best-first search)
Best-first with linear space, backing up the best alternative f-value
Linear memory; may regenerate nodes often
SMA* (simplified memory-bounded A*)
A* until memory is full, then drops the worst leaf and remembers its value in the parent
Uses all available memory; optimal if the solution fits
Topic 6
Natural language processing: grammars
- NLP enables computers to understand and generate human language: phases are lexical (tokens, morphology), syntactic (grammar and parsing), semantic (meaning) and pragmatic (context) analysis.
- Context-free grammar (CFG)
- Rules such as S → NP VP, NP → Det N, VP → V NP
- Lexicon
- Words with categories — the (Det), student (N), reads (V)
- Probabilistic CFG
- Rules with probabilities to choose likely parses
- Augmented grammars
- Add features for agreement, tense
- Dependency grammar
- Words linked by head–dependent relations
Topic 7
Parsing
Top-down parsing
Start from S and expand rules to match the words
Recursive descent
Bottom-up parsing
Combine words into constituents up to S
Shift–reduce
Chart parsing
Store partial results to avoid repeated work
CYK, Earley
Statistical and neural parsing
Learn parsers from treebanks
Dependency parsers in spaCy
Example
"The student reads a book": S → NP (Det the, N student) VP (V reads, NP (Det a, N book)).
Topic 8
Semantic analysis and pragmatics
- Semantic analysis maps parsed sentences to meaning — logical forms (Reads(student1, book1)), word senses ("bank" as river side or financial institution) and semantic roles (agent, object).
- Pragmatics and discourse use context: resolving pronouns ("Riya met Asha; she smiled"), speech acts ("Can you pass the salt?" is a request), and world knowledge.
- Today: neural language models and transformers learn many of these levels from large text corpora.
Key terms
- Hill climbing
- Local search moving to the best neighbour
- Simulated annealing
- Local search accepting worse moves with decreasing probability
- Admissible heuristic
- Heuristic that never overestimates
- IDA*
- Iterative deepening with an f-cost threshold
- Parsing
- Assigning syntactic structure to a sentence
Quick revision
- Hill climbing problems: local maxima, plateaus, ridges; random restarts.
- Simulated annealing acceptance probability and cooling.
- Greedy best-first: h(n); A*: f = g + h; admissible and consistent heuristics; h1 and h2 for the 8-puzzle.
- IDA, RBFS, SMA.
- NLP phases; CFG; top-down, bottom-up, chart parsing; semantics; pragmatics.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.What is a plateau in hill climbing?
- Q2.Why does simulated annealing accept worse moves?
- Q3.When is A* optimal?
- Q4.Compute h1 for an 8-puzzle state.
- Q5.What is SMA*?
- Q6.Distinguish semantic and pragmatic analysis.
Long-answer questions
- Q1.Explain hill climbing and simulated annealing.
- Q2.Explain A* search with an example and the properties of heuristics.
- Q3.Explain memory-bounded heuristic search.
- Q4.Explain grammars, parsing, semantic analysis and pragmatics in NLP.
Stuck on this unit?
Message SBS on WhatsApp for help with Artificial Intelligence & Soft Computing, or to ask about studying M.Sc IT at Synetic.