首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Weights Stagnation in Dynamic Local Search for SAT
  • 本地全文:下载
  • 作者:Abdelraouf Ishtaiwi
  • 期刊名称:Computer Science & Information Technology
  • 电子版ISSN:2231-5403
  • 出版年度:2016
  • 卷号:6
  • 期号:6
  • 页码:79-90
  • DOI:10.5121/csit.2016.60607
  • 出版社:Academy & Industry Research Collaboration Center (AIRCC)
  • 摘要:Since 1991, tries were made to enhance the stochastic local search techniques (SLS). Someresearchers turned their focus on studying the structure of the propositional satisfiabilityproblems (SAT) to better understand their complexity in order to come up with betteralgorithms. Other researchers focused in investigating new ways to develop heuristics that alterthe search space based on some information gathered prior to or during the search process.Thus, many heuristics, enhancements and developments were introduced to improve SLStechniques performance during the last three decades. As a result a group of heuristics wereintroduced namely Dynamic Local Search (DLS) that could outperform the systematic searchtechniques. Interestingly, a common characteristic of DLS heuristics is that they all depend onthe use of weights during searching for satisfiable formulas.In our study we experimentally investigated the weights behaviors and movements duringsearching for satisfiability using DLS techniques, for simplicity, DDFW DLS heuristic is chosen.As a results of our studies we discovered that while solving hard SAT problems such as blocksworld and graph coloring problems, weights stagnation occur in many areas within the searchspace. We conclude that weights stagnation occurrence is highly related to the level of theproblem density, complexity and connectivity.
国家哲学社会科学文献中心版权所有