ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Solving QBF with Heuristic Small World Optimization Search Algorithm

Journal: The International Arab Journal of Information Technology (Vol.12, No. 4)

Publication Date:

Authors : ; ;

Page : 370-378

Keywords : QBF; SW; search algorithm; optimization algorithm.;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

In this paper, we use gaifman graph to describe the topological structure of the Quantified Boolean Formulae (QBF), we mainly study the formula family with the Small World (SW) network topology. We analyze the traditional Davis,Putnam, Logemann and Loveland (DPLL) solving algorithm for QBF, then we improve the DPLL algorithm and propose the solving algorithm framework based on Small World Optimization Search (SWOS) algorithm, we apply this SWOS algorithm to determine the order of the DPLL branch variable. Our result proves that SWOS algorithm has a certain degree of effectiveness to improve the solving efficiency. It is valuable as an incomplete solution algorithm for search-based solver.

Last modified: 2019-11-17 15:49:49