arrays - A* 可接受的数组排序启发式算法

Question

我正在尝试为这样的问题解决 A* 可接受的启发式方法-

I have a array of numbers.

I am only allowed to swap two adjacent numbers.

I need to solve it minimum no of swaps.

谁能帮我找到一个可接受的启发式来解决这个问题？

在此先感谢您的帮助。

Answer 1

解决这个问题的一个很好的启发式方法是计算数组中的反转次数。

反转是一对索引 i,j，其中 i < j 使得 A[i] > A[j](即该对的顺序不正确)。

有一种 O(nlogn) 方法可以通过合并排序计算倒置次数(有关某些方法的说明，请参阅 here)。

这是一个很好的启发式方法，因为反转次数给出了到目标的精确距离。总会有一个可能的移动将反转次数减少 1。进行这样的移动将以最少的步骤对数组进行排序。