实验一项目：图搜索技术
一、实验目的
1．加深学生对图搜索技术的理解。
2．掌握图搜索基本编程方法。
3．能初步运用图搜索技术解决一些实际应用问题。
二、预习要求
1．复习广度优先搜索算法。
2．复习深度优先搜索算法。
3．设计初步的搜索算法。
三、实验内容
修道士和野人问题如下：
有三个传教士和三个野人一起来到河边准备渡河，河边有一条空船，且传教士和野人都会划船，但每次最多可供两人乘渡。河的任何一岸以及船上一旦出现野人人数超过传教士人数，野人就会把传教士吃掉。为完全地渡河，传教士应如何规划渡河方案？
四、实验要求
能够搜索出最好的解题路径，把传教士和野人一起运送到河对岸
五、实验步骤及实验结果
#最终为了对 问题进行回溯
#每次的算符有 （1，0） （0，1） （1，1） （2，0） （0，2）
#5中基本算符 与 船的位置相结合 产生 10中算符
#搜索 过程列表用来保存搜索过的 结果 statue_list=[[yr,cjs,chuan,self_id,father_id] ]
#其中self_id 可以省略， 它 对应于数组下标
#概念 队列 不需要存储
#待搜索状态队列，先进先出， 每次将当前节点pop[0]， 将当前节点的衍生节点 append,如果衍生过的节点已经被搜索过，则忽略不计，
当整个队列为空时，说明搜索过程结束
#概念队列可以采用两个下标 来进行实现，一个是数组当前的长度， 一个是 指向 弹出的 游标， 从0开始，向后 作为拓展节点
class yerenquestion: def __init__(self,yeren,chuanjiaoshi): self.chuan=-1 self.self_id=0 father_id=-1 #下一步会被拓展的 状态下标 self.tuozhan_point=0 self.statue=[yeren,chuanjiaoshi,self.chuan,self.self_id,father_id] #算符 self.suanfu=[[1,0],[0,1],[2,0],[0,2],[1,1]] #操作描述 self.miaoshu_caozuo=['1个野人','1个传教士','2个野人','2个传教士','1个野人1个传教士',] self.miaoshu_list=[] self.sousuo_list=[] self.sousuo_list.append(self.statue) self.tuozhan() self.caozuo_index=0 def tuozhan(self): if self.tuozhan_point>self.self_id: print("搜索结束") print(self.sousuo_list) exit(10) if self.tuozhan_point<=self.self_id: #从当前状态 拓展 节点 self.product_statue() self.tuozhan_point+=1 self.tuozhan() #根据当前搜索节点产生新的 节点 def product_statue(self): #当前状态 now_=self.sousuo_list[self.tuozhan_point] print('\n\n\n') print('当前状态',now_) self.chuan=now_[2] #可以产生的状态 self.caozuo_index=0 for item in self.suanfu: print("当前执行的算符",item) father_de_id=self.tuozhan_point new_statue=[now_[0]+self.chuan*item[0], now_[1]+self.chuan*item[1], -1*self.chuan, self.self_id, father_de_id] print("产生的新状态",new_statue) if self.check_statue(new_statue)==True: self.sousuo_list.append(new_statue) self.self_id+=1 self.miaoshu_list.append(self.miaoshu_caozuo[self.caozuo_index]) self.caozuo_index+=1 def check_statue(self,new_statue): #检查1 检查当前节点是否安全 野人在两岸的数量不能比传教士多， 除非传教士 为空 # 起点不安全，传教士不为 0 ，野人比传教士多 if new_statue[1]!=0 and new_statue[0]>new_statue[1]: return False #船对岸不安全 if (3-new_statue[1])!=0 and (3-new_statue[0])>(3-new_statue[1]): return False #两岸人数不能为 负 if new_statue[0]>3 or new_statue[0]<0 or new_statue[1]<0 or new_statue[1]>3: return False #保证节点未拓展过 flag=0 代表未拓展过 # flag=0 for item in self.sousuo_list: if new_statue[:3] == item[:3]: return False if new_statue[:3]==[0,0,1]: print("搜索成功") self.sousuo_list.append(new_statue) self.miaoshu_list.append(self.miaoshu_caozuo[self.caozuo_index]) self.self_id+=1 print(self.sousuo_list) self.show_process(self.self_id) exit(9) return True #展示搜索过程 def show_process(self,self_id_): if self_id_==-1: print("开始运输") print("") if self_id_!=-1: self.show_process(self.sousuo_list[self_id_][4]) if self_id_!=0: fangxiang = "运过去 " if self.sousuo_list[self_id_][2]==-1: fangxiang="运过来 " print(fangxiang,self.miaoshu_list[self_id_-1]) print(self.sousuo_list[self_id_]) #求解 yerenquestion(3,3)
[3, 3, -1, 0, -1] 运过去 2个野人 [1, 3, 1, 1, 0] 运过来 1个野人 [2, 3, -1, 3, 2] 运过去 2个野人 [0, 3, 1, 4, 4] 运过来 1个野人 [1, 3, -1, 5, 5] 运过去 2个传教士 [1, 1, 1, 6, 6] 运过来 1个野人1个传教士 [2, 2, -1, 7, 7] 运过去 2个传教士 [2, 0, 1, 8, 8] 运过来 1个野人 [3, 0, -1, 9, 9] 运过去 2个野人 [1, 0, 1, 10, 10] 运过来 1个野人 [2, 0, -1, 11, 11] 运过去 2个野人 [0, 0, 1, 13, 12]
六、心得体会
问题说明
对问题进行细致思考， 可以发现 (yr,cjs,chuan) 就可以描述问题的整个状态
其中 yr 代表野人在起点 数量， cjs 代表传教士 在起点的数量 ，船的位置， -1 船在起点
所以 问题的 初始状态描述为 (3,3,-1)
问题的终点 描述为 (0,0,1)
最终为了对 问题进行回溯
每次的算符有 （1，0） （0，1） （1，1） （2，0） （0，2）
5中基本算符 与 船的位置相结合 产生 10中算符
搜索 过程列表用来保存搜索过的 结果 statue_list=[[yr,cjs,chuan,self_id,father_id] ]
其中self_id 可以省略， 它 对应于数组下标
概念 队列 不需要存储
待搜索状态队列，先进先出， 每次将当前节点pop[0]， 将当前节点的衍生节点 append,如果衍生过的节点已经被搜索过，则忽略不计，
当整个队列为空时，说明搜索过程结束
概念队列可以采用两个下标 来进行实现，一个是数组当前的长度， 一个是 指向 弹出的 游标， 从0开始，向后 作为拓展节点
实验二项目：A*算法
一、实验目的
熟悉和掌握启发式搜索的定义、估价函数和算法过程，理解求解流程和搜索顺序。
2．使学生掌握A算法的编程方法，
3．并能利用A算法求解N数码难题。
二、预习要求
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。
三、实验内容
1、以8数码或15数码为例，用A算法编写一个求解数码问题的程序。
2、画出A算法求解框图。
四、实验要求
根据情况可以选择实现基本功能或者附加功能
１、基本功能
可以演示问题的求解过程。
２、附加功能
可选择实现下述一种或几种功能：
（１）开始演示。进入N数码难题演示程序，可选8数码或者15数码，点击“选择数码”按钮确定。
（２）点击“缺省棋局”，会产生一个固定的初始节点。点击“随机生成”，会产生任意排列的初始节点。
（３）算法执行。点击“连续执行”则程序自动搜索求解，并演示每一步结果；点击“单步运行”则每次执行一步求解流程。“运行速度”可自由调节。
（４）观察运行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示“15数码难题”，点击“选择数码”确定选择；运行15数码难题演示实例。
（５）算法流程的任一时刻的相关状态,以算法流程高亮、open表、close表、节点静态图、当前扩展节点移动图等5种形式在按钮上方同步显示,便于深入学习理解A*算法。
五、实验步骤及实验结果
start.py
from shiyan_2.uiClass1 import mainwindow1 from PyQt5.QtWidgets import QApplication,QMainWindow import sys def start_ui(): app=QApplication(sys.argv) window1=mainwindow1() window1.show() app.exec() start_ui()
uiClass1.py
# # import shiyan_2.fifteennumbergame as fnumgame # from PyQt5 import QtCore, QtGui, QtWidgets from PyQt5.QtWidgets import QApplication, QMainWindow from shiyan_2.fifteennumbergame import Ui_MainWindow class mainwindow1(QMainWindow,Ui_MainWindow): def __init__(self): super(mainwindow1,self).__init__() self.setupUi(self) # class MainWindow5(QMainWindow, w5.Ui_MainWindow): # def __init__(self): # super(MainWindow5, self).__init__() # self.setupUi(self)
qiuejie_question.py
import copy ### 传入一个 value_list ## 形如 [6, 5, 3, 1, 4, 7, 8, 2, 0] ##两个测试值 value_list9=[6, 5, 3, 1, 4, 7, 8, 2, 0] result_list9=[1,2,3,8,0,4,7,6,5] value_list16=[0, 14, 15, 1, 12, 3, 13, 11, 10, 8, 9, 2, 5, 7, 4, 6] result_list16=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0] # result_list16=list(range(1,17)) # result_list16[-1]=0 # print(result_list16) ## 交换规则， 根据当前 空白 也就是 0 在value_list 中的 位置可以确定 它 下一步会被交换的位置 next_pos_list9=[[1,3], [0,2,4], [1,5], [0,4,6], [1,3,5,7], [2,4,8], [3,7], [6,4,8], [5,7]] next_pos_list16=[[1,4], [0,2,5], [1,3,6], [2,7], [0,5,8], [1,4,6,9], [2,5,7,10], [3,6,11], [4,9,12], [5,8,10,13], [6,9,11,14], [7,10,15], [8,13], [9,12,14], [10,13,15], [11,14]] ### # 用来 保存 搜索过的 状态， 当没有被搜索过 时 压入 这个 列表， 当某个状态，被搜索过，则忽略， # 这个 状态 列表上 还应该 有一个指针， 指向， 当前搜索的 状态， # 每一次 指针向后移， 并且压入 会被搜索的 新状态 ， # 当 搜索 指针到达 队尾还没有 求解问题，代表 问题 在这种 解法下 暂时无解 now_search=0 # searched_status[0]= 状态的 集合 #[0]自身状态 [1]父节点 [2]是否被搜索过 [3]预估代价 [4]当前代价 searched_status=[[],[],[],[],[]] #用来记录 每个 被搜索状态的 父亲状态， father_status=[] # 得到传入的当前状态 now_value_list='' ## 搜索的总代价 等于 g(x) + h(x) result_list=[] #h(x) , g(x) info_list=[[],[]] def product_process(value_list): n=searched_status[0].index(value_list) while searched_status[1][n]!= -1: result_list.append(searched_status[0][n]) info_list[0].append(searched_status[3][n]) info_list[1].append(searched_status[4][n]) n=searched_status[1][n] result_list.append(searched_status[0][n]) info_list[0].append(searched_status[3][n]) info_list[1].append(searched_status[4][n]) ##### # 求解每一步的 g(x) def get_offset(value_list): sum_offset=0 len_=len(value_list) result_list='' if len_==9: result_list=result_list9 if len_==16: result_list=result_list16 for i in range(len(value_list)): if value_list[i]!=result_list[i]: sum_offset+=10 if sum_offset!=0: #如果没有达到终点，就进行 搜索 print(value_list) print('距离是{0}'.format(sum_offset)) print(len(searched_status[0])) return sum_offset #### 根据求得的 h(x) #### 根据搜索 过的路径 得到 g(x) def sum_daijia(): #初始代价为0 gx=0 pass # 添加searched_status=[] # [0]自身状态 [1]父节点 [2]是否被搜索过 [3]预估代价 [4]当前代价 def append_searched_list(value_list,father_index,is_searched,hwight,gwight): addlist=[value_list,father_index,is_searched,hwight,gwight] for i in range(len(searched_status)): searched_status[i].append(addlist[i]) def expand_searched_list(): while True: #如果 valuest 有返回值 说明 当前可以进行拓展， 否则会跑出一个异常 valuest_index=get_valuest_index() now_value_list = searched_status[0][valuest_index] #得到 0在 节点中的 位置 zero_index=get_zero_index(now_value_list) # 说明这个节点 被拓展过 了 searched_status[2][valuest_index]=1 ##### len_=len(now_value_list) stop_step=0 next_pos_list='' if len_ == 9: next_pos_list = next_pos_list9 stop_step=40 if len_ == 16: next_pos_list = next_pos_list16 stop_step = 100 #根据 下一步 可以 到达 的 状态 进行搜索 for i in range(len(next_pos_list[zero_index])): new_list=copy.deepcopy(now_value_list) #交换 可以到达的节点 与 0 的位置 new_list[zero_index],new_list[next_pos_list[zero_index][i]]=new_list[next_pos_list[zero_index][i]],new_list[zero_index] #如果这个状态 还没有出现过 if new_list not in searched_status[0]: hwight = get_offset(new_list) gwight = searched_status[4][valuest_index]+1 if gwight > stop_step: print('这个初始图没有解') return '这个初始图没有解',None,searched_status raise Exception('这个初始图没有解') father_index = valuest_index append_searched_list(new_list,father_index,0,hwight,gwight) if hwight == 0: print('游戏结束') a = get_valuest_index() print(searched_status[4][a]) product_process(new_list) print(result_list) return result_list,info_list,searched_status raise Exception('游戏结束') # return now_value_list #expand_searched_list() #找到 最需要 被 搜索的 节点 def get_valuest_index(): # 设定搜索的 代价 上限 threshold_value = 1000000 need_expand_index = -1 for i in range(len(searched_status[0])): # [0]自身状态 [1]父节点 [2]是否被搜索过 [3]预估代价 [4]当前代价 #当前节点没有被搜索过 if searched_status[2][i]==0: #当前节点搜索 代价比较小 ，当循环 一遍 之后 找到的就是 代价最小的 节点 if (searched_status[3][i]+searched_status[4][i])<threshold_value: threshold_value=searched_status[3][i]+searched_status[4][i] need_expand_index=i if need_expand_index != -1: #说明有 尚未拓展的节点， 那么对他进行拓展 print('当前最小代价',(searched_status[3][need_expand_index]+searched_status[4][need_expand_index])) return need_expand_index else: print(searched_status[0]) print(len(searched_status[0])) raise Exception('没有需要被拓展的节点了') def get_zero_index(value_list): zero_index='' for i in range(len(value_list)): zero_index= (i if value_list[i]==0 else zero_index) if zero_index == '' : raise Exception('找不到零所在的位置') else : return zero_index def goto_next_statue(): pass def get_random_list(n): import random if type(n) == int: list1 = list(range(n)) random.shuffle(list1) print(list1) return list1 else: raise Exception('get_random_list 需要传入一个整数') def start_question(value_list): # [0]自身状态 [1]父节点 [2]是否被搜索过 [3]预估代价 [4]当前代价 global searched_status searched_status = [[], [], [], [], []] # 用来记录 每个 被搜索状态的 父亲状态， global father_status father_status = [] global result_list result_list=[] # value_list=get_random_list(9) # value_list = get_random_list(16) now_value_list=value_list wight=get_offset(value_list) # 将当前状态 添加到 被搜索 列表 #[0]自身状态 [1]父节点 [2]是否被搜索过 [3]预估代价 [4]当前代价 append_searched_list(now_value_list,-1,0,wight,0) #添加完第一个状态，开始 搜索 与 拓展的 递归 # expand_searched_list() # contanst_expand() #连续拓展 节点 # def contanst_expand(): # while True: # expand_searched_list() # # start_question(get_random_list(16)) # # start_question([3, 7, 6, 0, 2, 4, 1, 5, 8]) # expand_searched_list() # get_offset(value_list16) #1222
六、心得体会
用来 保存 搜索过的 状态， 当没有被搜索过 时 压入 这个 列表， 当某个状态，被搜索过，则忽略，
这个 状态 列表上 还应该 有一个指针， 指向， 当前搜索的 状态，
每一次 指针向后移， 并且压入 会被搜索的 新状态 ，
当 搜索 指针到达 队尾还没有 求解问题，代表 问题 在这种 解法下 暂时无解
open表中用来保存还没有搜所过的节点，
Close 表中用来记录搜索过的节点
并且记录下来每个节点的 父节点，用来回溯最后的求解路径
实验三项目：神经网络
一、实验目的
加深学生对神经网络的理解。
2．使学生掌握BP神经网络。
3．使学生能够运用神经网络解决一些实际问题。
二、预习要求
神经网络，是模拟生物神经网络进行信息处理的一种数学模型。它以对大脑的生理研究成果为基础，其目的在于模拟大脑的某些机理与机制，实现一些特定的功能。目前，人工神经网络已应用于很多领域。
BP网络是一种多层前馈型神经网络，其神经元的传递是S型函数，输出量为0到1之间的连续量，它可以实现从输入到输出的任意非线性映射。由于权值的调整采用反向传播学习算法，因此也常称其为BP网络。BP网络主要用于函数逼近、模式识别、分类等领域。
三、实验内容
设计合适的BP神经网络，解决函数逼近问题。要求根据问题选择合适的BP神经网络结构，对非线性函数—正弦函数进行逼近，并分析神经网络不同参数的影响。
四、实验要求
要求能够对正弦函数进行逼近。
五、实验步骤及实验结果
网络结构：
输入层
第一层layers.Dense(32, activation=‘relu’)
第二层layers.Dense(32, activation=‘relu’)
第三层layers.Dense(32, activation=‘relu’)
输出层layers.Dense(1,))
import matplotlib.pyplot as plt#约定俗成的写法plt #首先定义两个函数（正弦&余弦） import numpy as np import tensorflow as tf from tensorflow.keras import layers model = tf.keras.Sequential() model.add(layers.Dense(32, activation='relu')) model.add(layers.Dense(32, activation='relu')) model.add(layers.Dense(32, activation='relu')) model.add(layers.Dense(1,)) # # model.compile(optimizer=tf.keras.optimizers.Adam(0.5), # loss='categorical_crossentropy', # metrics=['accuracy']) optimizer = tf.keras.optimizers.RMSprop(0.001) model.compile(loss='mse', optimizer=optimizer, metrics=['mae', 'mse']) X=np.linspace(-np.pi,np.pi,256,endpoint=True)#-π to+π的256个值 print("x的值",X.shape) S=np.sin(X) x1=[] s1=[] for index in range(len(X)): x1.append([X[index]]) s1.append([S[index]]) x1=np.array(x1) s1=np.array(s1) model.fit(x1,s1,epochs=0, batch_size=32) before_t=[] for tempx in X: print(tempx) tempx=model.predict([tempx]) tempx=tempx[0] before_t.append(tempx) model.fit(x1,s1,epochs=100, batch_size=32) after_t=[] for tempx in X: print(tempx) tempx=model.predict([tempx]) tempx=tempx[0] after_t.append(tempx) print(tempx) plt.plot(X,S,label='sin(x)') plt.plot(X,before_t,label="before_train") plt.plot(X,after_t,label="after_train",color="yellow") #在ipython的交互环境中需要这句话才能显示出来 plt.legend() plt.show()
六、心得体会
当神经元个数足够时，神经网络可以用来拟合任意的函数，
也可以用来对离散函数进行，连续化处理
也可以用来对函数进行 求导，积分 函数进行直接拟合
1、编写一个描述亲属关系的逻辑程序，然后再给予出一些事实数据，建立一个小型演绎数据库。
提示：可以以父亲和母亲为基本关系（作为基本谓词），再由此来描述祖父、祖母、兄弟、姐妹以及其他所属关系。
代码
import kanren import sympy from kanren import run, eq, membero, var, conde from kanren import Relation, facts parent = Relation() facts(parent, ("Homer","Bart"),("lmk","Bart"),("Homer","Lisa"),("Abe","Homer")) x = var() res1=run(0, x, parent(x, "Bart")) print(res1) father=Relation() mather=Relation() facts(father,("f1","f2"),("f2","f3"),("f2","f31"),("f3","f4"),("f4","f5")) facts(mather,("m1","m2"),("m2","m3"),("m3","m4")) someone=var() someone_son=var() #爷爷 def grandfather(grandson): someone = var() someone_son = var() return run(0,someone,father(someone,someone_son),father(someone_son,grandson)) #奶奶 def grandmather(grandson): someone = var() someone_son = var() return run(0,someone,mather(someone,someone_son),mather(someone_son,grandson)) # grandfather1=grandfather("f3") #兄弟 def borther(one_person): one_father = var() one_mather =var() one_brother = var() return run(0,(one_person,one_brother),father(one_father,one_person),father(one_father,one_brother),) one_grandson=input("你要找谁的爷爷\n") grandfather1=grandfather(one_grandson) print(grandfather1) one_person=input("你要找谁的兄弟\n") borther1=borther(one_person) print(borther1)
2、编写一个路径查询程序，使其能输出图中所有路径。
提示：程序中的事实描述了下面的有向图，规则是图中两节点间通路的定义。
import pyDatalog pyDatalog.create_terms('X,Y,Z,link,can_reach') # there is a link between node 1 and node 2 +link('a', 'b') +link('a', 'c') +link('c', 'd') +link('b', 'd') +link('b', 'e') +link('d', 'e') # x y之间是否可达? can_reach(X, Y) <= link(X, Y) # direct link # 递归查找 x，y 之间是否可达 can_reach(X, Y) <= link(X, Z) & can_reach(Z, Y) & (X != Y) while True: start_node=input('请输入出发的地点') print(can_reach(start_node, Y))
3、一个雇主在发出招聘广告之后，收到了大量的应聘申请。为了从中筛选出不量的候选人，该雇主采用下列判据：申请者必须会打字、开车，并且住在伦敦。
（a）用规则表述这个雇主的选择准则。
（b）用事实描述下列申请者的情况：
史密斯住在剑桥，会开车但不会打字。
布朗住在伦敦，会开车也会打字。
简住在格拉斯哥，不会开车但会打字。
埃文斯住在伦敦，会开车也会打字。
格林住在卢顿，会开车也会打字。（c）要求运行结果提供一个候选人名单。
import pyDatalog.pyDatalog as pyDatalog pyDatalog.create_terms('X,live,drive,type_word,can_be_hire') #现在又 几个 应聘者 # sms ,bl , jian ,aws ,gl +live('sms','jianqiao') +live('bl','lundun') +live('jian','silage') +live('aws','lundun') +live('gl','ludun') +drive('sms') +drive('bl') +drive('aws') +drive('gl') +type_word('bl') +type_word('jian') +type_word('aws') +type_word('gl') #定义能够被雇佣的 员工 can_be_hire(X) <= live(X,'lundun') & drive(X) & type_word(X) print(can_be_hire(X))
输出结果
