CODEWITHSUNDEEP
algorithmsearchartificial-intelligence
Richard
Richard

Reputation: 7433

Which heuristic function is used in Best-First Search?

So the major difference between Best-First Search (informed) and Uniform-Cost Search (uninformed) is that in BFS, we use a heuristic function to determine which node to go next. In UCS, we always take the lowest cost that is calculated from my initial state.

What is the heuristic function used in Best-First Search? It is mentioned everywhere that the heuristic function is h(n) = f(n), but what's f(n) exactly and how do I get its value if my "map" has many nodes and only the cost of the paths from one node to another?

Upvotes: 0

Views: 704

Answers (1)

trincot
trincot

Reputation: 350167

A heuristic function is not a unique thing. It is a decision you make that heavily depends on the particular properties of the problem that is being solved. And even then you can choose between different approaches (functions). Often you'll try out how a chosen function influences the quality of the solutions found in sample cases, and test alternatives.

For example, if the graph is an Euclidean graph, where nodes represent coordinates in n-dimensional space, and the cost of an edge is its length (distance between connected nodes), then one possible heuristic could be the distance between source and target node.

The less you can assume about a graph -- the less you know about its properties --, the harder it will be to find a suitable heuristic function.

Upvotes: 3

Related Questions