DPLL算法和访问节点数

Question

我正在实施 DPLL 算法来计算已访问节点的数量。我设法实现了不计算访问节点的 DPLL，但我想不出任何解决计数问题的方法。主要问题是，当算法找到令人满意的估值和 returns True 时，递归从递归开始的那一刻起开始滚动和 returns 计数器。在任何命令式语言中，我只会使用全局变量并在调用函数后立即递增它，但在 Haskell.

中并非如此

我粘贴在这里的代码并不代表我尝试解决计数问题，这只是我没有它的解决方案。我尝试使用诸如 (True,Int) 之类的元组，但从递归开始的那一刻起，它总是 return 整数值。

这是我的实现，其中 (Node -> Variable) 是一个启发式函数，Sentence 是 CNF 中要满足的子句列表，[Variable] 是未分配的文字列表，Model 只是一个真值评估。

dpll' :: (Node -> Variable) -> Sentence -> [Variable] -> Model -> Bool
dpll' heurFun sentence vars model
  | satisfiesSentence model sentence  = True
  | falsifiesSentence model sentence  = False
  | otherwise         = applyRecursion
    where
      applyRecursion
        | pureSymbol /= Nothing = recurOnPureSymbol
        | unitSymbol /= Nothing = recurOnUnitSymbol
        | otherwise             = recurUsingHeuristicFunction
          where
            pureSymbol  = findPureSymbol vars sentence model
            unitSymbol  = findUnitClause sentence model
            heurVar = heurFun (sentence,(vars,model))
            recurOnPureSymbol =
              dpll' heurFun sentence (vars \ [getVar pureSymbol]) ((formAssignment pureSymbol):model)
            recurOnUnitSymbol =
              dpll' heurFun sentence (vars \ [getVar unitSymbol]) ((formAssignment unitSymbol):model)
            recurUsingHeuristicFunction = case vars of
              (v:vs) ->     (dpll' heurFun sentence (vars \ [heurVar]) ((AS (heurVar,True)):model)
                        ||   dpll' heurFun sentence (vars \ [heurVar]) ((AS (heurVar,False)):model))
              []     ->     False

对于如何计算已访问节点的任何建议，我将不胜感激。谢谢。

编辑：

我唯一可以使用的库是 System.Random、Data.Maybe 和 Data.List。

编辑：

我尝试实现的一个可能的解决方案是使用元组 (Bool,Int) 作为 DPPL 函数的 return 值。代码如下：

dpll'' :: (Node -> Variable) -> Sentence -> [Variable] -> Model -> Int -> (Bool,Int)
dpll'' heurFun sentence vars model counter
  | satisfiesSentence model sentence  = (True,counter)
  | falsifiesSentence model sentence  = (False,counter)
  | otherwise         = applyRecursion
  where
    applyRecursion
      | pureSymbol /= Nothing = recurOnPureSymbol
      | unitSymbol /= Nothing = recurOnUnitSymbol
      | otherwise             = recurUsingHeuristicFunction
      where
        pureSymbol  = findPureSymbol vars sentence model
        unitSymbol  = findUnitClause sentence model
        heurVar = heurFun (sentence,(vars,model))
        recurOnPureSymbol =
          dpll'' heurFun sentence (vars \ [getVar pureSymbol]) ((formAssignment pureSymbol):model) (counter + 1)
        recurOnUnitSymbol =
          dpll'' heurFun sentence (vars \ [getVar unitSymbol]) ((formAssignment unitSymbol):model) (counter + 1)
        recurUsingHeuristicFunction = case vars of
          (v:vs)    ->    ((fst $ dpll'' heurFun sentence (vars \ [heurVar]) ((AS (heurVar,True)):model) (counter + 1))
                      ||  (fst $ dpll'' heurFun sentence (vars \ [heurVar]) ((AS (heurVar,False)):model) (counter + 1)),counter)
          []        -> (False,counter)

这种方法的基本思想是在每次递归调用时递增计数器。但是，这种方法的问题是我不知道如何从 OR 语句中的递归调用中检索计数器。我什至不确定这在 Haskell.

中是否可行

Answer 1

基本上，您在命令式语言中描述的解决方案可以通过传递一个计数变量来建模，在您 return 它时将变量添加到结果（递归的底部达到可满足的赋值)，即对于函数 a -> b，您将创建一个新函数 a -> Int -> (b, Int)。 Int 参数是计数器的当前状态，结果由计数器的更新状态丰富。

这可以使用 state monad. A very nice tutorial on haskell in general and state monad is here. Basically the transformation of a -> b to a -> Int -> (b, Int) can be seen as transformation of a -> b into a -> State Int b by simply given a nicer name to the function Int -> (b, Int). There is a very nice blog 进一步优雅地重新表达，它以一种非常易于访问的方式解释了这些漂亮的抽象来自何处。

import Control.Monad.Trans.StateT

type Count = Int

dpllM :: (Node -> Variable) -> Sentence -> [Variable] -> Model -> State Count Bool
dpllM heurFun sentence vars model | ... = do
    -- do your thing
    modify (+1)
    -- do your thing

dpll' :: (Node -> Variable) -> Sentence -> [Variable] -> Model -> Bool
dpll' heurFun sentence vars model = runState (dpllM heurFun sentence vars model) 0

也许你想要

f :: A -> Int -> (Bool, Int)
f a c =
    let a' = ...
        a'' = ...
        (b', c') = f a' c in f a'' c'

Answer 2

您可以使用 case 或类似方法从递归调用中检索计数器。

recurUsingHeuristicFunction = case vars of
    v:vs -> case dpll'' heurFun sentence (vars \ [heurVar]) (AS (heurVar,True):model) (counter + 1) of
        (result, counter') -> case dpll'' heurFun sentence (vars \ [heurVar]) (AS (heurVar,False):model) counter' of
            (result', counter'') -> (result || result', counter'')
    []   -> (False,counter)

这是 State monad 的手动实现。但是，我不清楚您为什么要经过柜台。就 return 吧。然后它是更简单的 Writer monad。这个助手的代码看起来像这样：

recurUsingHeuristicFunction = case vars of
    v:vs -> case dpll'' heurFun sentence (vars \ [heurVar]) (AS (heurVar,True):model) of
        (result, counter) -> case dpll'' heurFun sentence (vars \ [heurVar]) (AS (heurVar,False):model) of
            (result', counter') -> (result || result', counter + counter' + 1)
    []   -> (False,0)

其他结果将是相似的——returning 0 而不是 counter 和 1 而不是 counter+1——以及调用函数会更简单，只需少一个参数即可正确设置。

DPLL算法和访问节点数

DPLL algorithm and number of visited nodes

algorithm

haskell

recursion

artificial-intelligence

dpll