• 【人工智能实验】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 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
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43
      • 44
      • 45
      • 46
      • 47
      • 48
      • 49
      • 50
      • 51
      • 52
      • 53
      • 54
      • 55
      • 56
      • 57
      • 58
      • 59
      • 60
      • 61
      • 62
      • 63
      • 64
      • 65
      • 66
      • 67
      • 68
      • 69
      • 70
      • 71
      • 72
      • 73
      • 74
      • 75
      • 76
      • 77
      • 78
      • 79
      • 80
      • 81
      • 82
      • 83
      • 84
      • 85
      • 86
      • 87
      • 88
      • 89
      • 90
      • 91
      • 92
      • 93
      • 94
      • 95
      • 96
      • 97
      • 98
      • 99
      • 100
      • 101
      • 102
      • 103
      • 104
      • 105
      • 106
      • 107
      • 108
      • 109
      • 110
      • 111
      • 112
      • 113
      • 114
      • 115
      • 116
      • 117
      • 118
      • 119
      • 120
      • 121
      • 122
      • 123
      • 124
      • 125
      • 126
      • 127
      • 128
      • 129
      • 130
      • 131
      • 132
      • 133
      • 134
      • 135
      • 136
      • 137
      • 138
      • 139
      • 140
      • 141
      • 142

    • 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
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43

    • 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
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43
      • 44
      • 45
      • 46
      • 47
      • 48
      • 49
      • 50
      • 51
      • 52
      • 53
      • 54

    运行效果

    Y02114562

  • 相关阅读:
    Python自动操作 GUI 神器——PyAutoGUI
    YbtOJ「动态规划」第4章 树形DP
    阅读文献小技巧
    深度学习之基础模型——循环神经网络RNN
    Xilinx microblaze axi can 使用说明
    AWS SAA-C03 #99
    蓝桥杯国赛 小数第n位（数论）
    事务的四大特性----ACID
    RHCSA之Linux基础
    ArcGIS QGIS学习一：打开shp、geojson地图变形变扁问题（附最新坐标边界下载全国省市区县乡镇）
  • 原文地址：https://blog.csdn.net/qq_38177830/article/details/134436456