头歌人工智能原理_def playmazz(mazz, start, end): ''' 走迷宫,从start走到en

盲目搜索 

 

 

def PlayMazz(mazz, start, end):
 
    '''
    走迷宫，从start走到end
    :param mazz: 图
    :param start: 图的起点
    :param end: 图的出口
    '''
 
    # queue为队列，当队列为空或者当前地点为终点时搜索结束
 
    queue =list()
 
    closed=set()
 
    queue.append(start)
 
    #********* Begin *********#
 
    while(queue!=0):
 
        closed.add(queue[0])
 
        if queue[0]==end:
 
            print(end,end='')
 
            break
 
 
 
        else:
 
            print(queue[0],end='')
 
            for i in mazz[queue[0]]:
 
                if i in closed:
 
                    pass
 
                else:
 
                    queue.append( i )
 
 
 
        queue.remove(queue[0])
 
 
 
 
 
    #********* End *********#

启发式搜索 - 扫地机器人最短路径搜索

 

 

from a_star_utils import Node
 
def A_star(map, mapSize, start, end):
 
    '''
    A*算法，从start走到end
    :param map:地图
    :param mapSize:地图大小，例如[10,10]表示地图长10宽10
    :param start:表示出发地，类型为列表，如[1,2]表示出发地为地图中的第1行第2列的方块
    :param end:表示目的地，类型为列表，如[1,2]表示目的地为地图中的第1行第2列的方块
    :return:从出发地到目的地的路径
    '''
 
    openedList = []
 
    #********* Begin *********#
 
    # 获得出发地方块的信息，并将信息保存为node变量
 
    node = map[start[0]][start[1]]  
 
    #********* End *********#
 
    node.distanceFromOri = 0
 
    node.allDistance = 0
 
    #********* Begin *********#
 
    # 将当前方块存到开启列表中
 
    openedList.append (node)
 
    node.added = True
 
    #********* End *********#
 
    while len(openedList) != 0:
 
        node = openedList.pop(0)
 
        node.closed = True
 
        if node.y == end[0] and node.x == end[1]:
 
            finalListNeedReverse = []
 
            while node != None:
 
                finalListNeedReverse.append(node)
 
                node = node.parent
 
            finalListNeedReverse.reverse()
 
            return finalListNeedReverse
 
        neighboursList = []
 
        y = node.y
 
        x = node.x
 
        parentDistanceFromOri = node.distanceFromOri
 
        for needNodey in (y + 1, y, y - 1):
 
            if needNodey < 0 or needNodey >= mapSize[0]:
 
                continue
 
            for needNodex in (x + 1, x, x - 1):
 
                if needNodex < 0 or needNodex >= mapSize[1]:
 
                    continue
 
                needNode = map[needNodey][needNodex]
 
                if needNode.unable == True or needNode.closed == True or needNode.added == True:
 
                    continue
 
                yOffset = needNodey - y
 
                xOffset = needNodex - x
 
                allOffset = yOffset + xOffset
 
                if allOffset == 1 or allOffset == -1:
 
                    distanceFromOri = parentDistanceFromOri + 1
 
                else:
 
                    distanceFromOri = parentDistanceFromOri + 1.4
 
                if needNode in neighboursList:
 
                    # 若新的G值比老的G值低，则更新成老的G值
 
                    if distanceFromOri < needNode.distanceFromOri:
 
                        needNode.distanceFromOri = distanceFromOri
 
                else:
 
                    needNode.distanceFromOri = distanceFromOri
 
                    neighboursList.append(needNode)
 
        for needNode in neighboursList:
 
            needNode.parent = node
 
            # 更新F值
 
            needNode.allDistance = needNode.distanceFromOri + needNode.distanceFromDes
 
            needNode.added = True
 
            openedList.append(needNode)
 
        openedList.sort(key=lambda x: x.allDistance)
 
    return None

 搜索算法应用 - 四皇后问题

 

 

 

def make(mark):
 
    '''
    标记皇后的位置，例如mark[0] = 2, 表示第1行皇后放在第3列的位置
    :param mark: 皇后的位置信息
    :return: 拼接好的结果
    '''
 
    #初始化数组
 
    r = [['X' for _ in range(len(mark))] for _ in range(len(mark))]
 
    #将每一行中皇后的位置用‘Q’代替
 
    for i in mark:
 
        r[i][mark[i]] = 'Q'
 
    #枚举，将原来散的元素连接成字符串
 
    for k, v in enumerate(r):
 
        r[k] = ''.join(v)
 
    return r
 
def FourQueens(mark, cur, ret):
 
    '''
    深度优先搜索的方式求解四皇后问题
    :param mark:表示皇后的位置信息，例如[0,1,3,2]表示棋盘的第1行第1列，第2行第2列，第3行第4列，第4行第3列放置了皇后。例如[1, None, None, None]表示第1行第2列放置了皇后，其他行没有放置皇后。初始值为[None,None,None,None]
    :param cur:表示当前准备在第几行放置皇后，例如`cur=1`时，表示准备在第`2`行放置皇后。初始值为0
    :param ret:表示存放皇后摆放结果的列表，类型为列表。初始值为[]
    :return:无
    '''
 
    if cur == len(mark):
 
        #********* Begin *********#
 
        # 如果当前行是最后一行，记录一个解，并返回结束此次搜索
 
        ret.append(make(mark))
 
        return
 
        #********* End *********#
 
    #试探处理，将当前行的皇后应该在的位置遍历每一列，如果满足条件，递归调用处理下一行
 
    for i in range(len(mark)):
 
        mark[cur], down = i, True
 
        for j in range(cur):
 
            # 当想在当前位置放皇后会与其他皇后冲突时不放置皇后
 
            if mark[j] == i or abs(i-mark[j]) == cur - j:
 
                down = False
 
                break
 
        if down:
 
            # 准备在下一行找能放置换后的位置
 
            FourQueens(mark, cur+1, ret)

 产生式系统

 

 

 

# 动物识别系统
# 自定义函数，判断有无重复元素
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
       
       
        # ********* End *********#
        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根据所给条件无法判断为何种动物")
 

 框架表示法

 

#encoding=utf8
 
def d():
    #********* Begin *********#
    d = {'name':'蔡徐坤','age':'21','hobby':'rap','sex':'male'}
    #********* End *********#
    return d

逻辑表示法

 

 

#encoding=utf8
 
'''
请将下面代码空缺部分补全
'''
  
def x(p):
    #********* Begin *********#
    if p == '打雷':
        q = '下雨'
    elif p == '动物会飞会下蛋':
        q = '该动物是鸟'
    #********* End *********#
    print(q)

归结反演

 

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(father))
                    else:
                        print('归结式：' + ' ∨ '.join(father) + ' ∨ ' + ' ∨ '.join(mother))
                    #********** End **********#

模糊推理及其应用

 

 
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之间时，执行
    result = (stain - 50) / 50
    returnMDresult = ruleMD(stain)
    # 同时将参数传入给MD，同时比较MD方法传回来的参数和该方法求出的值相比较，求出最后的最适合的预测值
    # ********** Begin **********#
    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 stain >= 0 and stain <= 50:
        result_D = ruleSD(stain)
    else:
        result_D = ruleLD(stain)
 
    if oil >= 0 and oil <= 50:
        result_G = ruleSG(oil)
    else:
        result_G = ruleLG(oil)
        # ********** 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

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.endPoint = endPoint
            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 **********#
        self.startPoint = startPoint
        self.endPoint = endPoint
 
        # ********** End **********#
        # 可行走标记
        self.passTag = passTag
 
    def getMinNode(self):
        """
        获得openlist中F值最小的节点
        :return: Node
        """
 
        # ********** Begin **********#
        nowf = self.openList[0]
        minf=self.openList[0].g +self.openList[0].h
        for i in self.openList:
            if minf > i.g + i.h:
                minf = i.g + i.h
                nowf = i
        return nowf
 
 
 
        # ********** 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 >= self.map2d.w or minF.point.y + offsetY >= self.map2d.h or minF.point.x + offsetX < 0 or minF.point.y + offsetY < 0:
            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)
        currentNode = AStar.Node(currentPoint,self.endPoint)
        if self.pointInCloseList(currentPoint):
            return
        # 设置单位花费
        if offsetX == 0 or offsetY == 0:
            step = 10
        else:
            step = 14
        # 如果不再openList中，就把它加入openlist
        # ********** Begin **********#
        if not self.pointInOpenList(currentPoint):
            # print(currentNode.g)
            currentNode.g = step + minF.g
            # print(currentNode)
            currentNode.father = minF
            self.openList.append(currentNode)
        # ********** 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,1,0)
            self.searchNear(minF,-1,0)
            self.searchNear(minF,0,1)
 
            # ********** 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

盲目搜索之宽度优先搜索算法

 

# -*- coding:utf-8 -*-
class Maze:
    def __init__(self, map, n, m, x, y):
        self.ans = 0            #最短步长结果
        self.map = map          #迷宫地图map[0,n-1][0,m-1]（下标0开始）
        self.n = n              #迷宫地图行数n
        self.m = m              #迷宫地图列数m
        self.x = x              #起点，行坐标（下标0开始）
        self.y = y              #起点，列坐标（下标0开始）
        
class Solution:
    def solveMaze(self, maze):
        """求解迷宫问题
        :type: maze: class Maze #迷宫的数据结构类
        :rtype: maze.ans: int   #返回最短路径长度
        """
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        maze.ans = 0
        que = [(maze.x, maze.y, maze.ans)]              #宽度搜索——队列（列表类型）
        vis = {(maze.x, maze.y):True}                   #访问标记——字典类型
        dir = [[0, -1], [0, 1], [-1, 0], [1, 0]]        #移动方向控制
        while que.__len__()>0:
            node = que[0]                               #出队
            del que[0]
            x = node[0]
            y = node[1]
            ans = node[2]
            if x==0 or x==maze.n-1 or y==0 or y==maze.m-1:  #边界，出迷宫，更新结果
                if maze.ans==0 or maze.ans>ans:
                    maze.ans = ans
            for i in range(4):                              #上下左右移动
                newx = x + dir[i][0]                        #新的行坐标
                newy = y + dir[i][1]                        #新的列坐标
                if 0<=newx and newx<maze.n and 0<=newy and newy<maze.m \
                        and maze.map[newx][newy]==1 and (newx, newy) not in vis:
                    vis[(newx, newy)] = True
                    que.append((newx, newy, ans+1))         #入队
        return maze.ans                                     #返回结果
        #********** End **********#

盲目搜索之深度优先搜索算法

 

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self, n=0):
        self.vis = [[]]             #用于标记是否存在皇后的二维列表（初始值全为0）
        self.ans = 0                #用于存储答案（N皇后方案数，初始值0）
        self.n = n                  #用于存储皇后数量n
    def solveNQueens(self):
        """求解N皇后问题（调用self.DFS函数）
        :rtype: self.ans: int    #返回N皇后放置方案数
        """
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        self.vis = [[0 for j in range(50)] for i in range(3)]
        self.ans = 0
        self.DFS(1, 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+1:
            self.ans += 1
            return
        for i in range(1,n+1,1):
            if self.vis[0][row-i+n]==0 and self.vis[1][i]==0 and self.vis[2][row+i]==0 :
                self.vis[0][row-i+n] = self.vis[1][i] = self.vis[2][row+i] = 1
                self.DFS(row+1, n)
                self.vis[0][row-i+n] = self.vis[1][i] = self.vis[2][row+i] = 0
        #********** End **********#