The Gateway to Computer Science Excellence
+1 vote

A* algorithm is guaranteed to find an optimal solution if

  1. h’ is always 0
  2. g is always 1
  3. h’ never overestimates h
  4. h’ never underestimates h
in IS&Software Engineering by Veteran (105k points)
recategorized by | 1.1k views

1 Answer

0 votes

Answer : h’ never overestimates h

A*  is a computer algorithm that is widely used in path-finding and graph traversal.

DescriptionA* is an informed search algorithm, or a best-first search, meaning that it solves problems by searching among all possible paths to the solution (goal) for the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and among these paths it first considers the ones that appear to lead most quickly to the solution. It is formulated in terms of weighted graphs, starting from a specific node of a graph, it constructs a tree of paths starting from that node, expanding paths one step at a time, until one of its paths ends at the predetermined goal node.

Reference of Above Description is Wikipedia

Reference : Introduction to A*

by Boss (45.3k points)
Can you please explain what is h'?

I understand from wiki page that A* Algorithm minimizes the function

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

where n is the last node in the path

g(n) is length of path from start node to n

and h(n) is an estimate of cheapest path from n to goal

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,531 answers
101,350 users