【人工智能实验】A*算法求解8数码问题 golang

人工智能经典问题八数码求解

实际上是将求解转为寻找最优节点的问题，算法流程如下：

1. 求非0元素的逆序数的和，判断是否有解
2. 将开始状态放到节点集，并设置访问标识位为true
3. 从节点集中取出h(x)+g(x)最小的节点
4. 判断取出的节点的状态是不是最终状态，如果是的话则回溯打印
5. 找出取出的节点的状态中的0的位置
6. 对取出的节点进行move操作，包含up down left right
7. 如果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
  }
  

运行效果