东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2003, Vol. 24 ›› Issue (12): 1169-1172.

• 论著 • 上一篇    下一篇

一类约束满足问题及其算法

蒋本铁;毕世飞   

  1. 东北大学计算中心;东北大学信息科学与工程学院 辽宁沈阳　110004
  • 收稿日期:2013-06-24 修回日期:2013-06-24 出版日期:2003-12-15 发布日期:2013-06-24
  • 基金资助:
    辽宁省自然科学基金资助项目(9910701001)

  • Received:2013-06-24 Revised:2013-06-24 Online:2003-12-15 Published:2013-06-24

RichHTML

0

PDF (PC)

1106

摘要： 针对具有解析约束形式、同一变量多赋值的约束满足问题,提出了一种新的约束满足问题定义·通过一种特殊约束满足问题的研究提出一套建立在这个定义基础之上的概念和三种算法:整数规划法、不等式组法和直接求解不定方程法,详细研究了其中的第三种算法,并给出了最坏情况下的时间复杂度,从而能够比较清晰地描述一类约束满足问题的一般分析过程,揭示了约束满足问题同经典的整数规划、数论和整数环论的联系·

关键词: 约束满足问题(CSP), 不定方程, 整数规划, 偏移方程, 时间复杂度