网站推广方案中确定目标是指百度营销推广
人工智能经典问题八数码求解
实际上是将求解转为寻找最优节点的问题，算法流程如下：
- 求非0元素的逆序数的和，判断是否有解
- 将开始状态放到节点集，并设置访问标识位为true
- 从节点集中取出h(x)+g(x)最小的节点
- 判断取出的节点的状态是不是最终状态，如果是的话则回溯打印
- 找出取出的节点的状态中的0的位置
- 对取出的节点进行move操作，包含up down left right
- 如果move后的状态的访问标识位为false，则添加。否则什么都不做
需要注意：节点的数据结构如下
- 状态：int数组
- h(x)：当前节点的状态到目标状态的距离
- g(x)：当前节点的状态到初始状态的距离
- 动作：到当前节点所进行的move类型
- 父节点：记录上一个状态，方便回溯打印
使用go语言实现如下
-
main.go
package mainimport ("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 := 0for 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%3distance += 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 := *pqn := len(old)node := old[n-1]*pq = old[0 : n-1]return node } -
tool.go
package mainimport "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 := 0for 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 }
运行效果
