当前位置：首页 > article >正文

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

article 2024/9/22 17:37:13

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

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

求非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
}