人工智能答案

序言

人工智能考试结束了，然后educoder上也算入总成绩，对此我整理了一下答案，方便大家享用。

正文

神经网络

第一关 神经网络概述

1.A
2.ABCD
3.A

第二关 BP 神经网络

import numpy as np

def loaddataset(filename):
    fp = open(filename)

    #存放数据
    dataset = []

    #存放标签
    labelset = []
    for i in fp.readlines():
        a = i.strip().split()

        #每个数据行的最后一个是标签数据
        dataset.append([float(j) for j in a[:len(a)-1]])
        labelset.append(int(float(a[-1])))
    return dataset, labelset


#x为输入层神经元个数，y为隐层神经元个数，z输出层神经元个数
def parameter_initialization(x, y, z):

    #隐层阈值
    value1 = np.random.randint(-5, 5, (1, y)).astype(np.float64)

    #输出层阈值
    value2 = np.random.randint(-5, 5, (1, z)).astype(np.float64)

    #输入层与隐层的连接权重
    weight1 = np.random.randint(-5, 5, (x, y)).astype(np.float64)

    #隐层与输出层的连接权重
    weight2 = np.random.randint(-5, 5, (y, z)).astype(np.float64)

    return weight1, weight2, value1, value2

#返回sigmoid函数值
def sigmoid(z):
#********** Begin **********#
    return 1 / (1 + np.exp(-z))
#********** End **********#


'''
weight1:输入层与隐层的连接权重
weight2:隐层与输出层的连接权重
value1:隐层阈值
value2:输出层阈值
'''
def trainning(dataset, labelset, weight1, weight2, value1, value2):
    #x为步长
    x = 0.01
    for i in range(len(dataset)):
        #输入数据
        inputset = np.mat(dataset[i]).astype(np.float64)
        #数据标签
        outputset = np.mat(labelset[i]).astype(np.float64)
        #隐层输入
        input1 = np.dot(inputset, weight1).astype(np.float64)
        #隐层输出
        output2 = sigmoid(input1 - value1).astype(np.float64)
        #输出层输入
        input2 = np.dot(output2, weight2).astype(np.float64)
        #输出层输出
        output3 = sigmoid(input2 - value2).astype(np.float64)
 
        #更新公式由矩阵运算表示
        a = np.multiply(output3, 1 - output3)
        g = np.multiply(a, outputset - output3)
        b = np.dot(g, np.transpose(weight2))
        c = np.multiply(output2, 1 - output2)
        e = np.multiply(b, c)
 
        value1_change = -x * e
        value2_change = -x * g
        weight1_change = x * np.dot(np.transpose(inputset), e)
        weight2_change = x * np.dot(np.transpose(output2), g)
 
        #更新参数
        value1 += value1_change
        value2 += value2_change
        weight1 += weight1_change
        weight2 += weight2_change
    return weight1, weight2, value1, value2


def testing(dataset, labelset, weight1, weight2, value1, value2):
    #记录预测正确的个数
    rightcount = 0
    for i in range(len(dataset)):
        #计算每一个样例通过该神经网路后的预测值
        inputset = np.mat(dataset[i]).astype(np.float64)
        outputset = np.mat(labelset[i]).astype(np.float64)
        output2 = sigmoid(np.dot(inputset, weight1) - value1)
        output3 = sigmoid(np.dot(output2, weight2) - value2)
 
        #确定其预测标签
        if output3 > 0.5:
            flag = 1
        else:
            flag = 0
        if labelset[i] == flag:
            rightcount += 1
        #输出预测结果
        print("预测为%d   实际为%d"%(flag, labelset[i]))
    #返回正确率
    return rightcount / len(dataset)

第三关 Hopfield 神经网络

import numpy as np
import random
from random import randint
from matplotlib import pyplot as plt
#根据Hebb学习规则计算神经元之间的连接权值
def calcWeight(savedsample):
    N = len(savedsample[0])
    P = len(savedsample)
    mat = [0]*N
    returnMat = []
    for i in range(N):
        m = mat[:]
        returnMat.append(m)
    for i in range(N):
        for j in range(N):
            if i==j:
                continue
            sum = 0
            for u in range(P):
                sum += savedsample[u][i] * savedsample[u][j]
            returnMat[i][j] = sum/float(N)
    return returnMat
#根据神经元的输入计算神经元的输出（静态突触）
def calcXi(inMat , weighMat):
    #假设计算第t次循环后神经元的输出时，输入的参数inMat表示第t-1次循环后神经元的输出。即用上一次循环的输出做本次循环的输入。
    #weighMat权值矩阵
    returnMat = inMat
    choose = []
    for i in range(len(inMat)//5):
        #随机改变N/5个神经元的值，该参数可调，也可同时改变所有神经元的值
        choose.append(random.randint(0,len(inMat)-1))
    for i in choose:
        sum = 0
        #网络动态演变
        #********** Begin **********#
        for j in range(len(inMat)):
            sum += weighMat[i][j] * inMat[j]
        if sum>=0:
            returnMat[i] = 1
        else: returnMat[i] = -1
        #********** End **********#
    return returnMat
    
#加噪函数，在记忆样本的基础上增加30%的噪声：
def addnoise(mytest_data,n):
    #mytest_data：网络矩阵 n:节点数 
    #********** Begin **********#
    for x in range(n):
        for y in range(n):
            if random.randint(0, 10) > 7:
                mytest_data[x * n + y] = -mytest_data[x * n + y]
    #********** End **********#
    return mytest_data
    
#标准输出函数：data 为联想记忆后的矩阵，N 为方阵行数：
def regularout(data,N):
    for j in range(N):
        ch = ""
        for i in range(N):
        #矩阵元素值为 1 则输出“ X ”，否则输出“ ”
        #********** Begin **********#
         ch += " " if data[j*N+i] == -1 else "X"
        #********** Begin **********#
        print(ch)

第四关 卷积神经网络

import numpy as np

def my_conv(inputmatrix,kernel):
    output_size = (len(inputmatrix)-len(kernel)+1)
    res = np.zeros([output_size,output_size],np.float32)
    for i in range(len(res)):
        for j in range(len(res)):
            res[i][j] = compute_conv(inputmatrix,kernel,i,j)
    return res

#两个矩阵的卷积算法
def compute_conv(inputmatrix,kernel,i,j):
    #inputmatrix为输入矩阵，kernel为卷积核，i,j分别是每次卷积运算的首元素地址
    res = 0
    #********** Begin **********#
    for kk in range(3):
        for k in range(3):
            #print(input[i+kk][j+k])
            res +=inputmatrix[i+kk][j+k]*kernel[kk][k] 
    #********** End **********#
    return res

机器学习

第一关 机器学习概述

A
AB
A

第二关 线性回归

import numpy as np
import pandas as pd
#计算代价函数J(θ)
def computeCost(X, y, theta):
# X 、 y 、 theta 与数据预处理参数保持一致
#返回代价函数的值（参考编程要求中的代价函数函数）
#********** Begin **********#
    inner=np.power(((X*theta.T)-y),2) 
    return np.sum(inner)/(2*len(X))   
#********** End **********#

#批量梯度下降
#返回参数 θ 的值和每次迭代后代价函数的值，梯度下降公式参考编程要求梯度下降公式
def gradientDescent(X, y, theta, alpha, epoch):
# X 、 y 、 theta 与数据预处理参数保持一致
# alpha :学习率（取值：alpha = 0.01）
# epoch :迭代次数（取值：epoch = 1000）
    cost = np.zeros(epoch)  # 初始化一个 ndarray ，包含每次 epoch 的cost
    #********** Begin **********#
    temp=np.matrix(np.zeros(theta.shape))
    parameters=int(theta.flatten().shape[1])
    cost=np.zeros(epoch)
    m=X.shape[0]

    for i in range(epoch):
        temp=theta-(alpha/m)*(X*theta.T-y).T*X
        theta=temp
        cost[i]=computeCost(X,y,theta)
    #********** End **********#
    return theta, cost

第三关 逻辑回归

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import scipy.optimize as opt

# S 型函数
def sigmoid(z):
    #返回 sigmoid 的函数值，z 为函数变量（参考编程要求中的 sigmoid 函数）
    #********** Begin **********#
     return 1 / (1 + np.exp(-z))
    #********** End **********#

#代价函数
def cost(theta, X, y):
    #X 、 y 、 theta 与数据预处理参数保持一致
    #返回代价函数的值（参考编程要求中的代价函数）
    #********** Begin **********#
    first = (-y) * np.log(sigmoid(X @ theta))
    second = (1 - y)*np.log(1 - sigmoid(X @ theta))
    return np.mean(first - second) 
    #********** End **********#

#批量梯度下降
def gradient(theta, X, y):
    return (X.T @ (sigmoid(X @ theta) - y))/len(X)

#假设函数
def predict(theta, X):
    #X 、 y 、 theta 与数据预处理与参数保持一致
    #将所有预测出的值存储在 list 中并返回（参考编程要求中的假设函数）
    #********** Begin **********#
    probability = sigmoid(X@theta)
    return [1 if x >= 0.5 else 0 for x in probability]  # return a list
    #********** End **********#

第四关 支持向量机

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from scipy.io import loadmat
from sklearn.svm import SVC

#读文件
data1=loadmat('/data/workspace/myshixun/project/src/step4/ex6data1.mat')
#数据预处理
data=pd.DataFrame(data1['X'],columns=['x1','x2'])
data['y']=data1['y']

#初始化 SVC
#********** Begin **********#
svc1=SVC(C=1,kernel='linear')
#********** End **********#

#在数据集(X,y)上使用 SVM 模型进行数据拟合
#********** Begin **********#
svc1.fit(data1['X'],data1['y'].ravel())#拟合
#当前分类器的准确率
svc1.score(data1['X'],data1['y'].ravel())
#********** End **********#


#在数据集(X,y)上使用 SVM 模型进行数据拟合
#********** Begin **********#

#********** End **********#

第五关 聚类

import scipy.io as sio # load mat
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd
import numpy as np
from sklearn.cluster import KMeans

#生成随机的k个中心,请使用sample(k)
def random_init(data, k):
    #data：数据集 k：聚类中心个数
    #返回 k 个聚类中心并转换成array数组
    #********** Begin **********#
    return data.sample(k).as_matrix() #as_matrix(): 转换成array
    #********** End **********#

#单个找寻聚类
def find_cluster(x, centroids):
    #x:待聚类点坐标  centroids:中心坐标
    #********** Begin **********#
    distances = np.apply_along_axis(func1d=np.linalg.norm, axis=1 , arr=x-centroids )
    #********** End **********#
    return np.argmin(distances)

# 集体data聚类标签
def assign_cluster(data, centroids):
    return np.apply_along_axis(lambda x: find_cluster(x, centroids), axis=1, arr=data.as_matrix())
#  data中增加一列聚类标签C
def combineDataC(data, C):
    dataC = data.copy()
    dataC['C'] = C
    return dataC

# 新中心点，同时去掉C， 再转换成array数组
def newCentroids(data, C):
    dataC = combineDataC(data, C)
    return dataC.groupby('C', as_index=False).mean().sort_values(by='C').drop('C', axis=1).as_matrix()


# 损失函数
def cost(data, centroids, C):
    #data:数据集 centroids:中心坐标 C:聚类标签
    m = data.shape[0] # 样本量
    dataCentroids = centroids[C] # 各行的中心坐标
    #********** Begin **********#
    distances = np.apply_along_axis(func1d=np.linalg.norm, axis= 1, arr= data.as_matrix()-dataCentroids )
    #********** End **********#
    return distances.sum()/m


# kmeans通道，运行一次
def kMeansIter(data, k, epoch=100, tol=0.0001):
    # 生成最初的中心坐标
    centroids = random_init(data, k)

    costProgress = []  # 用来存放递归聚类的每次损失
    # 分配聚类标签
    for i in range(epoch):
        C = assign_cluster(data, centroids)
        centroids = newCentroids(data, C)
        costProgress.append(cost(data, centroids, C))

        if len(costProgress) > 1:
            if np.abs(costProgress[-1] - costProgress[-2]) / costProgress[-1] < tol:
                break

    return C, centroids, costProgress[-1]

# 每个k运行n_init次，套用kmeans通道
def kMeans(data, k, epoch=100, n_init=10):
    tries = np.array([kMeansIter(data, k) for _ in range(n_init)])
    leasrCostIndex = np.argmin(tries[:, -1])
    return tries[leasrCostIndex]

确定性推理

第一关 推理概述

1.A
2.D
3.ABC
4.ABCD
5.C
6.ABCD

第二关 自然演绎推理

1.C
2.F

第三关 鲁宾孙归结原理

1.A
2.A
3.A

第四关 归结反演

S = []  # 以列表形式存储子句集S

""" 读取子句集文件中子句，并存放在S列表中 - 每个子句也是以列表形式存储 - 以析取式分割 - 例如：～p ∨ ～q ∨ r 存储形式为 ['～p', '～q', 'r'] """


def readClauseSet(filePath):
    global S
    for line in open(filePath, mode='r', encoding='utf-8'):
        line = line.replace(' ', '').strip()
        line = line.split('∨')
        S.append(line)


""" - 为正文字，则返回其负文字 - 为负文字，则返回其正文字 """


def opposite(clause):
    if '～' in clause:
        return clause.replace('～', '')
    else:
        return '～' + clause


""" 归结 """


def resolution():
    global S
    end = False
    while True:
        if end: break
        father = S.pop()
        for i in father[:]:
            if end: break
            for mother in S[:]:
                if end: break
                j = list(filter(lambda x: x == opposite(i), mother))
                if j == []:
                    continue
                else:
                    print('\n亲本子句：' + ' ∨ '.join(father) + ' 和 ' + ' ∨ '.join(mother))
                    father.remove(i)
                    mother.remove(j[0])
                    #********** Begin **********#
                    if(father == [] and mother == []):
                        print('归结式：NIL')
                        end = True
                    elif father == []:
                        print('归结式：' + ' ∨ '.join(mother))
                    elif mother == []:
                        print('归结式：' + ' ∨ '.join(mother))
                    else:
                        print('归结式：' + ' ∨ '.join(father) + ' ∨ ' + ' ∨ '.join(mother))
                    #********** End **********#

不确定性推理

第一关 可信度方法

1.C
2.A
3.D

第二关 证据理论

1.D
2.B
3.A

第三关 模糊推理基础

1.A 
2.B
3.C
4.A
5.B

第四关 模糊推理及其应用

OIL=100.0#定义油渍论域
Stain=100.0#定义污渍论域
def ruleMD(stain):
    if stain<0 or stain>100:
        return 0.0
    else:#当传入的参数在0-100之间时，该处有两种情况
        # 计算MD的结果，并且和同参数下的SD结果相比较，得出一个结果
        if stain>=0 and stain<=50:
            return stain/50.0
        else:
        # 同上的操作，得出结果和同参数下的LD相比较
         return (100-stain)/50.0
def ruleSD(stain):
    #SD部分的rule
    #当输入的参数0 <= x <= 50, 执行该方法
    result=(50-stain)/50.0
    returnMDresult=ruleMD(stain)
    #传参数到MD中，计算，并比较
    #1、相同，则返回结果为SD，2、SD的结果大，则返回SD，3、MD的结果大，则返回MD的返回值
    if result<returnMDresult:
        return 2.0
    else:
        return 1.0
def ruleLD(stain):
    #LD部分的rule
    #当输入的参数在50 - 100之间时，执行
    #同时将参数传入给MD，同时比较MD方法传回来的参数和该方法求出的值相比较，求出最后的最适合的预测值
    # ********** Begin **********#
    returnMDresult = ruleMD(stain)
    result = (stain - 50) / 50.0
    if result<returnMDresult:
        return 2.0
    else:
         return 3.0


    # ********** End **********#
def ruleMG(oil):
    #当传入的参数在0 - 100之间时，该处有两种情况
    if oil<0 or oil>100:
        return 0#当在论域之外时，直接返回无结果
    else:
        if oil>=0 and oil<=50:
            return oil/50.0#计算MD的结果，并且和同参数下的SD结果相比较，得出一个结果
        else:
            return (100 - oil) / 50#同上的操作，得出结果和同参数下的LD相比较
def ruleSG(oil):
    if oil<0 or oil>50:
        return 0.0
    else:
        #SG部分的rule
        #当输入的参数0<=x<=50,执行该方法
        result=(50-oil)/50.0
        returnMGresult=ruleMG(oil)
        #传参数到MD中，计算，并比较
        #1、相同，则返回结果为SD，2、SD的结果大，则返回SD，3、MD的结果大，则返回MD的返回值
        if result<returnMGresult:
            return 2.0
        else:
            return 1.0
def ruleLG(oil):
   # LD部分的rula
   #当输入的参数在50 - 100之间时，执行
   #同时将参数传入给MG，同时比较MG方法传回来的参数和该方法求出的值相比较，求出最后的最适合的预测值
   returnMGresult=ruleMG(oil)
   result=(oil-50)/50.0
   #比较后，得到预测值
   if result<returnMGresult:
       return 2.0
   else:
       return 3.0

#F函数，总的函数，从该函数中分流到rule的三个函数中
def Function(oil,stain):
    #VS: SD, SG
    #S: MD, SG
    #M: SD, MG     MD, MG     LD, SG
    #L: SD, LG     MD，LG     LD，MG
    #XL: LD, LG
    #根据规则输出最后的洗涤时间
    #需要客户的正确输入
    # ********** Begin **********#
        
    
        if oil<0 or oil>OIL or stain<0 or stain>Stain:
          return 0.0
        else:
          if oil>=0 and oil<=50:
             result_G = ruleSG(oil)
          else:
             result_G = ruleLG(oil)
          if stain>=0 and stain<=50:
             result_D = ruleSD(stain)
          else: 
             result_D = ruleLD(stain)

    # ********** End **********#
        #比较最后的结果,返回结果控制规则表，例如VS在表格中的坐标是（1,1）,S的坐标是（2,1）
        if result_D==1.0 and result_G==1.0:
            return 1 #return VS
        elif result_G==1.0 and result_D==2.0:
            return 2 #return S
        elif (result_D==1.0 and result_G==2.0) or (result_G==2.0 and result_D==2.0) or (result_G==1.0 and result_D==3.0):
            return 3 #reutrn M
        elif (result_D==1.0 and result_G==3.0) or (result_D==2.0 and result_G==3.0) or (result_D==3.0 and result_G==2.0):
            return 4 #return L
        elif result_G==3.0 and result_D==3.0:
            return 5 #return VL

知识表示概述

第一关

B
ABCD
A

一般谓词逻辑表示法

第一关

A
B
D

第二关

B
C
ABD
B
B

第三关

ABCD
A
A

产生式表示法与框架表示法

第一关 产生式表示法

A
D
A
ABCD
ABCD

第二关 产生式系统

# 动物识别系统
# 自定义函数，判断有无重复元素
def judge_repeat(value, list=[]):
    for i in range(0, len(list)):
        if (list[i] == value):
            return 1
        else:
            if (i != len(list) - 1):
                continue
            else:
                return 0
# 自定义函数，对已经整理好的综合数据库real_list进行最终的结果判断
def judge_last(list):
    for i in list:
        if (i == '23'):
            for i in list:
                if (i == '12'):
                    for i in list:
                        if (i == '21'):
                            for i in list:
                                if (i == '13'):
                                    print("黄褐色，有斑点,哺乳类，食肉类->金钱豹\n")
                                    print("所识别的动物为金钱豹")
                                    return 0
                                elif (i == '14'):
                                    print("黄褐色，有黑色条纹，哺乳类，食肉类->虎\n")
                                    print("所识别的动物为虎")
                                    return 0
        elif (i == '14'):
            for i in list:
                if (i == '24'):
                    print("有黑色条纹，蹄类->斑马\n")
                    print("所识别的动物为斑马")
                    return 0
        elif (i == '24'):
            for i in list:
                if (i == '13'):
                    for i in list:
                        if (i == '15'):
                            for i in list:
                                if (i == '16'):
                                    print("有斑点，有黑色条纹，长脖，蹄类->长颈鹿\n")
                                    print("所识别的动物为长颈鹿")
                                    return 0
        elif (i == '20'):
            for i in list:
                if (i == '22'):
                    print("善飞，鸟类->信天翁\n")
                    print("所识别的动物为信天翁")
                    return 0
        #********* Begin *********#
        elif (i == '22'):
            for i in list:
                if (i == '4'):
                    for i in list:
                        if (i == '15'):
                            for i in list:
                                if (i == '16'):
                                    print("不会飞，长脖，长腿，鸟类->鸵鸟\n")
                                    print("所识别的动物为鸵鸟")
                                    return 0
        # ********* Begin *********#
        elif (i == '4'):
            for i in list:
                if (i == '22'):
                    for i in list:
                        if (i == '18'):
                            for i in list:
                                if (i == '19'):
                                    print("不会飞，会游泳，黑白二色，鸟类->企鹅\n")
                                    print("所识别的动物企鹅")
                                    return 0
        else:
            if (list.index(i) != len(list) - 1):
                continue
            else:
                print("\n根据所给条件无法判断为何种动物")

第三关 框架表示法

B
B
ACD

问题求解的基本原理

第一关 状态空间法问题求解

A
ABC
B

第二关 问题归约法问题求解

B
BCD
ACD

盲目搜索算法

第一关 广度优先搜索

def PlayMazz(mazz, start, end):
    '''
    走迷宫，从start走到end
    :param mazz: 图
    :param start: 图的起点
    :param end: 图的出口
    '''
    # queue为队列，当队列为空或者当前地点为终点时搜索结束
    visited, queue = set(), [start]
    ans = []
    #********* Begin *********#
    while queue:
        node = queue.pop(0)
        ans.append(node)
        if node==end:
            break
        for c in mazz[node]:
            queue.append(c)
    print(''.join(ans))

    #********* End *********#

第二关 深度优先搜索

def PlayMazz(graph, start,end, visited=None):
    '''
    深度优先搜索，从1走到9
    :param graph: 搜索的空间
    :param start: 开始搜索的起点
    :param visited:  已经搜索过的点集合
    '''
    if visited is None:
        visited = set()
    # visited.add(start)
    # print(start, end='')
    # 当前地点为终点时结束搜索
    # if start == end:
    #     return
    #********* Begin *********#
    # 看看当前位置有哪些路可以走，如果能走并且之前没有走过就走
    stack = [start]
    ans = []
    while stack:
        node = stack.pop(-1)
        if node in visited:
            continue
        ans.append(node)
        visited.add(node)
        if node==end:
            break
        for c in graph[node][::-1]:
            stack.append(c)
    print(''.join(ans))
        
    #********* End *********#

第三关 盲目搜索算法的应用

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self, n=0):
        # self.vis = [[0]*n for _ in range(n)]    #用于标记是否存在皇后的二维列表（初始值全为0）
        self.ans = 0                #用于存储答案（N皇后方案数，初始值0）
        self.n = n                  #用于存储皇后数量n

    def solveNQueens(self):
        """求解N皇后问题（调用self.DFS函数）
        :rtype: self.ans: int    #返回N皇后放置方案数
        """
        #请在这里补充代码，完成本关任务
        #********** Begin ********#
        self.exit_column = set()
        self.exit_diagonal1 = set()
        self.exit_diagonal2 = set()
        self.DFS(0, self.n)
        return self.ans
        #********** End **********#
    def DFS(self, row, n):
        """深度优先搜索N皇后问题的解空间
        :type: row: int      #NxN棋盘的第row行
        :type: n: int        #皇后数量n
        :rtype: None         #无返回值
        """
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        if row == n:
            self.ans += 1
            return

        for i in range(n):
            if i not in self.exit_column and i+row not in self.exit_diagonal1 and i-row not in self.exit_diagonal2:
                self.exit_column.add(i)
                self.exit_diagonal1.add(i+row)
                self.exit_diagonal2.add(i-row)

                self.DFS(row+1, n)

                self.exit_column.remove(i)
                self.exit_diagonal1.remove(i+row)
                self.exit_diagonal2.remove(i-row)
        #********** End **********#

启发式搜索算法

第一关 评估函数和启发信息

A
A

第二关 A*搜索算法

class Array2D:
    """
        说明：
            1.构造方法需要两个参数，即二维数组的宽和高
            2.成员变量w和h是二维数组的宽和高
            3.使用：‘对象[x][y]’可以直接取到相应的值
            4.数组的默认值都是0
    """

    def __init__(self, w, h):
        self.w = w
        self.h = h
        self.data = []
        self.data = [[0 for y in range(h)] for x in range(w)]

    def showArray2D(self):
        for y in range(self.h):
            for x in range(self.w):
                print(self.data[x][y], end=' ')
            print("")

    def __getitem__(self, item):
        return self.data[item]


class Point:
    """
    表示一个点
    """

    def __init__(self, x, y):
        self.x = x;
        self.y = y

    def __eq__(self, other):
        if self.x == other.x and self.y == other.y:
            return True
        return False

    def __str__(self):
        return "x:" + str(self.x) + ",y:" + str(self.y)


class AStar:
    """
    AStar算法的Python3.x实现
    """

    class Node:  # 描述AStar算法中的节点数据
        def __init__(self, point, endPoint, g=0):
            self.point = point  # 自己的坐标
            self.father = None  # 父节点
            self.g = g  # g值，g值在用到的时候会重新算
            self.h = (abs(endPoint.x - point.x) + abs(endPoint.y - point.y)) * 10  # 计算h值

    def __init__(self, map2d, startPoint, endPoint, passTag=0):
        """
        构造AStar算法的启动条件
        :param map2d: Array2D类型的寻路数组
        :param startPoint: Point或二元组类型的寻路起点
        :param endPoint: Point或二元组类型的寻路终点
        :param passTag: int类型的可行走标记（若地图数据!=passTag即为障碍）
        """
        # 开启表
        self.openList = []
        # 关闭表
        self.closeList = []
        # 寻路地图
        self.map2d = map2d
        # 起点终点
        #********** Begin **********#
        if isinstance(startPoint, Point) and isinstance(endPoint, Point):
            self.startPoint = startPoint
            self.endPoint = endPoint
        else:
            self.startPoint = Point(*startPoint)
            self.endPoint = Point(*endPoint)
        #********** End **********#
        # 可行走标记
        self.passTag = passTag
        
    def getMinNode(self):
        """
        获得openlist中F值最小的节点
        :return: Node
        """

        #********** Begin **********#
        currentNode = self.openList[0]
        for node in self.openList:
            if node.g + node.h < currentNode.g + currentNode.h:
                currentNode = node
        return currentNode
        #********** End **********#

    def pointInCloseList(self, point):
        for node in self.closeList:
            if node.point == point:
                return True
        return False

    def pointInOpenList(self, point):
        for node in self.openList:
            if node.point == point:
                return node
        return None

    def endPointInCloseList(self):
        for node in self.openList:
            if node.point == self.endPoint:
                return node
        return None

    def searchNear(self, minF, offsetX, offsetY):
        """
        搜索节点周围的点
        :param minF:F值最小的节点
        :param offsetX:坐标偏移量
        :param offsetY:
        :return:
        """
        # 越界检测
        #********** Begin **********#
        if minF.point.x + offsetX < 0 or minF.point.x + offsetX > self.map2d.w - 1 or minF.point.y + offsetY < 0 or minF.point.y + offsetY > self.map2d.h - 1:
            return
        #********** End **********#
        # 如果是障碍，就忽略
        if self.map2d[minF.point.x + offsetX][minF.point.y + offsetY] != self.passTag:
            return
        # 如果在关闭表中，就忽略
        currentPoint = Point(minF.point.x + offsetX, minF.point.y + offsetY)
        if self.pointInCloseList(currentPoint):
            return
        # 设置单位花费
        if offsetX == 0 or offsetY == 0:
            step = 10
        else:
            step = 14
        # 如果不再openList中，就把它加入openlist
        #********** Begin **********#
        currentNode = self.pointInOpenList(currentPoint)
        if not currentNode:
            currentNode = AStar.Node(currentPoint, self.endPoint, g=minF.g + step)
            currentNode.father = minF
            self.openList.append(currentNode)
            return
        #********** End **********#
        # 如果在openList中，判断minF到当前点的G是否更小
        if minF.g + step < currentNode.g:  # 如果更小，就重新计算g值，并且改变father
            currentNode.g = minF.g + step
            currentNode.father = minF

    def start(self):
        """
        开始寻路
        :return: None或Point列表（路径）
        """
        # 判断寻路终点是否是障碍
        if self.map2d[self.endPoint.x][self.endPoint.y] != self.passTag:
            return None

        # 1.将起点放入开启列表
        startNode = AStar.Node(self.startPoint, self.endPoint)
        self.openList.append(startNode)
        # 2.主循环逻辑
        while True:
            # 找到F值最小的点
            minF = self.getMinNode()
            # 把这个点加入closeList中，并且在openList中删除它
            self.closeList.append(minF)
            self.openList.remove(minF)
            # 判断这个节点的上下左右节点
            #********** Begin **********#
            self.searchNear(minF, 0, -1)
            self.searchNear(minF, 0, 1)
            self.searchNear(minF, -1, 0)
            self.searchNear(minF, 1, 0)
            #********** End **********#
            # 判断是否终止
            point = self.endPointInCloseList()
            if point:  # 如果终点在关闭表中，就返回结果
                # print("关闭表中")
                cPoint = point
                pathList = []
                while True:
                    if cPoint.father:
                        pathList.append(cPoint.point)
                        cPoint = cPoint.father
                    else:
                        return list(reversed(pathList))
            if len(self.openList) == 0:
                return None

博弈中的搜索

第一关 博弈概述

A
A

第二关 极小极大算法

# -*- coding:utf-8 -*-
import copy     # 注意对象的深拷贝和浅拷贝的使用！！！
class GameNode:
    '''博弈树结点数据结构
    成员变量：
    map - list[[]] 二维列表，三子棋盘状态
    val - int  该棋盘状态对执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
    deepID - int 博弈树的层次深度，根节点deepID=0
    parent - GameNode，父结点
    children - list[GameNode] 子结点列表
    '''
    def __init__(self, map, val=0, deepID=0, parent=None, children=[]):
        self.map = map
        self.val = val
        self.deepID = deepID
        self.parent = parent
        self.children = children
class GameTree:
    '''博弈树结点数据结构
    成员变量：
    root - GameNode 博弈树根结点
    成员函数：
    buildTree - 创建博弈树
    '''
    def __init__(self, root):
        self.root = root                # GameNode 博弈树根结点
    def buildTree(self, root):
        '''递归法创建博弈树
        参数：
        root - GameNode 初始为博弈树根结点
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        posList = []
        for i in range(3):
            for j in range(3):
                if root.map[i][j]=='_':
                    posList.append((i,j))

        for (x, y) in posList:
            childNode = GameNode(map=copy.deepcopy(root.map),
                                 val=0, deepID=root.deepID+1, parent=root, children=[])
            if root.deepID%2==0:
                childNode.map[x][y]='x'
            else :
                childNode.map[x][y]='o'
            root.children.append(childNode)

        for childNode in root.children:
            self.buildTree(childNode)
        #********** End **********#
class MinMax:
    '''博弈树结点数据结构
    成员变量：
    game_tree - GameTree 博弈树
    成员函数：
    minmax - 极大极小值算法，计算最优行动
    max_val - 计算最大值
    min_val - 计算最小值
    get_val - 计算某棋盘状态中：执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
    isTerminal - 判断某状态是否为最终状态：无空闲棋可走
    '''
    def __init__(self, game_tree):
        self.game_tree = game_tree      # GameTree 博弈树
    def minmax(self, node):
        '''极大极小值算法，计算最优行动
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - list[map] 最优行动，即x棋子的下一个棋盘状态GameNode.map
              其中，map - list[[]] 二维列表，三子棋盘状态
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        best_val = self.max_value(node)
        best_move = []
        for childNode in node.children:
            if childNode.val == best_val and best_val==1:
                best_move.append(childNode.map)
        return best_move
        #********** End **********#
    def max_value(self, node):
        '''计算最大值
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - int 子结点中的最大的评估值
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        if self.isTerminal(node):
            val = self.get_value(node)
            node.val = val
            return val
        inf_val = float('inf')
        max_val = -inf_val
        for childNode in node.children:
            max_val = max(max_val, self.min_value(childNode))
        node.val = max_val
        return max_val
        #********** End **********#
    def min_value(self, node):
        '''计算最小值
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - int 子结点中的最小的评估值
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        if self.isTerminal(node):
            val = self.get_value(node)
            node.val = val
            return val
        inf_val = float('inf')
        min_val = inf_val
        for childNode in node.children:
            min_val = min(min_val, self.max_value(childNode))
        node.val = min_val
        return min_val
        #********** End **********#
    def get_value(self, node):
        '''计算某棋盘状态中：执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - int 执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        for i in range(3):
            if node.map[i][0]=='o' and node.map[i][0]==node.map[i][1] and node.map[i][1]==node.map[i][2]:
                return -1
            if node.map[0][i]=='o' and node.map[0][i]==node.map[1][i] and node.map[1][i]==node.map[2][i]:
                return -1
        if node.map[0][0]=='o' and node.map[0][0]==node.map[1][1] and node.map[1][1]==node.map[2][2]:
            return -1
        if node.map[0][2]=='o' and node.map[0][2]==node.map[1][1] and node.map[1][1]==node.map[2][0]:
            return -1
        for i in range(3):
            if node.map[i][0]=='x' and node.map[i][0]==node.map[i][1] and node.map[i][1]==node.map[i][2]:
                return 1
            if node.map[0][i]=='x' and node.map[0][i]==node.map[1][i] and node.map[1][i]==node.map[2][i]:
                return 1
        if node.map[0][0]=='x' and node.map[0][0]==node.map[1][1] and node.map[1][1]==node.map[2][2]:
            return 1
        if node.map[0][2]=='x' and node.map[0][2]==node.map[1][1] and node.map[1][1]==node.map[2][0]:
            return 1
        return 0
        #********** End **********#
    def isTerminal(self, node):
        '''判断某状态是否为最终状态：无空闲棋可走（无子结点）
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - bool 是最终状态，返回True，否则返回False
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        assert node is not None
        return len(node.children)==0
        #********** End **********#

第三关 α-β剪枝算法

# -*- coding:utf-8 -*-
import copy     # 注意对象的深拷贝和浅拷贝的使用！！！
class GameNode:
    '''博弈树结点数据结构
    成员变量：
    name - string 结点名字
    val - int  结点值
    children - list[GameNode] 子结点列表
    '''
    def __init__(self, name='', val=0):
        self.name = name        # char
        self.val = val          # int
        self.children = []      # list of nodes
class GameTree:
    '''博弈树结点数据结构
    成员变量：
    root - GameNode 博弈树根结点
    成员函数：
    buildTree - 创建博弈树
    '''
    def __init__(self):
        self.root = None                # GameNode 博弈树根结点
    def buildTree(self, data_list, root):
        '''递归法创建博弈树
        参数：
        data_list - list[] like this ['A', ['B', ('E', 3), ('F', 12)], ['C', ('H', 2)], ['D', ('K', 14)]]
        root - GameNode
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        for i in range(1,len(data_list)):
            if type(data_list[i]) == list:
                root.children.append(GameNode(data_list[i][0]))
                self.buildTree(data_list[i],root.children[i-1])
            else:
                root.children.append(GameNode(data_list[i][0],data_list[i][1]))

        #********** End **********#
class AlphaBeta:
    '''博弈树结点数据结构
    成员变量：
    game_tree - GameTree 博弈树
    成员函数：
    minmax_with_alphabeta - 带AlphaBeta剪枝的极大极小值算法，计算最优行动
    max_value - 计算最大值
    min_value - 计算最小值
    get_value - 返回结点的值
    isTerminal - 判断某结点是否为最终结点
    '''
    def __init__(self, game_tree):
        self.game_tree = game_tree      # GameTree 博弈树
    def minmax_with_alphabeta(self, node):
        '''带AlphaBeta剪枝的极大极小值算法，计算最优行动
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - GameNode 最优行动的结点
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        clf = self.max_value(node,-10000,10000)
        for child in node.children:
            if child.val == clf:
                return child;
        #********** End **********#
    def max_value(self, node, alpha, beta):
        '''计算最大值
        参数：
        node - GameNode 博弈树结点
        alpha - int 剪枝区间下限值
        beta - int 剪枝区间上限值
        返回值：
        clf - int 子结点中的最大的评估值
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        if self.isTerminal(node):
            return self.get_value(node)
        clf = -10000
        for child in node.children:
            clf = max(clf,self.min_value(child,alpha,beta))
            if clf >= beta:
                return clf
            alpha = max(alpha,clf)
        node.val = clf;
        return clf
        #********** End **********#
    def min_value(self, node, alpha, beta):
        '''计算最小值
        参数：
        node - GameNode 博弈树结点
        alpha - int 剪枝区间下限值
        beta - int 剪枝区间上限值
        返回值：
        clf - int 子结点中的最小的评估值
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        if self.isTerminal(node):
            return self.get_value(node)
        clf = 10000
        for child in node.children:
            clf = min(clf,self.max_value(child,alpha,beta))
            if clf <= alpha:
                return clf
            beta = min(clf,beta)
        node.val = clf;
        return clf;

        #********** End **********#
    def get_value(self, node):
        '''返回结点的值
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - int 结点的值，即 node.val
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        return node.val;
        #********** End **********#
    def isTerminal(self, node):
        '''判断某结点是否为最终结点（无子结点）
        参数：
        node - GameNode 博弈树结点
        返回值：
        clf - bool 是最终状态，返回True，否则返回False
        '''
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        if node.val == 0:
            return False
        else:
            return True
        #********** End **********#

人工智能概述

第一关 什么是人工智能？

D
ABCD

第二关 人工智能的历史

C
B

第三关 人工智能研究途径与目标

D
B

第四关 人工智能研究领域

ABCD
A