...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>WSEAS Transactions on Computers >Constraint Satisfaction Problem Using Modified Branch and Bound Algorithm
【24h】

Constraint Satisfaction Problem Using Modified Branch and Bound Algorithm

机译：改进的分支定界算法的约束满足问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A constraint satisfaction problem (CSP) involves assigning possible values to a set of variables without defying any constraints. There are various techniques available to solve or give partial solution to CSP. This paper presents a modification of branch and bound algorithm, which is used to solve a constraint satisfaction problem in map colouring problem. There are two constraints involved which are only three colours are allowed to be used and adjacent regions in the map must not be of the same colour. The modified branch and bound algorithm uses back jumping when it encounters a dead-end in the search. Static variable ordering was also applied to aid the searching process. The modified branch and bound algorithm shows a better result in terms of the number of nodes instantiated and the reduced number of backtracking at dead ends. The result illustrated that the modified branch and bound algorithm with the use of variable ordering technique is better if compared to backjumping. Thus, it is concluded that the modified branch and bound algorithm would improve constraint satisfaction problem.
机译：约束满足问题（CSP）涉及在不违反任何约束的情况下将可能的值分配给一组变量。有多种技术可以解决CSP或提供部分解决方案。本文提出了一种分支定界算法的改进方法，用于解决地图着色问题中的约束满足问题。涉及两个约束，仅允许使用三种颜色，并且地图中的相邻区域不得具有相同的颜色。修改后的分支定界算法在搜索中遇到死角时使用回跳。静态变量排序也被应用于辅助搜索过程。改进的分支定界算法在实例化节点数量和减少死角回溯数量方面显示出更好的结果。结果表明，与后跳相比，使用变量排序技术的改进分支定界算法更好。因此，可以得出结论，改进的分支定界算法将改善约束满足问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号