| 八数码问题中的逆序数 | 您所在的位置：网站首页 › 逆序数的三个性质是什么意思 › 八数码问题中的逆序数 |
|
转载自：http://blog.csdn.net/ju136/article/details/6876647（选取部分）。 对于给定八数码棋局的初始状态，我们的目标是通过交换空格与其相邻棋子使棋盘达到目标状态。 其中，游戏规则是只能交换空格与其上下左右四个方向的相邻棋子。 假设棋局目标状态为如下形式：（A、B、C、D、E、F、G、H表示棋子） A B C D E F G H 而初始状态就是A、B、C、D、E、F、G、H这八个棋子在这九个棋格上的任意分布。 并且我们对棋盘中每个棋格进行如下形式的编号： 1 2 3 4 5 6 7 8 9 那么，对于一个任意的棋局状态，我们可以取得这八个棋子（A、B、C、D、E、F、G、H）的一个数列：棋子按照棋格的编号依次进行排列，记为p=c[1]c[2]c[3]c[4]c[5]c[6]c[7]c[8]（即A、B、C、D、E、F、G、H的一个排列）。 在分析之前，先引进逆序和逆序数的概念：对于棋子数列中任何一个棋子c[i]（1≤i≤8），如果有j>i且c[j] |
| CopyRight 2018-2019 实验室设备网 版权所有 |