Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/StackCompSci/status/776425609086046208
edited tags
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393
added 17 characters in body
Source Link
Carlos Linares López
Carlos Linares López
  • 3.5k
  • 16
  • 30

A heuristic function h$h (n)$ is...

  • ConsistentConsistent if the estimated cost from node n$n$ to the goal is no greater than the step cost to its successor n'$n'$ plus the estimated cost from the successor to the goal.
  • AdmissibleAdmissible if h$h(n)$ never overestimates the true cost to the goal state.

The textbook for my Artificial Intelligence course states that consistency is stronger than admissibility but does not prove it, and I'm having trouble coming up with a mathematical explanation.

A heuristic function h is...

  • Consistent if the estimated cost from node n to the goal is no greater than the step cost to its successor n' plus the estimated cost from the successor to the goal.
  • Admissible if h never overestimates the true cost to the goal state.

The textbook for my Artificial Intelligence course states that consistency is stronger than admissibility but does not prove it, and I'm having trouble coming up with a mathematical explanation.

A heuristic function $h (n)$ is...

  • Consistent if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the goal.
  • Admissible if $h(n)$ never overestimates the true cost to the goal state.

The textbook for my Artificial Intelligence course states that consistency is stronger than admissibility but does not prove it, and I'm having trouble coming up with a mathematical explanation.

Source Link
user58348
user58348
  • 161
  • 1
  • 1
  • 3

How does consistency imply that a heuristic is also admissible?

A heuristic function h is...

  • Consistent if the estimated cost from node n to the goal is no greater than the step cost to its successor n' plus the estimated cost from the successor to the goal.
  • Admissible if h never overestimates the true cost to the goal state.

The textbook for my Artificial Intelligence course states that consistency is stronger than admissibility but does not prove it, and I'm having trouble coming up with a mathematical explanation.