DPLL算法与访问节点数
我正在实现DPLL算法，它计算访问节点的数量。我成功地实现了不计算访问节点的DPLL，但我想不出任何解决方案来解决计数问题。主要问题是，当算法找到满意的赋值并返回True时，从递归开始的那一刻起，递归就卷起来并返回计数器。在任何命令式语言中，只要调用函数，我就会使用全局变量并增加它，但在Haskell中并非如此。
我在这里粘贴的代码并不代表我试图解决计数问题，它只是我的解决方案，没有它。我尝试使用元组，例如(True，Int)，但从递归开始的那一刻起，它总是返回整数值。
这是我的实现，其中(节点->变量)是一个启发式函数，句子是CNF中要满足的子句列表，变量是未赋值的文字列表，而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函数的返回值。代码看起来像：
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是否可行。
回答 2
Stack Overflow用户
发布于 2017-03-13 21:56:39
您可以使用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的手动实现。但是，我不清楚你为什么要经过柜台。把它还回去。那么，取而代之的是更简单的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)其他结果也是相似的--返回0而不是counter和1，而不是counter+1 --对函数的调用将更简单，只需少一个关于正确设置的参数。
Stack Overflow用户
发布于 2017-03-13 20:13:58
基本上，您用命令式语言描述的解决方案可以通过传递一个计数变量来建模，在返回变量时将变量添加到结果中(达到可满足赋值的递归的底部)，即对于一个函数a -> b，您将创建一个新的函数a -> Int -> (b, Int)。Int参数是计数器的当前状态，计数器的更新状态丰富了结果。
这可以进一步使用州单优雅地重新表达.关于haskell和state的一个非常好的教程是这里。从根本上说，a -> b到a -> Int -> (b, Int)的转换可以看作是将a -> b转换为a -> State Int b，只需给函数Int -> (b, Int)取一个更好的名称。有一个非常好的博客，它以一种非常容易访问的方式解释了这些好的抽象来自何处。
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'https://stackoverflow.com/questions/42772275
复制相似问题
腾讯云开发者
