项目名称: 约束满足问题的结构特征和算法分析

项目编号: No.60973033

项目类型: 面上项目

立项/批准年度: 2010

项目学科: 自动化技术、计算机技术

项目作者: 刘田

作者单位: 北京大学

项目金额: 29万元

中文摘要: 在约束满足问题中要求为一组变量赋值来满足给定的一组约束条件,这类问题覆盖了计算机科学、人工智能、运筹学等很多领域的重要问题。值域可变的约束满足问题可以更好地描述实际问题,近年来逐渐引起关注,但过去在固定值域条件下取得的结论往往不能直接应用。随机约束满足问题通过一个随机过程产生随机实例,通过调整随机过程的控制参数,可以观察到实例性质的相变现象,包括从有解到无解的可满足性相变、在可满足性临界点附近算法行为的相变等,但目前还没有建立起可满足性相变与难解性之间的确切关联。本项目研究值域可变的随机约束满足性问题的结构特征和算法分析,包括结构参数的取值和解空间的结构变化、各种求解算法的相变点、在算法模型和证明系统下的指数下界、近似算法和精确算法研究等,目标是比较其与固定值域的约束满足问题的差别,刻画值域可变的随机约束满足问题的难解性,建立起相变现象与难解性之间的确切联系,为实际应用打下坚实的理论基础。

中文关键词: 约束满足;RB模型;相变现象;结构分解;算法分析

英文摘要:

英文关键词: Constraint Satisfaction;Model RB;Phase Transition;Structural Decomposition;Algorithm Analysis

成为VIP会员查看完整内容
0

相关内容

专知会员服务
111+阅读 · 2021年9月22日
逆优化: 理论与应用
专知会员服务
35+阅读 · 2021年9月13日
算法分析导论, 593页pdf
专知会员服务
144+阅读 · 2021年8月30日
专知会员服务
21+阅读 · 2021年6月26日
专知会员服务
39+阅读 · 2021年6月2日
【2021新书】分布式优化,博弈和学习算法,227页pdf
专知会员服务
212+阅读 · 2021年5月25日
专知会员服务
22+阅读 · 2021年4月21日
【经典书】数据结构与算法,770页pdf
专知会员服务
133+阅读 · 2021年4月15日
专知会员服务
69+阅读 · 2020年12月7日
专知会员服务
41+阅读 · 2020年7月29日
一纵一横,搭建完整数据分析体系
人人都是产品经理
0+阅读 · 2022年1月30日
定位理论5大坑,你踩过几个?
人人都是产品经理
1+阅读 · 2022年1月27日
正则化方法小结
极市平台
2+阅读 · 2021年11月24日
【经典书】数据结构与算法,770页pdf
专知
1+阅读 · 2021年4月15日
约束进化算法及其应用研究综述
专知
0+阅读 · 2021年4月12日
【深度】行人检测算法
GAN生成式对抗网络
29+阅读 · 2018年6月3日
RCNN算法分析
统计学习与视觉计算组
10+阅读 · 2018年1月12日
基于LDA的主题模型实践(二 )MCMC--吉布斯采样
机器学习深度学习实战原创交流
24+阅读 · 2015年9月17日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年4月20日
Arxiv
0+阅读 · 2022年4月19日
Arxiv
24+阅读 · 2021年6月25日
小贴士
相关VIP内容
专知会员服务
111+阅读 · 2021年9月22日
逆优化: 理论与应用
专知会员服务
35+阅读 · 2021年9月13日
算法分析导论, 593页pdf
专知会员服务
144+阅读 · 2021年8月30日
专知会员服务
21+阅读 · 2021年6月26日
专知会员服务
39+阅读 · 2021年6月2日
【2021新书】分布式优化,博弈和学习算法,227页pdf
专知会员服务
212+阅读 · 2021年5月25日
专知会员服务
22+阅读 · 2021年4月21日
【经典书】数据结构与算法,770页pdf
专知会员服务
133+阅读 · 2021年4月15日
专知会员服务
69+阅读 · 2020年12月7日
专知会员服务
41+阅读 · 2020年7月29日
相关资讯
一纵一横,搭建完整数据分析体系
人人都是产品经理
0+阅读 · 2022年1月30日
定位理论5大坑,你踩过几个?
人人都是产品经理
1+阅读 · 2022年1月27日
正则化方法小结
极市平台
2+阅读 · 2021年11月24日
【经典书】数据结构与算法,770页pdf
专知
1+阅读 · 2021年4月15日
约束进化算法及其应用研究综述
专知
0+阅读 · 2021年4月12日
【深度】行人检测算法
GAN生成式对抗网络
29+阅读 · 2018年6月3日
RCNN算法分析
统计学习与视觉计算组
10+阅读 · 2018年1月12日
基于LDA的主题模型实践(二 )MCMC--吉布斯采样
机器学习深度学习实战原创交流
24+阅读 · 2015年9月17日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
微信扫码咨询专知VIP会员