技术问询：8向移动代价相同时15 puzzle的Euclidean distance是否可采纳？

Alright, let's break this down step by step to answer your question clearly.

First, let's recap the core definition of an admissible heuristic: a heuristic function is admissible if it never overestimates the minimum cost to reach the goal state from any given current state. In other words, for any state n, h(n) ≤ h*(n), where h*(n) is the actual minimum cost to get from n to the goal.

Context for 8-way moves in the 15-puzzle #

In this scenario, each tile can move to any of the 8 adjacent squares (horizontal, vertical, diagonal), and every move has the same cost (we'll assume cost = 1 for simplicity).

For a single tile, let's say its current position is (x1, y1) and its target position is (x2, y2). Let dx = |x1 - x2| and dy = |y1 - y2| be the horizontal and vertical distances to the target. With 8-way moves, the minimum number of steps (cost) to move this tile to its target is max(dx, dy):

• You can take min(dx, dy) diagonal steps (each step reduces both dx and dy by 1), then |dx - dy| straight steps (horizontal or vertical) to cover the remaining distance. Total steps = min(dx, dy) + |dx - dy| = max(dx, dy).

Comparing Euclidean distance to the actual minimum cost #

The Euclidean distance for this tile is sqrt(dx² + dy²). Now we need to check if this value is always ≤ max(dx, dy) (the actual minimum cost):

• Let's assume dx ≥ dy (the logic is symmetric if dy ≥ dx). Then max(dx, dy) = dx.
• sqrt(dx² + dy²) = dx * sqrt(1 + (dy/dx)²). Since dy/dx ≥ 0, sqrt(1 + (dy/dx)²) ≥ 1.
• When dy > 0, this value is greater than dx (e.g., if dx=1, dy=1, Euclidean distance is sqrt(2) ≈ 1.414, which is greater than max(1,1)=1).
• Only when dy=0 (or dx=0) does the Euclidean distance equal the minimum cost.

What this means for admissibility #

Since the Euclidean distance often overestimates the actual minimum cost for individual tiles (and thus the total minimum cost for the entire puzzle state), it violates the requirement for admissibility. Even for simple cases—like a tile one diagonal step away from its target—the Euclidean distance gives a higher value than the actual minimum cost of 1.

Conclusion #

Euclidean distance is not admissible for the 15-puzzle with 8-way moves, as it regularly overestimates the minimum number of moves required to reach the goal state.

内容的提问来源于stack exchange，提问作者Torjus Halden