欢迎来到工友文库! | 帮助中心 工友共享,造福你我!
工友文库
全部分类
  • 行业文库 >
    行业文库
    行业标准 农林牧渔 能源矿业 电力热力 水利环境 材料技术 地理测绘 建筑工程 机械工程 制造加工 交通物流 网络计算 电气机电 信息通讯 汽车行业 航空航天 船舶工程 光电工程 住宿餐饮 财会金融 房地产业 城建规划 装饰装修 家电维修 电商行业 租赁商务 批发零售 居民服务 教育服务 医药卫生 体育行业 公共管理 图书管理 外语翻译 休闲旅游 文艺传媒 其他行业
  • 商业文档 >
    商业文档
    企业计划 工程管理 广告经营 财务报表 物业管理 质控管理 企业文化 绩效管理 商务礼仪 创业孵化 市场营销 经营企划 销售管理 营销创新 资本运营 招商加盟 合同协议 信息管理 励志材料 人事档案 员工关系 薪酬管理 招聘面试 其它文档
  • 办公文书 >
    办公文书
    统计图表 总结报告 演讲致辞 心得体会 述职报告 工作计划 解决方案 调研报告 事务文书 经验事迹 往来文书 规章制度 申请范文 求职简历 活动策划 会议纪要 党建材料 软件教程 其他文书
  • PPT模板库 >
    PPT模板库
    扁平风格 创意新颖 动画效果 动态模板 简约风格 静态模板 环保绿色 卡通风格 立体风格 欧洲风格 手绘风格 创意黑板 相册风格 星空风格 炫酷科技 中国风格 医疗风格 高端商务 工作常用 总结报告 毕业答辩 节日庆典 公益风格 化妆美容 婚礼策划 餐饮美食 培训课件 融资路演 商业策划 英文模板 党政机关 述职竞聘
  • 小学初中 >
    小学初中
    幼儿教育 小学语文 小学数学 小学英语 初中语文 初中数学 初中英语 初中物理 初中化学 初中地理 初中生物 初中政治 初中历史 思想品德 小学竞赛 初中竞赛 其他学科
  • 高中教育 >
    高中教育
    高中语文 高中数学 高中英语 高中物理 高中化学 高中生物 高中地理 高中政治 高中历史 高考资料 高中竞赛 其他学科
  • 高等教育 >
    高等教育
    基础课 艺术类 哲学类 体育类 水利类 测绘类 法学类 历史学 社会学 心理学 教育学 政治学 统计学 房地产 语言文化 生物科学 医药卫生 天文气象 地理科学 环境科学 系统科学 材料科学 机械仪表 图书档案 土建工程 海洋工程 轻工纺织 工程力学 能源动力 光电工程 电力技术 市政工程 财会金融 工商管理 语言文学 广播影视 公安司法 汽车汽修 交通运输 水产加工 植物生产 森林资源 动物科学 食品加工 餐饮旅游 公共事业 新闻传播学 农林业工程 城镇规划管理 水文与水资源 地矿及资源勘查 航空航天与武器 管理科学与工程 农林业经济管理 机电设备及自动化 计算机与信息科学 大学生竞赛资料
  • 执业资格考试 >
    执业资格考试
    财会类考试 建筑类考试 外贸类考试 外语类考试 医药类考试 管理类考试 公务员类考试 司法法律考试 教师资格考试 计算机类考试 公共服务类考试 其他资格证考试
  • 一线采风 >
    一线采风
    一线新闻 事迹宣传 工友作品
  • 教育视频 >
    教育视频
    幼儿教育视频 小学教育视频 初中教育视频 高中教育视频 大学教育视频 C#自学视频教程 软件视频教程 英语视频教学 其他教学视频
  • 换一换
    首页 工友文库 > 资源分类 > PPTX文档下载
     

    人工智能第三章参考资料.pptx

    • 资源ID:20113       资源大小:395.95KB        全文页数:33页
    • 资源格式: PPTX        下载权限:注册会员/VIP会员    下载费用:0金币 【人民币0元】
    下载资源需要0金币 【人民币0元】
    已注册用户请登录:
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,既可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

    人工智能第三章参考资料.pptx

    约束程序研究与进展,,2,内容提要,一.概述 二.研究现状,3,一.概述,约束程序 Constraint Programming,简称CP 是围绕约束这一数学概念建立起来的关于程序设计和问题求解的方法论 是研究基于约束的组合优化问题的推理和计算系统 Wegner和Doyle(ACM),4,Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming the user states the problem, the computer solves it. Eugene C. Freuder,5,标志事件,1963年,Sutherland 研制了Sketchpad系统 1975年,Waltz 提出了相容性技术 1987年,Jaffar和Lassez约束逻辑程序 1995年,召开专题国际会议CP 1996年,具有战略意义的研究方向ACM 1997年,“Constraints ”杂志创刊 ,6,7,研究对象,约束Constraint 约束满足问题 Constraint Satisfaction Problem, CSP 三元组V, D, C. V变量集; D变量论域; C 约束集; 求解一个或所有解 典型问题图着色,N-皇后,8,地图着色问题,变量集V WA, NT, Q, NSW, V, SA, T 论域集D Di {red,green,blue} 约束集C 相邻区域必须颜色不同 如, WA ≠ NT, or WA,NT in {red,green,red,blue,green,red, green,blue,blue,red,blue,green},9,解满足所有约束的一组完全赋值 {WA red, NT green,Q red,NSW green, V red,SA blue,T green},地图着色问题,10,约束图,二元 CSP 每个约束是包含两个变量 约束图点表示变量,弧表示约束,11,研究方向,基本理论 约束求解算法 软约束满足问题 约束程序语言系统 应用方面 成为许多软件系统的核心技术,,12,二.研究现状,约束 求解技术 软约束满足问题 资源,13,CSPs分类,离散变量 有限论域finite domains 布尔论域,整数区间; 无限论域infinite domains 整数论域,字符串论域; 连续变量 时间 实数区间,14,约束,一元约束每个约束只包含一个变量, 例如, SA ≠ green 二元约束约束包含两个变量, 例如, SA ≠ WA 多元约束约束包含3个或者更多的变量, 例如,字谜游戏约束,15,字谜游戏,变量 F T U W R O X1 X2 X3 论域 {0,1,2,3,4,5,6,7,8,9} 约束 Alldiff F,T,U,W,R,O O O R 10 X1 X1 W W U 10 X2 X2 T T O 10 X3 X3 F, T ≠ 0, F ≠ 0,16,约束的表示,定义在变量集合 X1, , Xk上 的约束CX1,X2, , Xk 可看成是一个函数 CX1,X2, , Xk DX1  DXk  {0,1} 外延表示 随机产生问题 内涵表示 表达式,函数,过程 实际问题 全局约束,17,外延表示(1),CX,Y,Z with DX DY DZ {1, 2, 3},18,外延表示(2),19,外延表示(3),20,,X ≤ Y ≤ Z,内涵表示,21,全局约束(global constraint),Alldifferent Alldiff F,T,U,W,R,O Global Constraint Catalog06.9.30 http//www.emn.fr/xnfo/sdemasse/gccat/titlepage.html Nicolas Beldiceanu,22,求解技术,系统搜索(回溯) 相容性技术 约束传播+搜索 回顾 展望 启发式策略 不完备的搜索 对称消除 Symmetry breaking 变量对称,值对称 计算智能(粒子群、遗传算法等),23,思想 反复为变量选择一个与当前部分解相容的值来把部分解扩展到完全解 顺序的实例化变量 如果当前部分解不满足某个约束,就回溯到最近的变量实例化 优点 是完备的方法 比GT方法效率高 缺点 发生“颠簸”现象,顺序回溯(BacktrackingBT),24,25,BT的改进,Dependency-directed Backtracking Backjumping1BJ Graph-based BackjumpingGBB Conflict-directed BackjumpingCBJ Dynamic Backtracking-DB backchecking and backmarking,让BT变得更“聪明”,从失败中获得经验 ,回溯到更高的层次,,,,,,,jump here,1.Rina Dechter and Daniel Frost.Backjump-based backtracking for constraint satisfaction problems. Artificial Intelligence, Volume 136, Issue 2, April 2002, ,147-188,26,相容性技术,1975年Waltz 提出的 优点 有效的压缩了问题的搜索空间 缺点 是不完备的,通常不单独使用 分类 节点相容性 弧相容性 AC-3, AC-4, Directional AC, 边界相容性 AC-3 只检查可能由值的删除受到影响的约束,27,弧相容性(Arc Consistency-AC ),1 2,1 2,1 2,,,,,,,,,1 2,1 2,1 2,,,,,,,,X,Y,Z,X,Y,Z,Problem X{1,2}, Y{1,2}, Z{1,2} X Y, X  Z, Y Z,Martin Cooper and Thomas Schiex.Arc consistency for soft constraints . Artificial Intelligence, Volume 154, Issues 1-2, April 2004, Pages 199-227,28,AC不完备,某个变量论域为空 无解 所有变量论域基数为1 解 Problem X{1,2}, Y{1,2}, Z{1,2} X  Y, X  Z, Y  Z,1 2,1 2,1 2,,,,,,,,,,X,Y,Z,29,约束传播+搜索,look back,30,BTMAC,31,启发式策略,变量选择启发式 最先失败原则(First Fail Principle-FFP) 选择受约束最强的变量进行实例化 值选择启发式 N皇后问题, middle-out值选择 和具体问题紧密相关 学习 Counting Solutions,32,不完备的搜索,Bounded Backtrack Search-BBS Depth-bounded Backtrack SearchDBS Iterative Broadening-IB Credit Search CS,33,

    注意事项

    本文(人工智能第三章参考资料.pptx)为本站会员(小旋风)主动上传,工友文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知工友文库(发送邮件至gydoc@qq.com或直接QQ联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    copyright@ 2019-2022 工友文库网站版权所有
    经营许可证编号:鲁ICP备19032292号-1


    1
    收起
    展开