北京市住房和城乡建设厅官方网站,怎么下载网页视频到本地,wordpress用户界面,怎样修改静态公司网站页面电话人工智能经典问题八数码求解
实际上是将求解转为寻找最优节点的问题#xff0c;算法流程如下#xff1a;
求非0元素的逆序数的和#xff0c;判断是否有解将开始状态放到节点集#xff0c;并设置访问标识位为true从节点集中取出h(x)g(x)最小的节点判断取出的节点的状态是不…人工智能经典问题八数码求解
实际上是将求解转为寻找最优节点的问题算法流程如下
求非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/heapgithub.com/gookit/colorlogosos/signalsyscall
)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 i1, 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].Heuristicpq[i].G pq[j].Heuristicpq[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
}运行效果
