循序渐进解决八数码问题

数据结构与算法
11k 词

八数码问题

题目描述

在 3 x 3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格，空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

样例

样例输入

283104765

样例输出

4

提示

样例解释

图中标有 0 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

BFS+康托判重

首先介绍一个东西，叫做康托展开。

来自wikipedia：康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

https://zh.wikipedia.org/wiki/康托展开

公式

image-20240718152917112

其中,image-20240718153033860为整数,并且image-20240718152945202image-20240718153104663的意义参见举例中的解释部分。

举例

例如，3 5 7 4 1 2 9 6 8 展开为 98884 。因为X=2x8!+3x7!+4x6!+2x5!+0x4!+0x3!+2x2!+0x1!+0*0! = 98884.

解释：

排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为2*8!

排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为3*7!

以此类推，直至0*0!

思路

最近抽空学了一下kotlin语言，所以这道题就拿kotlin写了，首先我们创建一个一维数组来表示这个3x3的棋盘，这里我就用9这个数字表示空格了。

fun main{
    val list = mutableListOf(1, 2, 3, 4, 5, 6, 7, 8, 9)
}

当目标状态为123456789时，当前状态的逆序对数必须为偶数才能有解，故打乱这个数组时，要一直判断逆序对数是否为偶数，不是则重新打乱，kotlin中有现成的打乱函数，直接调用即可。

fun main() {
    val list = mutableListOf(1, 2, 3, 4, 5, 6, 7, 8, 9)
    do {
        list.shuffle()
    } while (getInvCnt(list) % 2 != 0)
}
fun getInvCnt(list: List<Int>): Int {
    var count = 0
    for (i in list.indices) {
        for (j in i + 1 ..< list.size) {
            // 注意空格这里我们不计入计算中
            if (list[i] != 9 && list[j] != 9 && list[i] > list[j]) count++
        }
    }
    return count
}

然后我们需要根据康托展开来判重，一共九个数，那么就有9!种全排列，而9! = 362,880，那么我们创建一个Boolean类型数组vis

val vis = BooleanArray(362880)

然后我们编写函数k，用来计算康托展开，也就是传入一个排列，得到这个排列唯一对应的顺序，f的作用是求n!，其实可以直接打表，因为只会用到1-9的阶乘，但是我懒就没写了（

private fun k(list: List<Int>): Int {
    val n = list.joinToString("") { it.toString() }.toInt()
    return k(n)
}

private fun k(n: Int): Int {
    val digits = n.toString().map { it - '0' }
    var rank = 0
    for (i in digits.indices) {
        val cnt = digits.drop(i + 1).count { it < digits[i] }
        rank += cnt * f(digits.size - i - 1)
    }
    return rank
}

private fun f(n: Int): Int {
    if (n == 0 || n == 1) return 1
    return n * f(n - 1)
}

因为我们需要进行BFS搜索，那么队列中肯定要存放多种状态，那么我们直接定义一个状态类Node：

data class Node(
    val list: List<Int>,//当前状态，例如:1 7 6 9 5 3 2 8 4
    val i: Int,//当前空格的位置
    val step: Int = 0,//当前是第几步
    val path: MutableList<IntArray> = mutableListOf<IntArray>()//保存之前的走的路径，可有可无，这里我写只是想看走的路径是什么样的方便调试
)

然后创建队列并加入头节点：

val q = java.util.ArrayDeque<Node>()
q.add(Node(list, list.indexOf(9), 0, mutableListOf<IntArray>(list.toIntArray())))

然后下面就是标准BFS板子：

队列不为空就取出节点，然后根据获取这个节点的康托展开，如果没有标记过，那么标记上，如果标记过，那么就跳过，定义dx和dy偏移量，进行将空格上下左右移动并交换，

计算新的x=idx/3 + dx和y=idx%3+dy一维转到二维的坐标，那么再通过x*3+y就能得到新的在一维中空格移动到的索引位置，kotlin有一点比较好的就是判断是否越界很简单，它可以直接写一个区间x in 0..2代表0<=x<=2，这里获取到了下一步走的索引，就可以进行交换了，kotlin在交换元素时可以用一个骚操作就是用also方法:

nextList[curIdx] = nextList[nextIdx].also { nextList[nextIdx] = nextList[curIdx] }

also函数是在一个对象上执行某些操作并返回该对象本身。这使得它非常适合于链式调用或在不影响原对象的情况下进行操作。

  • nextList[nextIdx]：获取nextIdx索引位置的元素。

  • also { nextList[nextIdx] = nextList[curIdx] }：

    • also接收一个函数块，在该块中，我们将nextIdx索引位置的元素赋值为curIdx索引位置的元素。
    • also的返回值是它调用者，也就是nextList[nextIdx]的原始值。

  • nextList[curIdx] = nextList[nextIdx].also { ... }：最终，nextList[curIdx]被赋值为also的返回值，也就是nextList[nextIdx]的原始值。

根据获得的新的状态，构造下一步的状态并放入队列中，直到当前的状态是目标状态，得以将问题解决。

private fun main() {
    val list = mutableListOf(1, 2, 3, 4, 5, 6, 7, 8, 9)
    do {
        list.shuffle()
    } while (getInvCnt(list) % 2 != 0)
//    val list = readln().toCharArray().map { if (it != '0') it - '0' else 9 }

    val vis = BooleanArray(362880)
    val q = java.util.ArrayDeque<Node>()
    q.add(Node(list, list.indexOf(9), 0, mutableListOf<IntArray>(list.toIntArray())))
    while (!q.isEmpty()) {
        val curNode = q.poll()
        val curNum = curNode.list.joinToString("") { it.toString() }.toInt()
        val curIdx = curNode.i
        val curK = k(curNode.list)
        val curPath = curNode.path
//        if (curNum == 123894765) {
        if (curNum == 123456789) {
            println("找到了")
            for ((i, path) in curPath.withIndex()) {
                println("第${i}步：")
                printPintu(path.toList())
                println()
            }
            println(curNode.step)
            break
        }
        if (vis[curK]) continue
        vis[curK] = true
        val dx = intArrayOf(0, 0, -1, 1)
        val dy = intArrayOf(-1, 1, 0, 0)
        for (i in 0 until 4) {
            val x = curIdx / 3 + dx[i]
            val y = curIdx % 3 + dy[i]
            if (x in 0..2 && y in 0..2) {
                val nextIdx = x * 3 + y
                val nextList = curNode.list.toMutableList()
                nextList[curIdx] = nextList[nextIdx].also { nextList[nextIdx] = nextList[curIdx] }
                val nextK = k(nextList)
                val nextPath = curNode.path.toMutableList()
                nextPath.add(nextList.toIntArray())
                val node = Node(nextList, nextIdx, curNode.step + 1, nextPath)
                q.add(node)
            }
        }
    }
}

data class Node(
    val list: List<Int>,
    val i: Int,
    val step: Int = 0,
    val path: MutableList<IntArray> = mutableListOf<IntArray>()
)

private fun getInvCnt(list: List<Int>): Int {
    var count = 0
    for (i in list.indices) {
        for (j in i + 1 until list.size) {
            if (list[i] != 9 && list[j] != 9 && list[i] > list[j]) count++
        }
    }
    return count
}

private fun printPintu(list: List<Int>) {
    for (i in list.indices) {
        val x = list[i]
        if (x == 9) print("  ") else print("$x ")
        if (i % 3 == 2) println()
    }
}

private fun k(list: List<Int>): Int {
    val n = list.joinToString("") { it.toString() }.toInt()
    return k(n)
}

private fun k(n: Int): Int {
    val digits = n.toString().map { it - '0' }
    var rank = 0
    for (i in digits.indices) {
        val cnt = digits.drop(i + 1).count { it < digits[i] }
        rank += cnt * f(digits.size - i - 1)
    }
    return rank
}

private fun f(n: Int): Int {
    if (n == 0 || n == 1) return 1
    return n * f(n - 1)
}

当然只是这样的话，还是不够的，由于状态过于多，我们搜索的而又太广泛，很容易将队列内存干爆，那么我们就可以尝试以下启发式搜索。

image-20240718160347318

A*算法(启发式搜索)

介绍算法

启发式搜索（英文：heuristic search）是一种在普通搜索算法的基础上引入了启发式函数的搜索算法。

启发式函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。

启发式搜索最核心的就是找到启发式函数，也叫估价函数，其一般形式为

img

式中：g(x)为从初始节点到节点x付出的实际代价；h(x)为从节点x到目标节点的最优路径的估计代价。启发性信息主要体现在h(x)中，其形式要根据问题的特性来确定。

虽然启发式搜索有望能够很快到达目标节点，但需要花费一些时间来对新生节点进行评价。因此，在启发式搜索中，估计函数的定义是十分重要的。如定义不当，则上述搜索算法不一定能找到问题的解，即使找到解，也不一定是最优的。

定义启发式函数

那么我们就定义g(x)估计代价为当前走的步数，步数越少的，肯定到目标节点的步数会越少，定义h(x)为所有点到目标点的曼哈顿距离和，那么我们用优先队列，优先处理f(x)小的节点，也就是到达目标状态走的步数最小的节点。

平面上的曼哈顿距离：例如坐标（x1, y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为

image-20240718164040107

曼哈顿距离估价

fun h(list: List<Int>): Int {
    var dist = 0
    for (i in list.indices) {
        // 不计入空格
        if (list[i] != 9) {
            val tx = (list[i] - 1) / 3
            val ty = (list[i] - 1) % 3
            val x = i / 3
            val y = i % 3
            dist += abs(x - tx) + abs(y - ty)
        }
    }
    return dist
}

因为定义了估价函数，那么我们用来保存状态的类就需要修改一下了：

data class Node(
    val list: List<Int>,
    val i: Int,
    val step: Int,
    val h: Int,
    val g: Int = step
)

然后我们还是基于之前的算法通过康托判重，BFS搜索，只不过加上了优先级，将估价最小的放在前面，先拿出来进行搜索。

实现代码

import java.util.PriorityQueue
import kotlin.math.abs

private fun main() {
    /*val list = mutableListOf(1, 2, 3, 4, 9, 5, 6, 7, 8)
    do {
        list.shuffle()
    } while (getInvCnt(list) % 2 != 0)*/

    val list = readln().toCharArray().map { if (it != '0') it - '0' else 9 }
    val vis = BooleanArray(362880)
    val open = PriorityQueue(compareBy<Node> { it.g + it.h })
    val close = HashSet<Node>()
    val head = Node(list, list.indexOf(9), 0, h(list))
    open.add(head)
    var ans = -1
    while (open.isNotEmpty()) {
        val curNode = open.poll()
        val curNum = curNode.list.joinToString("") { it.toString() }.toInt()
        val curIdx = curNode.i
        val curK = k(curNode.list)
        if (curNum == 123894765) {
            ans = curNode.step
            break
        }
        if (curNode in close) continue
        close.add(curNode)
        if (vis[curK]) continue
        vis[curK] = true

        val dx = intArrayOf(0, 0, -1, 1)
        val dy = intArrayOf(-1, 1, 0, 0)
        for (i in 0 until 4) {
            val x = curIdx / 3 + dx[i]
            val y = curIdx % 3 + dy[i]
            if (x in 0..2 && y in 0..2) {
                val nextIdx = x * 3 + y
                val nextList = curNode.list.toMutableList()
                nextList[curIdx] = nextList[nextIdx].also { nextList[nextIdx] = nextList[curIdx] }
                val nextK = k(nextList)
                val nextNode = Node(nextList, nextIdx, curNode.step + 1, h(nextList))
                open.add(nextNode)
            }
        }
    }
    println(ans)
}

internal data class Node(
    val list: List<Int>,
    val i: Int,
    val step: Int,
    val h: Int,
    val g: Int = step
)

private fun getInvCnt(list: List<Int>): Int {
    var count = 0
    for (i in list.indices) {
        for (j in i + 1 until list.size) {
            if (list[i] != 9 && list[j] != 9 && list[i] > list[j]) count++
        }
    }
    return count
}

private fun h(list: List<Int>): Int {
    var dist = 0
    for (i in list.indices) {
        if (list[i] != 9) {
            val tx = (list[i] - 1) / 3
            val ty = (list[i] - 1) % 3
            val x = i / 3
            val y = i % 3
            dist += abs(x - tx) + abs(y - ty)
        }
    }
    return dist
}

private fun k(list: List<Int>): Int {
    val n = list.joinToString("") { it.toString() }.toInt()
    return k(n)
}

private fun k(n: Int): Int {
    val digits = n.toString().map { it - '0' }
    var rank = 0
    for (i in digits.indices) {
        val cnt = digits.drop(i + 1).count { it < digits[i] }
        rank += cnt * f(digits.size - i - 1)
    }
    return rank
}

private fun f(n: Int): Int {
    if (n == 0 || n == 1) return 1
    return n * f(n - 1)
}

image-20240718165615824

我们发现确实优化了不少了，比上次多拿了33分，如何进一步优化呢，考虑使用IDA*算法。

IDA*算法（迭代加深的深度优先搜索）

简要介绍算法

IDA*算法采用了迭代加深算法的 A* 算法。

这种算法有利有弊：

  • 优点：
    1. 不需要判重，不需要排序，利于深度剪枝。
    2. 空间需求减少：每个深度下实际上是一个深度优先搜索，不过深度有限制，使用 DFS 可以减小空间消耗。
  • 缺点：
    1. 导致重复搜索，即使前后两次搜索相差微小，回溯过程中每次深度变大都要再次从头搜索。

思路

这里因为代码几乎重写了，所以我就不小心用0代表空格了，但是之前的不知道为什么改成0跑不出来（

创建一个Node对象head来表示拼图的初始状态，Node包括拼图的数字列表、空格（0）的索引、到达该状态的步数（0）和启发值 h。

主函数

val head = Node(list, list.indexOf(0), 0, h(list, target))

并且初始化ans和迭代深度deep，不断迭代进行深度优先搜索，并且不断加深搜索深度，

var ans = -1
var deep = head.h // 初始深度就直接设为初始曼哈顿距离即可

然后下面是迭代的代码：

 while (true) {
     val t = dfs(head, 0, deep, target)
     if (t == -1) {
         ans = deep
         break
     }
     if (t == Int.MAX_VALUE) break
     deep = t
 }
println(ans)

当dfs函数找到答案的时候会返回-1，这是我规定好的，找到那么就直接返回答案为deep即可

如果在当前deep深度内没有找到解决方案但仍有节点可以探索，则更新deep为超过当前deep的最小代价，并继续循环。

DFS函数

fun dfs(node: Node, g: Int, deep: Int, target: List<Int>): Int {
    val f = g + node.h
    if (f > deep) return f
    if (node.list == target) return -1

    var min = Int.MAX_VALUE
    val dx = intArrayOf(0, 0, -1, 1)
    val dy = intArrayOf(-1, 1, 0, 0)
    for (i in 0 until 4) {
        val x = node.i / 3 + dx[i]
        val y = node.i % 3 + dy[i]
        if (x in 0..2 && y in 0..2) {
            val nextIdx = x * 3 + y
            val nextList = node.list.toMutableList()
            nextList[node.i] = nextList[nextIdx].also { nextList[nextIdx] = nextList[node.i] }
            val nextNode = Node(nextList, nextIdx, node.step + 1, h(nextList, target))
            val t = dfs(nextNode, g + 1, deep, target)
            if (t == -1) return -1
            if (t < min) min = t
        }
    }
    return min
}

f是实际代价g(步数)和启发值h(曼哈顿距离) 的和。

  • 如果f超过了当前限制的深度，那么直接返回当前的f

  • 如果找到了答案，就返回-1

  • 否则进行对上下左右四个方向继续更深层的搜索

    • 当下一层返回的值为-1时，我们找到了答案，同样直接返回-1
    • 如果不为-1那么我们就记录每次返回的值的最小值，用于下一次迭代递归时限制其深度

完整代码

import kotlin.math.abs

private fun main() {
    val list = readln().toCharArray().map { it - '0' }
    val target = listOf(1, 2, 3, 8, 0, 4, 7, 6, 5)
    val head = Node(list, list.indexOf(0), 0, h(list, target))

    var ans = -1
    var deep = head.h
    while (true) {
        val t = dfs(head, 0, deep, target)
        if (t == -1) {
            ans = deep
            break
        }
        if (t == Int.MAX_VALUE) break
        deep = t
    }
    println(ans)
}

private data class Node(
    val list: List<Int>,
    val i: Int,
    val step: Int,
    val h: Int,
    val g: Int = step
)

private fun dfs(node: Node, g: Int, deep: Int, target: List<Int>): Int {
    val f = g + node.h
    if (f > deep) return f
    if (node.list == target) return -1

    var min = Int.MAX_VALUE
    val dx = intArrayOf(0, 0, -1, 1)
    val dy = intArrayOf(-1, 1, 0, 0)
    for (i in 0 until 4) {
        val x = node.i / 3 + dx[i]
        val y = node.i % 3 + dy[i]
        if (x in 0..2 && y in 0..2) {
            val nextIdx = x * 3 + y
            val nextList = node.list.toMutableList()
            nextList[node.i] = nextList[nextIdx].also { nextList[nextIdx] = nextList[node.i] }
            val nextNode = Node(nextList, nextIdx, node.step + 1, h(nextList, target))
            val t = dfs(nextNode, g + 1, deep, target)
            if (t == -1) return -1
            if (t < min) min = t
        }
    }
    return min
}

private fun h(list: List<Int>, target: List<Int>): Int {
    var dist = 0
    for (i in list.indices) {
        if (list[i] != 0) {
            val tx = target.indexOf(list[i]) / 3
            val ty = target.indexOf(list[i]) % 3
            val x = i / 3
            val y = i % 3
            dist += abs(x - tx) + abs(y - ty)
        }
    }
    return dist
}

image-20240718172942105

于是就AC啦，第一次A绿题，太激动了QwQ

留言