人工智能经典问题八数码求解
实际上是将求解转为寻找最优节点的问题，算法流程如下：
- 求非0元素的逆序数的和，判断是否有解
- 将开始状态放到节点集，并设置访问标识位为true
- 从节点集中取出h(x)+g(x)最小的节点
- 判断取出的节点的状态是不是最终状态，如果是的话则回溯打印
- 找出取出的节点的状态中的0的位置
- 对取出的节点进行move操作，包含up down left right
- 如果move后的状态的访问标识位为false，则添加。否则什么都不做
需要注意：节点的数据结构如下
- 状态：int数组
- h(x)：当前节点的状态到目标状态的距离
- g(x)：当前节点的状态到初始状态的距离
- 动作：到当前节点所进行的move类型
- 父节点：记录上一个状态，方便回溯打印
使用go语言实现如下
-
main.go
package main import ( "container/heap" "github.com/gookit/color" "log" "os" "os/signal" "syscall" ) var ( start = []int{2, 8, 3, 1, 6, 4, 7, 0, 5} target = []int{1, 2, 3, 8, 0, 4, 7, 6, 5} ) var ( movables = []string{"up", "down", "left", "right"} moveOffsets = map[string]int{"up": -3, "down": 3, "left": -1, "right": 1} ) var ( visited = make(map[string]bool) ) func main() { color.BgCyan.Println("Y02114562") printFun := func(list []int) { for _, i := range list { color.BgLightCyan.Print(i, ",") } color.BgLightCyan.Print("\n") } printFun(start) printFun(target) if reverseSum(start) != reverseSum(target) { log.Fatal("不可解") } path, steps := solve(start) if steps == -1 { log.Fatal("No solution") } color.BgGreen.Println("只需:", steps, "步") color.BgGreen.Println("操作:", path) quit := make(chan os.Signal, 1) signal.Notify(quit, syscall.SIGINT, syscall.SIGTERM) <-quit } // 启发函数：h(x) 从当前状态到目标的距离 func manhattanDistance(state []int) int { distance := 0 for i := 0; i < 9; i++ { if state[i] != 0 { row1, col1 := i/3, i%3 // 遍历所有不为0的点，计算他与他的目标位置的曼哈顿距离 for j := 0; j < 9; j++ { if state[i] == target[j] { row2, col2 := j/3, j%3 distance += abs(row1-row2) + abs(col1-col2) break } } } } return distance } // 启发式搜索：八数码问题求解 func solve(start []int) ([]string, int) { // 创建起始节点 startNode := &Node{ State: start, Heuristic: manhattanDistance(start), G: 0, PrevMove: "", PrevNode: nil, } // 创建优先队列 pq := make(PriorityQueue, 0) heap.Init(&pq) heap.Push(&pq, startNode) visited[listToString(startNode.State)] = true // A*搜索 for pq.Len() > 0 { currentNode := heap.Pop(&pq).(*Node) // 到达目标状态，返回路径 if listToString(currentNode.State) == listToString(target) { path := make([]string, 0) for currentNode.PrevNode != nil { path = append(path, currentNode.PrevMove) currentNode = currentNode.PrevNode } return func(slice []string) ([]string, int) { for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 { slice[i], slice[j] = slice[j], slice[i] } return slice, len(path) }(path) } zeroIndex := func(state []int) int { for i, num := range state { if num == 0 { return i } } return -1 }(currentNode.State) for _, move := range movables { if canMove(move, zeroIndex) { newState := make([]int, len(currentNode.State)) copy(newState, currentNode.State) newZeroIndex := zeroIndex + moveOffsets[move] newState[zeroIndex], newState[newZeroIndex] = newState[newZeroIndex], newState[zeroIndex] // 创建新节点 newNode := &Node{ State: newState, Heuristic: manhattanDistance(newState), G: currentNode.G + 1, PrevMove: move, PrevNode: currentNode, } // 如果新状态未被访问，则加入优先队列和已访问集合 if !visited[listToString(newState)] { heap.Push(&pq, newNode) visited[listToString(newState)] = true } } } } // 没有找到解 return nil, -1 } -
node.go
package main // Node 节点结构体 type Node struct { State []int // 当前状态 Heuristic int // 启发函数值 G int // 初始节点到当前节点 PrevMove string // 上一步移动的方向 PrevNode *Node // 上一步的节点 } // PriorityQueue 优先队列 type PriorityQueue []*Node // Len 优先队列的方法：计算长度 func (pq PriorityQueue) Len() int { return len(pq) } // Less 优先队列的方法：比较优先级 func (pq PriorityQueue) Less(i, j int) bool { return pq[i].Heuristic+pq[i].G < pq[j].Heuristic+pq[j].G } // Swap 优先队列的方法：交换元素 func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] } // Push 优先队列的方法：向队列中插入元素 func (pq *PriorityQueue) Push(x interface{}) { node := x.(*Node) *pq = append(*pq, node) } // Pop 优先队列的方法：从队列中弹出元素 func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) node := old[n-1] *pq = old[0 : n-1] return node } -
tool.go
package main import "fmt" // 辅助函数：判断是否可移动 func canMove(move string, zeroIndex int) bool { if move == "up" && zeroIndex >= 3 { return true } if move == "down" && zeroIndex <= 5 { return true } if move == "left" && zeroIndex%3 != 0 { return true } if move == "right" && zeroIndex%3 != 2 { return true } return false } // 辅助函数：将[]int转换为字符串 func listToString(state []int) string { str := "" for _, num := range state { str += fmt.Sprintf("%d", num) } return str } // 辅助函数：求除了0之外的逆序和 func reverseSum(arr []int) bool { sum := 0 for i := 1; i < len(arr); i++ { if arr[i] != 0 { for j := 0; j < i; j++ { if arr[j] > arr[i] { sum++ } } } } return sum%2 != 0 } // 辅助函数：计算绝对值 func abs(num int) int { if num < 0 { return -num } return num }
运行效果
