人工智能原理作业

人工智能原理作业记录

背景

AI这门课程需要我们完成一项选择性作业，需要完成编码，演示，报告，因此写这篇文章做一些实验记录

题目

作业: (二选一)

2) 算法程序

四个同心园盘的扇区数字如图所示，
每个圆盘可以单独转动，如何设计搜索算法转动
圆盘使得8个扇区径向数字之和均为12.

分析

阴影部分数字和：48
直径部分数字和：24
转45°改变阴影部分
转90°改变直径部分
但不改变阴影部分
转180°改变扇区部分
但不改变阴影部分
也不改变直径部分

分析

题目要求使用搜索算法搜索出答案，那么我们将整个问题视为一个大的产生式，则需要做的工作就可初步分为如下几个方面：

如何表示综合数据库
如何表示规则库
如何表示控制系统

我们使用状态空间法将这些问题具体话，则可以产生如下问题：

如何表示状态空间
如何进行状态转化
使用怎样的控制策略对问题进行求解

状态空间

问题中提及的原状态是一个被划分为4个柱面+8个扇面的原，显然无法用代码完全还原原有模样。

但我们思考如何表示一个包含数字的小块。比如图中最外圈的数字为1的块，我们可以认为它位于第4扇区第4柱面。

以此为基础我们可以将整个磁盘表示为一个二维矩阵：

(柱面)(扇区)	0	1	2	3	4	5	6	7
1	2	2	5	1	5	3	4	3
2	2	1	3	4	5	3	5	2
3	1	3	2	1	3	4	2	5
4	3	2	3	4	1	3	4	5

图的存储问题在此得到了解决，此外我们为了不重复搜索状态，需要对每种状态给定一个唯一的标识符号，且，由于问题的求解需要考量每个扇区的加权和。因此我们也需要将每个扇区的和存入状态。

状态转化

如何表示状态的转化，也就是要构造一个对状态封闭的规则集。

根据题面的描述，我们的每一步操作需要对二维数组的某一行进行循环左移或右移。

而由于实际的操作是在圆盘上进行的，因此，只需保证一个方向的移动即可。

因此我们可以定义操作： $M(i,j)$ ,表示将第i行循环右移j个单位。

状态去重

为了避免不必要的重复搜索，我们需要对状态进行标记的操作。对于每个状态，判断其是否出现过，最简单的方法就是维护一个visited表，其中存放了所有已经拓展过的状态，最直接的方法就是将状态原原本本你的存入，也就是将以二维表表示的状态直接存入visited表，这样visited将是一个三维数组。

由于最坏的情况下我们需要拓展所有的状态，若我们的状态包括m行，n列，那么这样做的空间复杂度将是 $O(m^{n}n)$ ，并且判断状态是否重复需要 $O(m^{(n)}*n)$ 的复杂度

这样做显然效率非常低，于是我们考虑能否将状态表示的复杂度降低。

由于状态中每行的顺序是固定的，因此我们只需要记录每行相对初状态的相对位置即可表示每行上的状态变化。因此我们可以使用一维数组来记录每一行的相对位置，那么visted数组就能降低为2维数组。

那么用这种方式记录的状态，空间复杂度为 $O(m^n)$ ，时间复杂度为 $O(m^{n})$

控制策略

首先我们采用没有启发信息的，即 $f(n)=g(n)+h(n)$ ，其中 $h(n) = 0,g(n) = d(n)$ ，其中 $d(n)$ 表示搜索深度，即BFS算法。

具体实现：

import queue
import numpy as np
import copy


d1 = [2, 2, 5, 1, 5, 3, 4, 3]
d2 = [2, 1, 3, 4, 5, 3, 5, 2]
d3 = [1, 3, 2, 1, 3, 4, 2, 5]
d4 = [3, 2, 3, 4, 1, 3, 4, 5]
d = []

class status(object):
    def __init__(self, matrix, statusCode, columSum, columNum, rowNum):
        self.matrix = matrix
        self.statusCode = statusCode
        self.columSum = columSum
        self.columNum = columNum
        self.rowNum = rowNum
    
    def __str__(self):
        return self.matrix
    
    __repr__ = __str__

class sector(object):
    def __init__(self, data, index) :
        self.data = data
        self.index = index
    
    def set_data(self, d):
        self.data = d
    
    def __add__(self, other):
        v = self.data + other.data
        return sector(v, self.index)
   
    def __str__(self) -> str:
        return f"(%d)[%d]" %(self.data, self.index)
    __repr__ = __str__



def judge(status):
    for i in status.columSum:
        if i.data != 12:
            return False
    return True

def reverse(start, end, A):
    end = end - 1
    while start < end:
        A[start], A[end] = A[end], A[start]
        start += 1
        end -= 1

def move(status, row, step):
    length = len(status.matrix[row])
    reverse(0, length, status.matrix[row])  # 0 1 2 3 4 5 6 7 -> 7 6 5 4 3 2 1 0
    reverse(0, step, status.matrix[row])  # 7 6 5 4 3 2 1 0
    reverse(step, length, status.matrix[row])  # 7 0 1 2 3 4 5 6
    columSum = []
    for i in range(8):
        sumNow = np.sum(status.matrix[:,i])
        # print(sumNow)
        columSum.append(sumNow)
    status.columSum = columSum
    status.statusCode[row] = (status.statusCode[row] + step)%8
    # print(status.statusCode)
    return

def visited(status, visit):
    if status.statusCode in visit:
        return True
    else:
        return False

def dfs(status_origin):
    searchNum = 0  # 记录搜索次数
    visit = []
    q = queue.Queue()
    q.put(status_origin)
    status_now = copy.deepcopy(status_origin)
    temp = copy.deepcopy(status_origin)
    visit.append(temp.statusCode)
    flag = False
    while not q.empty():
        searchNum += 1
        status_now = q.get()
        # print("=======取出状态=======")
        # print(status_now.matrix)
        # print(status_now.statusCode)
        # print("======================")
        for i in range(3):
            temp = copy.deepcopy(status_now)
            move(temp, (i+1), 1)  # 移动第i个转盘，移动j次
            if not visited(temp, visit) :
                visit.append(temp.statusCode)
                if judge(temp):
                    flag = True
                    print(temp.matrix)
                    print(temp.statusCode)
                    break
                q.put(temp)
                # print("=======加入队列=======")
                # print(temp.matrix)
                # print("======================")
        if flag:
            print(searchNum)
            break
            # else:
            #     print("重复状态")
            #     print(temp.statusCode)
            #     print("======================")
        # input()


if __name__ == "__main__":
    d = [d1,d2,d3,d4]
    for i in range(len(d)):
        for j in range(len(d[i])):
            d[i][j] = sector(d[i][j], j)
    matrixO = np.array(d).reshape(4, 8)
    columSum = []
    for i in range(8):
        sumNow = np.sum(matrixO[:,i])
        # print(sumNow)
        columSum.append(sumNow)
    statusCodeO = [0, 0, 0, 0]
    statusO = status(matrixO, statusCodeO, columSum, len(d1), len(d))
    dfs(statusO)

运行结果：

[[(2)[0] (2)[1] (5)[2] (1)[3] (5)[4] (3)[5] (4)[6] (3)[7]]
 [(3)[5] (5)[6] (2)[7] (2)[0] (1)[1] (3)[2] (4)[3] (5)[4]]
 [(3)[4] (4)[5] (2)[6] (5)[7] (1)[0] (3)[1] (2)[2] (1)[3]]
 [(4)[3] (1)[4] (3)[5] (4)[6] (5)[7] (3)[0] (2)[1] (3)[2]]]  # 最终状态
[0, 3, 4, 5]  # 最终状态表示
286  # 拓展节点个数