In maze search, the objective is to find a shortest path from the start to the goal. A* ranks candidate states using f(n) = g(n) + h(n): g(n) is the cost of reaching a state, and h(n) estimates the cost remaining. The next state explored is the one with the lowest f(n). This is a path-cost objective, not a measure of error between predicted and expected outputs. section 2.2
Scoring a maze location
If reaching a location took four steps and its estimated distance to the goal is five, its score is nine. A* uses that score to compare it with other locations waiting on the frontier. A heuristic that never overestimates the remaining cost preserves the optimal-path guarantee. section 2.2
class Node<T>: Comparable, Hashable {
let state: T
let parent: Node?
let cost: Float
let heuristic: Float
init(state: T, parent: Node?, cost: Float = 0.0, heuristic: Float = 0.0) {
self.state = state
self.parent = parent
self.cost = cost
self.heuristic = heuristic
}
var hashValue: Int { return Int(cost + heuristic) }
}
func < <T>(lhs: Node<T>, rhs: Node<T>) -> Bool {
return (lhs.cost + lhs.heuristic) < (rhs.cost + rhs.heuristic)
}
func == <T>(lhs: Node<T>, rhs: Node<T>) -> Bool {
return lhs === rhs
}
The Swift node stores cost and heuristic separately; its comparison adds them so a priority queue can favor the lower-scoring node. section 2.2
