# 启发式搜索22数码局部搜索NM皇后问题

**Repository Path**: lxxqdddd/ai

## Basic Information

- **Project Name**: 启发式搜索22数码局部搜索NM皇后问题
- **Description**: 本项目为中国科学技术大学ai课程问题求解章节实验，问题主要包括，以两种启发式函数实现的A*搜索算法，解决了8数码问题的变种----22数码问题，第二个算法为局部搜索算法求解8皇后问题的变种----N，M皇后问题，两种局部搜索算法为：随机重开始搜索，模拟退火算法。
- **Primary Language**: C
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2018-07-23
- **Last Updated**: 2023-03-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 启发式搜索22数码局部搜索NM皇后问题

#### 项目介绍
本项目为中国科学技术大学ai课程问题求解章节实验，问题主要包括，以两种启发式函数实现的A*搜索算法，解决了8数码问题的变种----22数码问题，第二个算法为局部搜索算法求解8皇后问题的变种----N，M皇后问题，两种局部搜索算法为：随机重开始搜索，模拟退火算法。

#### 主要包括
a)	A*h1
b)	A*h2
c)	IDA*h1
d)	Ida*h2
e)	随机重开始爬山算法
f)	模拟退火算法



#### 算法思想
A*h1：基本按照书本实现，节点信心维护在qnode结构体内，维护一个优先链表，用来生成子节点。
A*h2：启发式函数采用的是欧几里得距离，性能较h1好
IDh1&&h2 :用g=f+h作为深度迭代阀值，并且迭代深度自动增加，与A*不同的地方在于使用的insert2（）函数，即为将迭代深度越界的节点插回队列当中并且是同深度节点的最末尾。
模拟退火算法：与书本的设计一样，对于N皇后的N*N-1种后继采用随机生成，然后判断是否接受。
随机重开始爬山算法：随机重开始的方法在于记录相同的h出现的次数，出现足够多是可以认为已经是局部最大点了，所以重新开始，随机赋初状态。

#### 性能
A*h1<=25层
A*h2<=35层
ID同

#### 优化
对搜索来说，用性能探查工具可以发现，%91的CPU时间用于有序插入，对插入函数的判断条件进行优化，对于g同大小的直接插在对头，可以减少到70%CPU时间。
另外，可以思考出更为高效的优化方式：
即为:对于待探索节点不在维护在优先链表中，而是维护在一个基于“桶排序“的链表数组当中，这样对于每次插入的时间复杂度可以从O(4^N)减小到O（1）,这种结论主要基于两点：H(n)是一个可以判断为有界的函数，所以每个桶的标记即为，g=h+f，则对于每个节点，只需插入到head[g]的头即可。但由于时间不足，该想法未实现。
对于查重来说，可直接利用c++的SET容器查重即可。

#### 问题介绍
请参看./question