微信服务号

微信订阅号

2025-4-4- 7
Home > Archive>Volume 9, Issue 8, 1998 >598-600
PDF HTML XML Export Cite reminder
Local Search Methods for Constraint Solving in First-Order Logic
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [1]
    • |
  • Related
    • | | |
  • Comments
    Abstract:

    In this paper, the author discusses constraint satisfaction problems in the framework of first-order logic. Local search methods for satisfying first-order formulas are studied, and compared with satisfiability procedures in the propositional logic. Experimental results on the Queens problem and the Hamiltanian circuit problem show that the framework is suitable for dealing with quite large problem instances.

    Reference
    1　 Mackworth A. The logic of constraint satisfaction. Artificial Intelligence, 1992,58(1):3～20 2　 Gu J. Efficient local search for very large-scale satisfiability problems. SIGART Bulletin, 1992,3(1):8～12 3　 Selman B et al. A new method for solving hard satisfiability problems. In: Proceedings of the 10th National Conference on Artificial Intelligence(AAAI-92). Menlo Park, CA: AAAI Press, 1992. 440～446 4　 李未,黄文奇.一种求解合取范式可满足性问题的数学物理方法.中国科学（A辑）,1995,38(1):116～128 (Li Wei, Huang Wen-qi. A mathematic-physical approach to the satisfiability problem. Science in China, 1995,38(1):116～128) 5　 刘涛,李国杰.求解SAT问题的分级重排搜索算法.软件学报,1996,7(4):201～210 (Liu Tao, Li Guo-jie. Multi-stage search rearrangement algorithm for solving SAT problem. Journal of Software, 1996,7(4):201～210) 6　 Selman B et al. Noise strategies for improving local search. In: Proceedings of the 12th National Conference on Artificial Intelligence(AAAI-94). 1994. 337～343 7　 Nadel B. Tree search and arc consistency in constraint satisfaction algorithms. In: Kanal L, Kumar V eds. Search in Artificial Intelligence. New York: Springer-Verlag, 1988. 287～342 8　 Zhang J, Zhang H. SEM: a system for enumerating models. In: Mellish C S ed. Proceedings of the 14th International Joint Conference on Artificial Intelligence. San Mateo, CA: Morgan Kanfmann Publishers, 1995. 298～303 9　 Zhang J, Zhang H. Combining local search and backtracking techniques for constraint satisfaction. In: Proceedings of the 13th National Conference on Artificial Intelligence and the 8th Innovative Applications of Artificial Intelligence Conference. Cambridge, MA: MIT Press, 1996. 369～374
    Related
    Cited by
Get Citation

张 健.一阶逻辑中约束求解的局部搜索法*.软件学报,1998,9(8):598-600

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 31,1997
  • Revised:July 30,1997
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063