A - algorithm — heuristic, admissibility, consistency — important for GNC

3.5.13 · Coding › Graphs

A* ka Dijkstra aur Greedy se kya relation hai? (80/20 core)

Algorithm	Priority key	Behaviour
Dijkstra	$f = g$	exact, slow, andha
Greedy best-first	$f = h$	fast, optimal nahi
A*	$f = g + h$	optimal (agar $h$ admissible ho) + fast

Figure — A - algorithm — heuristic, admissibility, consistency — important for GNC

DERIVATION 1 — Admissibility ⇒ optimal path kyun

Step 1. Maano $C^{*}$ true optimal cost hai. Maano A* ek goal node $G_{2}$ ko pop karne wala hai jiska path cost $g (G_{2}) > C^{*}$ hai (ek suboptimal goal). Hum dikhayenge yeh impossible hai. Yeh step kyun? Agar hum prove kar lein ki A* kabhi pehle bura goal pop nahi kar sakta, toh pehla popped goal optimal hi hoga.

Step 2. Kyunki true optimal path exist karta hai, open list (frontier) par kahin ek node $n$ hai jo ek optimal path par baith raha hai. Kyun? Start se goal tak koi bhi path joh poori tarah expand nahi hua, uska kam se kam ek "boundary" node frontier par zaroor hoga.

Step 3. Us $n$ ke liye: $f (n) = g (n) + h (n) \leq g (n) + h^{*} (n) = C^{*} .$ Yeh step kyun? $h (n) \leq h^{*} (n)$ hi admissibility hai, aur $n$ optimal path par hone ki wajah se $g (n) + h^{*} (n)$ optimal total cost $C^{*}$ ke barabar hai.

Step 4. Lekin $G_{2}$ goal hai isliye $h (G_{2}) = 0$ , ataḥ $f (G_{2}) = g (G_{2}) > C^{*}$ . Milaane par: $f (n) \leq C^{*} < f (G_{2})$ .

Step 5. A* sabse chhota $f$ pehle pop karta hai, isliye $n$ ko $G_{2}$ se pehle pop kiya jaata. Contradiction. ∎ Yeh kyun matter karta hai: A* jo pehla goal queue se nikalta hai wo guaranteed optimal hota hai — admissibility bilkul wohi condition hai jo yeh guarantee khareedti hai.

DERIVATION 2 — Consistency ⇒ admissibility (aur kabhi re-expand nahi) kyun

Step A: consistent ⇒ admissible. Koi bhi path lo $n = v_{0} \to v_{1} \to \dots \to v_{k} = goal$ . Consistency isko along apply karo: $h (v_{i}) \leq c (v_{i}, v_{i + 1}) + h (v_{i + 1}) .$ $i = 0$ se $k - 1$ tak sum karo ( $h$ terms telescope ho jaate hain), $h (v_{k}) = 0$ ke saath: $h (n) \leq \sum_{i = 0}^{k - 1} c (v_{i}, v_{i + 1}) = us path ki cost .$ Yeh step kyun? Yeh har path ke liye hold karta hai, khaaskar sabse saste ke liye, isliye $h (n) \leq h^{*} (n)$ . Ho gaya — consistency admissibility se zyada strong hai.

Step B: $f$ expansions ke along non-decreasing hai. Edge $u \to v$ ke liye: $f (v) = g (v) + h (v) = g (u) + c (u, v) + h (v) \geq g (u) + h (u) = f (u),$ consistency $c (u, v) + h (v) \geq h (u)$ use karte hue. Yeh kyun matter karta hai: $f$ kabhi decrease nahi karta jab hum deeper jaate hain. Isliye jab koi node pop hota hai uska $g$ already final hota hai → A ko koi closed node kabhi re-open nahi karna padta*. Sirf-admissible (par inconsistent) heuristic ke saath tumhe re-expand karna pad sakta hai, jo slower hai.

Worked Example 1 — grid with Manhattan distance

Grid, 4-directional moves cost 1 each. Heuristic $h =$ Manhattan distance $= ∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣$ .

Admissible kyun? Har move Manhattan distance ko zyada se zyada 1 badalta hai aur cost 1 hai, isliye seedha count kabhi true number of moves ko overestimate nahi karta.
Consistent kyun? Neighbours ke liye $c (u, v) = 1$ aur $∣ h (u) - h (v) ∣ \leq 1 = c (u, v)$ , isliye $h (u) \leq c (u, v) + h (v)$ . ✔

Start $(0, 0)$ , goal $(2, 2)$ :

$h (0, 0) = 4$ , $f = 0 + 4 = 4$ .
$(1, 0)$ ki taraf move karo: $g = 1$ , $h = 3$ , $f = 4$ . Same $f$ — A* goal ki taraf badhta rehta hai, $(- 1, 0)$ ko expand nahi karta jiska $f = 2 + 5 = 7$ hai. Yeh step kyun? Goal se door wale node ka $f$ zyada hai, isliye A* simply usse ignore karta hai — yahi Dijkstra se speedup hai.

Worked Example 2 — inadmissible heuristic optimality kaise todni hai

Nodes $S \to A \to G$ : $c (S, A) = 1, c (A, G) = 1$ (total 2). Aur $S \to G$ direct $= 2.5$ . Ek bura $h (A) = 5$ set karo (overestimate; true 1 hai).

$f (via A at A) = 1 + 5 = 6$ . $f (G direct, on open) = 2.5 + 0 = 2.5$ .
A* direct $G$ pehle pop karta hai → cost $2.5$ return karta hai, true optimum 2 miss karke. Yeh kyun matter karta hai: overestimate karne se achha path mahenga dikhne laga. Steel-man fix: $h$ ko clamp/lower karo taki $h \leq h^{*}$ ho.

Worked Example 3 — drone ke liye Euclidean heuristic (GNC)

Continuous space, moves along grid lekin real robot diagonally fly kar sakta hai; cost = Euclidean length. Use $h =$ straight-line (Euclidean) distance.

Seedhi line sabse chhota possible path hai ⇒ $h \leq h^{*}$ ⇒ admissible.
Yeh triangle inequality bhi satisfy karta hai ⇒ consistent. GNC kyun care karta hai: admissible Euclidean $h$ guarantee karta hai ki planner genuinely shortest flyable route return kare, aur target ki taraf ek narrow cone explore kare — on-board compute limited hone par yeh crucial hai.

Common mistake Classic errors ko steel-man karna

"Bada $h$ hamesha better hai, isliye speed ke liye $h$ bada banao." Kyun sahi lagta hai: bada heuristic search ko zyada aggressively focus karta hai, kam nodes expand → faster. Fix: haan, bada admissible $h$ (jo $h^{*}$ ke kareeb ho) better hai, lekin sirf jab tak $h \leq h^{*}$ ho. Us line ko cross karo aur optimality chali jaati hai (Example 2). Tum jaanbujhkar inadmissible ja sakte ho Weighted A* ke liye ( $f = g + w \cdot h, w > 1$ ) jab bounded-suboptimal paths speed ke liye acceptable hoin — lekin tab yeh optimal nahi rehta.

"Admissible matlab main kabhi kisi node ko re-expand nahi karta." Kyun sahi lagta hai: admissibility already optimality guarantee karti hai, poora lagta hai. Fix: re-expansion-free behaviour ke liye consistency chahiye, jo zyada strong property hai. Sirf admissible heuristics closed nodes ko reopen karne par majboor kar sakte hain.

"A with $h = 0$ toot gaya hai."* Fix: $h = 0$ admissible aur consistent hai — A* tab bilkul Dijkstra ban jaata hai. Toota nahi, bas unguided hai.

Recall Feynman: 12-saal ke bachche ko samjhao

Socho tum ek maze mein exit dhundh rahe ho. Dijkstra har direction mein equally explore karta hai — slow. A* smarter hai: har jagah par tum jhankke andaaza lagaate ho "yahan se exit roughly kitni door hai?" (jaise seedhi-line distance dekhna). Tum hamesha us jagah jaate ho jo sabse chhoti total trip deti lage = abhi tak chale steps plus andaaza. Ek rule: tera andaaza kabhi zyada promise mat kare — kabhi mat bolo "exit ekdum paas hai" jab wo ho nahi. Agar tera andaaza hamesha thoda cautious rahe (kabhi zyada rosy nahi), toh A* guaranteed sabse chhota raasta dhundh lega, sirf bahut jaldi.

Flashcards

A* mein f(n) kya hai?

f (n) = g (n) + h (n)

— cost-so-far plus estimated cost-to-go.

Admissible heuristic ki definition

0 \leq h (n) \leq h^{*} (n)

; kabhi true remaining cost ko overestimate nahi karta.

Consistent heuristic ki definition

h (u) \leq c (u, v) + h (v)

har edge ke liye,

h (goal) = 0

ke saath (triangle inequality).

Kya consistency admissibility imply karti hai?

Haan — kisi bhi path par consistency ko telescope karne se

h (n) \leq h^{*} (n)

milta hai. (One-way; admissible zarori nahi consistent ho.)

Kaunsi property guarantee karti hai ki A* optimal path return kare?

Admissibility.

Kaunsi property guarantee karti hai ki A* koi closed node kabhi re-expand na kare?

Consistency (yeh

f

ko kisi bhi path par non-decreasing banati hai).

h(n)=0 wala A* kya ban jaata hai?

Dijkstra's algorithm.

Sirf f=h use karna (g ignore karna) kya hai?

Greedy best-first search — fast lekin optimal nahi.

Overestimating heuristic optimality kyun todta hai?

Yeh true cheapest path ko mahenga dikhata hai, isliye A* pehle worse goal pop kar sakta hai.

Weighted A* kya hai?

f = g + w \cdot h

with

w > 1

: faster, bounded-suboptimal (≤ w × optimal), generally inadmissible.

Continuous space mein Euclidean distance admissible kyun hai?

Seedhi line sabse chhota possible path hai, isliye yeh kabhi overestimate nahi karta.

Connections

Dijkstra's Algorithm — A* with $h = 0$ .
Greedy Best-First Search — A* jab $g$ drop ho.
Heuristic Functions — Manhattan, Euclidean, Chebyshev.
Priority Queue / Min-Heap — data structure jo $f$ ke order mein arrange karta hai.
Triangle Inequality — consistency ki geometric jadd.
Weighted A* and Bounded Suboptimality
GNC Path Planning — rovers, drones, spacecraft.
Bellman Optimality — relation $g (v) = g (u) + c (u, v)$ .