出版社: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.