Which Algorithm is Optimal and Complete? (DFS vs Hill Climbing vs A* vs Simulated Annealing)

To decide “which algorithm is optimal and complete,” we must distinguish two properties in state-space search:

• [keyword]{def="Complete": "A search is complete if it is guaranteed to find a solution whenever one exists."}
• [keyword]{def="Optimal": "A search is optimal if it returns the lowest-cost solution among all solutions."}
• [keyword]{def="Graph search": "Search that avoids revisiting already-expanded states using a closed set."}
• [keyword]{def="Tree search": "Search that does not avoid revisiting states; it may revisit infinitely."}
• [keyword]{def="Heuristic h(n)": "An estimate of the remaining cost from state n to a goal."}

In general, for cost-optimal pathfinding problems with nonnegative step costs, A* is the only one among the four that can be both complete and optimal under standard conditions on the heuristic, while DFS, hill climbing, and simulated annealing have limitations that prevent both guarantees simultaneously.

A concise rule of thumb:

• DFS: usually not optimal, and not complete in some common settings.
• Hill Climbing: typically neither complete nor optimal (it can get stuck in local optima).
• Simulated Annealing: can be asymptotically convergent under specific cooling schedules, but it does not provide the same kind of guaranteed optimality in finite time as A*.
• A*: can be complete and optimal when the heuristic is admissible (and often consistent) and the algorithm uses graph/tree-search assumptions consistent with the proof.

⚠️ Important: The exact guarantees depend on modeling choices (tree vs graph search), whether edge costs are nonnegative, and the heuristic/cooling schedule. For a rigorous course answer, always state the assumptions you’re using.

1) Depth First Search (DFS)

[keyword]{def="DFS": "A search strategy that expands the deepest available node first."} [keyword]{def="Depth bound": "A limit on how deep the search explores, often used to ensure termination."} [keyword]{def="Infinite path": "A path that never reaches a goal and can be extended indefinitely."} [keyword]{def="Worst-case behavior": "How an algorithm behaves under the least favorable scenario."}

• Optimality: DFS is not optimal in general because it commits to a depth-first traversal order that can reach a non-cheapest goal path first (especially under differing step costs).
• Completeness: Completeness depends on the search space and implementation:
  • In tree search without depth limits, DFS can get stuck exploring an infinite branch and never reach a goal that exists elsewhere.
  • Even in graph search with repeated-state detection, DFS still does not guarantee the best solution cost.

Net: Under standard formulations, DFS is not both complete and optimal.

2) Hill Climbing

[keyword]{def="Hill Climbing": "A local search method that repeatedly moves to a neighbor state with better evaluation."} [keyword]{def="Local optimum": "A state where no neighbor has a better evaluation, even if a global optimum exists."} [keyword]{def="Greedy ascent/descent": "A neighbor-choice rule that selects the best immediate improvement."} [keyword]{def="Plateau": "Region of equal evaluation where progress may stall."}

• Optimality: Not optimal in general; local improvement does not imply global best cost.
• Completeness: Not complete in general; it can stop at a local optimum/plateau without finding a goal (or without exploring alternative routes that would eventually lead to a solution).

Net: Hill climbing is neither complete nor optimal in general.

3) A* Search

[keyword]{def="A*": "Best-first search using f(n)=g(n)+h(n) to guide exploration toward optimal solutions."} [keyword]{def="f(n)": "Estimated total cost through node n: g(n)+h(n)."} [keyword]{def="g(n)": "Cost from start to node n along the discovered path."} [keyword]{def="Admissible heuristic": "h(n) never overestimates the true minimal cost to reach a goal."} [keyword]{def="Consistent heuristic": "Heuristic satisfying h(n) <= cost(n,n') + h(n') for all edges (monotonicity)."}

A* is the canonical “optimal pathfinding” algorithm for a wide class of problems:

• Completeness: Typically holds for finite graphs (or when using graph search with closed sets) under standard assumptions about step costs and state representation.
• Optimality: Holds when:
  • step costs are nonnegative, and
  • h(n) is admissible (and many treatments also assume consistency for simpler implementation/expanded-node handling).

Because A* explicitly uses cost estimates $f(n)=g(n)+h(n)$ with admissibility preventing over-optimism, it won’t “skip” a cheaper solution in a way that would violate optimality.

Net: A* is the correct answer for “optimal and complete” under standard conditions.

4) Simulated Annealing

[keyword]{def="Simulated Annealing": "A probabilistic local search that accepts worse moves with decreasing probability controlled by temperature."} [keyword]{def="Temperature schedule": "A function that controls exploration; lower temperature reduces random uphill moves over time."} [keyword]{def="Global optimum": "The best state according to the objective function across the entire search space."} [keyword]{def="Convergence": "Eventual approach toward an optimum, typically in probability over time."}

Simulated annealing is designed to overcome local optima by occasionally accepting worse moves. However:

• Optimality (in the strong, finite-time sense): Not generally guaranteed like A*.
• Completeness/termination: It is typically run for a number of iterations; with finite time, there is no deterministic guarantee of finding a goal.
• Theoretical convergence: Under certain mathematically specific cooling schedules and regularity assumptions, simulated annealing can be shown to converge (often described as convergence with probability 1 in the limit), but that is not the same as the textbook search guarantee of “returns the optimal solution whenever a solution exists.”

Net: SA may be eventually very good and can be theoretically analyzed, but it is not the standard “optimal and complete search algorithm” choice.

Bottom-Line Answer

Under standard AI search definitions for optimality and completeness in pathfinding:

• (i) Depth First Search → Not optimal, and not complete in general.
• (ii) Hill Climbing → Not optimal, and not complete in general.
• (iii) A* Search → Optimal and complete (under admissible/consistent heuristic + nonnegative costs + standard finite-state assumptions).
• (iv) Simulated Annealing → Generally not guaranteed optimal/complete in the classical sense; may converge under specific probabilistic schedules.

Visual decision summary