网站建设包六个,许昌市网站建设找汉狮,达州北京网站建设,音乐网站设计外国【人工智能】—约束传播、弧约束、问题结果与问题分解、局部搜索CSP约束传播弧约束弧相容算法AC-3问题结构化简约束图-树结构CSP问题的局部搜索CSP的迭代算法举例#xff1a;4-Queens加速#xff1a;模拟退火法加速#xff1a;最小最大优化(约束加权法)小结约束传播
前向检…
【人工智能】—约束传播、弧约束、问题结果与问题分解、局部搜索CSP约束传播弧约束弧相容算法AC-3问题结构化简约束图-树结构CSP问题的局部搜索CSP的迭代算法举例4-Queens加速模拟退火法加速最小最大优化(约束加权法)小结约束传播
前向检验将信息从已分配的变量传播到未分配的变量但不能为所有失败情景提供早期检测NT和SA不能都是蓝色的约束传播在局部重复强制执行约束
弧约束 能使每个弧相容的最简单形式 X→Y是可相容的当 对于X的每个值xY都存在不与之冲突的取值y 如果X丢失了一个值则需要重新检查X的邻居 弧相容比前向检验更早检测到可能失败的情景 弧相容可以作为预处理运行也可以在每次分配后运行
弧相容算法AC-3 时间复杂度O(n2d3)O(n^2d^3)O(n2d3)
问题结构 T和其它地区是独立的子问题独立性可以简单地通过在约束图中寻找连通子图来确定。每个连通子图对应于一个子问题CSP 假设每个子问题有n个变量中的c个。最坏情况下的解决方案成本是n/c⋅dcn/c·d^cn/c⋅dc对n是线性的 例如n80d2,c20n80d2,c20n80d2,c20 280402^{80}4028040亿年1000万个节点/秒4⋅2200.44·2^{20}0.44⋅2200.4秒1000万个节点/秒 任何一个树状结构的CSP问题可以在变量个数的线性时间内求解 如果约束图没有循环CSP可以在O(n⋅d2)O(n·d^2)O(n⋅d2)时间内解决。 与一般CSP相比最坏情况下的时间是O(dn)O(d^n)O(dn)
化简约束图-树结构 CSP问题的局部搜索
CSP的迭代算法
爬坡法、模拟退火法通常对 完整 状态进行工作即所有变量均被分配为了适用于CSP 允许有未满足的约束条件的状态操作者重新分配变量值 变量选择随机选择任何有冲突的变量通过最小冲突进行价值选择 启发式 选择会造成与其它变量的冲突最小的值在爬山法中h(n)被违反的约束总数
举例4-Queens
状态 4个皇后在4列44256个状态行动在列中移动皇后目标测试没有冲突评价hn冲突次数 最小冲突启发式的性能 给定随机初始状态可以在几乎恒定的时间内解决任意n的高概率问题如n10,000,000的n-queens。对于任何随机生成的CSP来说除了在一个狭窄的比率范围内似乎也是如此。 在3-SAT问题中也能取得很好的性能
加速模拟退火法
思路通过允许一些 坏 的动作来逃避局部最大值但要逐渐减少其频率
加速最小最大优化(约束加权法) 小结
