- 1、本文档共19页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
人工智能 实 验 报 告 4
授课时间: 2011-2012 学年 第 1 学期 实验学时: 3
专业班级: 计算机09-1 学生姓名No. 王丹0936040
实验题目: 代价树的广度优先搜索—交通图
实验目的:
1.掌握代价树的广度优先搜索方法。
2.通过运用所学代价树的广度优先搜索知识来解答交通图的最短路径问题。
实验语言环境:
c++与c语言
实验要求及内容:
如图是5城市之间交通路线图,A城市是出发地,E城市是目的地,两城市间的交通费用(代价)如图中数字所示,求从A到E的最小费用路线。 解:采用代价树的广度优先搜索(1)把初始节点S0放入OPEN,令g(S0)=0。
(2)检查OPEN是否为空,是,无解,退出。
(3)把OPEN第一个节点(并记该节点为n )取出放入CLOSED。
(4)考察节点n是否为目标节点,是,得解,退出。
(5)考察节点n是否可扩展,否,则转2)。
(6)扩展节点n ,将其子节点放入OPEN,并为每一个子节点都配一个指向父节点的指针计算各子节点的代价,并按各节点的代价进行排序(从小到大),然后转2)。
↘按各节点的代价进行排序(从小到大)2.根据交通图,画出代价图 代价图3.开始搜索 oepn表存放刚刚生成的节点。 closed表存放将要扩展的节点或已经扩展过的节点。 open表结构: [代价]|[节点]|[父节点] closed表结构: [序号]|[节点]|[父节点] 1) 把A放入 open表
open表:0| A | 0?????? Closed表: 空 2) 把A从open表放入closed表 open表: 空???????????? closed表: 1 | A | 0 3) 扩展A,得C1,B1,放入open表 C1的代价:3 B1的代价:4 Open表: 3 | C1 | A? 4 | B1 | A closed表: 1 | A | 04) 把C1从open表放到closed表 Open表: 4 | B1 | A? closed表: 1 | A | 0 2 | C1 | A C1不是目标节点,于是继续扩展 5) 把C1扩展得到 D1,放入open表 D1的代价:3+2=5 B1的代价:4
open表: 4 | B1 | A 5 | D1 | C1 closed表: 1 | A? | 0 2 | C1 | A6) 把B1从open放入closed表
open表: 5 | D1 | C1?? closed表: 1 | A? | 0 2 | C1 | A 3 | B1 | AB1不是目标节点,于是继续扩展 7) 扩展B1得D2,E1,放入Open表 D2的代价:4+4=8 E1的代价:4+5=9 open表: 5 | D1 | C1? 8 | D2 | B1???????????? 9 | E1 | B1???????????? closed表: 1 | A | 0 2 | C1 | A 3 | B1 | A 8) 把D1从open表放入closed表
open表: 8 | D2 | B1? 9 | E1 | B1???????????? closed表: 1 | A | 0 2 | C1 | A 3 | B1 | A 4 | D1 | C1D1不是目标节点,于是继续扩展 9) 把D1扩展得到E2,B2,放入open表 E2的代价:3+2+3=8 B2的代价:3+2+4=9 D2的代价:8 E1的代价:9 open表: 8 | E2 | D1? 8 | D2 | B1???????????? 9 | B2 | D1???????????? 9 | E1 | B1????????????? closed表: 1 | A | 0 2 | C1 | A 3 | B1 | A 4 | D1 | C1 10) 把E2从open表放入closed表
open表: 8 | D2 | B1??????????? 9 | B2 | D1???????????? 9 | E1 | B1???????????? closed表: 1 | A | 0 2 | C1 | A 3 | B1 | A 4 | D1 | C1 5 | E2 | D1????则搜索路径 A - C1 - D1 -E2 即:A - C - D - E 分析总结:
通过本次交通图的代价树的广度优
您可能关注的文档
- 城市便捷连锁酒店集团公司财务手册.doc
- 承装(修、试)电力设施许可证申请表与填报说明(新).doc
- 城市规划相关知识笔记.doc
- 城投公司运作模式研究(报告)文档.doc
- 城厢区华亭镇拆迁项目旧房拆除工程(重新招标).doc
- 齿轮轴的加工工艺与编程---毕业设计说明书.doc
- 出国旅行留学必备英语经典口语.doc
- 初级矿井维修电工职业技能鉴定考试卷(ABC)及答案.doc
- 初级中药学专业知识习题1.doc
- 初三毕业班第二学期家长会教师发言稿.doc
- 2024年江西省寻乌县九上数学开学复习检测模拟试题【含答案】.doc
- 2024年江西省省宜春市袁州区数学九上开学学业水平测试模拟试题【含答案】.doc
- 《GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语》.pdf
- 中国国家标准 GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语.pdf
- GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- 《GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构》.pdf
- 中国国家标准 GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 中国国家标准 GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 《GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南》.pdf
文档评论(0)