短絡回路をブーリアン論理に並べ替える方法は？

Question

私は実行に長い時間がかかる関数がたくさんあり、それぞれTrue/Falseを返すという問題があります。全体のTrue/Falseスコアを得るために、すべての関数に巨大なブール式を適用します。現在、私のコードは関数ベースではないので、すべての関数が実行され、大きなブール式が適用されます。私はすでにそれらを関数にすることで、関数式呼び出しを防ぐために短期間に実行される部分式が可能になることを理解しました。私が今必要とするのは、最小限の呼び出し数を持つように式を並べ替える方法です。次のコードを考えると

（恐ろしいのコード例をあなたのアイデアを取得する必要があります）：あなたが印刷されたq個のR Sを参照してください。この場合

def q(): 
    print "q" 
    return False 

def r(): 
    print "r" 
    return False 

def s(): 
    print "s" 
    return False 

def a(): 
    print "a" 
    return False 

def b(): 
    print "b" 
    return False 

def c(): 
    print "c" 
    return False 


def d(): 
    print "d" 
    return False 

def i(): 
    print "i" 
    return False 

def j(): 
    print "j" 
    return False 


(q() or r() or s()) and (a() and b() and c() and (i() or j())) 

。すべてがFalseなので、短絡します。しかし、この場合は、最初にbまたはcを評価する必要があります。そのうちの1つがFalseの場合、式全体がFalseになるからです。最善の順序をハードコーディングできないように、最後の式がユーザーによって生成されたとします。私は欠けている非常に簡単なアルゴリズムがあると思っています。

他の二つの事柄：

1）私は、このような「いない」として、他のロジックを許可した場合はどう？ 2）実行するのにかかる時間に基づいて各機能にスコアを割り当てて、それを計算することはできますか？

Answer 1

あなたの計算式はCNFです（計算上の複雑さには非常に良いので、最上位の括弧は不要です）。これは本当に簡単な公式です。あなたは今のところnotを持っていないので、複雑なアルゴリズムを探す必要があるかどうかは分かりません。しかし、あなたは確かに何らかのヒューリスティックを試すことができます（できるだけリテラルが少ない句の評価から始めて、できるだけ早く失敗するように...）。問題は、リテラルが1つしかない句から始めても、関数を計算する方が大きい節を計算するよりも高価になる可能性があるので、サイズに応じて並べ替えるのではなく、計算の複雑さに応じて並べ替えるのが理にかなっています）。

notを組み込んだ瞬間、便利なものがいくつか見つかります。特にそれらをCNFに変換する方法や、また、resolutionからのアイデアはあなたにとって役に立つかもしれません。

Answer 2

式を最適化するには、各関数のコストと短絡する確率の2つを知る必要があります。いったんこれを取得すると、各部分式を評価して同じ用語を生成することができます。パラメータの順序のすべての並べ替えを試行すると、どの配置が最もコストが低いかが示されます。

def evaluate_or(argument_evaluation_list): 
    total_cost = 0.0 
    probability_of_reaching = 1.0 
    for cost, probability_of_true in argument_evaluation_list: 
     total_cost += probability_of_reaching * cost 
     probability_of_reaching *= 1.0 - probability_of_true 
    return total_cost, 1.0 - probability_of_reaching 

def evaluate_and(argument_evaluation_list): 
    total_cost = 0.0 
    probability_of_reaching = 1.0 
    for cost, probability_of_true in argument_evaluation_list: 
     total_cost += probability_of_reaching * cost 
     probability_of_reaching *= probability_of_true 
    return total_cost, probability_of_reaching 

def evaluate_not(argument_evaluation) 
    cost, probability_of_true = argument_evaluation 
    return cost, 1.0 - probability_of_true