--- title: "Greedy best-first drawbacks; A*" subject: "Artificial Intelligence" chapter: 3 key: "semester_6/artificial_intelligence:greedy-best-first-vs-astar" source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/greedy-best-first-vs-astar site: BCT Engineering --- # Greedy best-first drawbacks; A* Artificial Intelligence · Chapter 3: Search Techniques - Asked in: 2074 Bhadra, 2+7 marks - Video: [VTU | 5th Sem | AI Module 3 | Greedy Best First Search & A* Search | Solved Graph Problem | BCS515B](https://www.youtube.com/watch?v=-58hNVO3mps) — Express VTU 4 All - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/greedy-best-first-vs-astar - Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-3 ## Question Why is searching important in problem solving? What are the drawbacks of greedy best-first search and how does the A* search algorithm solve them? Explain with an example. ## Short answer Greedy best-first expands the node with smallest h(n) but ignores g(n), so it is not optimal or complete. A* uses f(n) = g(n) + h(n); in the example greedy gives S-A-C-G costing 12, while A* returns S-B-G costing 9. ## Answer #### Importance of searching Most problems (route finding, puzzles, planning, games) are represented as a state space where no direct formula gives the answer. Search systematically explores the possible action sequences to find a path from the initial state to the goal, and finds the best one when many exist. #### Greedy best-first search It expands the node that appears closest to the goal, using only the heuristic: **f(n) = h(n)**. **Drawbacks** 1. **Not optimal:** it ignores the cost already spent, g(n), so it may return a long path. 2. **Not complete:** it can follow a misleading heuristic into a loop or dead end (unless repeated states are checked). 3. **Worst-case time and space O(b^m)**; it may expand many nodes if the heuristic is poor. 4. Being greedy at every step, it can be fooled by local minima in h. #### A\* search A* uses **f(n) = g(n) + h(n)**, where g(n) = cost from the start to n and h(n) = estimated cost from n to the goal. With an **admissible** heuristic (one that never overestimates), A* is **complete and optimal**. Because g(n) is included, a path that has become expensive is abandoned, while the heuristic still guides the search towards the goal. #### Example Edges: S-A = 2, S-B = 5, A-C = 9, C-G = 1, B-G = 4. Heuristic: h(S) = 6, h(A) = 1, h(B) = 3, h(C) = 1, h(G) = 0 (admissible). ```text S 2 / \ 5 A B 9 | | 4 C | 1 | | G---+ ``` **Greedy:** from S, compare h(A) = 1 and h(B) = 3 and choose A; then C (h = 1); then G. Path **S-A-C-G, cost 2 + 9 + 1 = 12**. **A\*:** | Step | Expand | f values generated | |---|---|---| | 1 | S | A: 2+1 = 3; B: 5+3 = 8 | | 2 | A (f=3) | C: (2+9) + 1 = 12 | | 3 | B (f=8) | G: (5+4) + 0 = 9 | | 4 | G (f=9, lowest) | Goal | A* returns **S-B-G, cost 9**, which is better than the greedy path (12). A* did not follow the attractive h(A) = 1, because it counted the high cost 9 of the edge A-C in g. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does greedy best-first search use to choose a node? A. f(n) = g(n) + h(n) B. f(n) = h(n) only C. f(n) = g(n) only D. A random choice Answer: B. Greedy best-first expands the node that seems closest to the goal using only the heuristic. (Key point: Greedy evaluation) 2. Why is greedy best-first search not optimal? A. It ignores the cost already spent g(n) B. It uses too little memory C. It uses a stack D. It always expands the root last Answer: A. Because it ignores g(n), it may return a long, costly path. (Key point: Greedy drawback) 3. How does A* overcome greedy's weakness? A. By dropping the heuristic B. By adding the path cost g(n), so expensive paths are abandoned while h still guides to the goal C. By expanding nodes randomly D. By using a larger queue Answer: B. f = g + h accounts for cost already travelled and the estimated remainder. (Key point: How A* fixes it) 4. In the example, what do greedy and A* return? A. Greedy S-A-C-G (12); A* S-B-G (9) B. Greedy S-B-G (9); A* S-A-C-G (12) C. Both S-A-C-G (12) D. Both S-B-G (9) Answer: A. Greedy follows the small h(A) = 1 into a costly edge, but A* counts A-C = 9 and finds S-B-G with cost 9. (Key point: Example result) ## Related in Artificial Intelligence - [Well defined problem, state-space search](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Awell-defined-problem-state-space) — Artificial Intelligence, chapter 2 - [Searching: BFS vs DFS comparison](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ablind-search-dfs-bfs-compare) — Artificial Intelligence, chapter 3, asked 5× - [Informed vs blind search; DFS vs BFS](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ainformed-vs-blind-search-dfs-bfs) — Artificial Intelligence, chapter 3 - [Problem space; BASE+BALL=GAMES](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aproblem-space-base-ball-games) — Artificial Intelligence, chapter 2 ## Related in other subjects - [Three students solving a problem](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Athree-students-solve-problem) — Probability and Statistics, chapter 1 - [ID3 algorithm and why greedy](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-greedy) — Data Mining, chapter 3 - [Creative problem solving and brainstorming](https://www.bctengineer.com/question.md?key=semester_6%2Fmachine_design_i%3Acreative-problem-solving-brainstorming) — Machine Design I, chapter 4 - [Binary search with algorithm and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-algorithm-example) — Data Structure and Algorithm, chapter 8, asked 4×