3

ここに問題があります。

2つのステートメント p=>qとがある場合q=>r、それはまた、を意味しp=>rます。

一連のステートメントが与えられた場合、与えられたステートメントが与えられたステートメントから結論付けられるtrueかどうかを見つける必要があります。false

例：
与えられたステートメントp=>q, p=>r, q=>s

  • 入力がの場合、p=>s出力を取得する必要がありますtrue

  • 入力がの場合、p=>t出力を取得する必要がありますCannot be concluded

  • 入力がの場合、p=> ~p出力を取得する必要がありますfalse

ここで私の質問は、これを実装するための最良のデータ構造と、使用するアルゴリズムは何かということです。

ありがとう。

4

3 に答える 3

1

ですから、あなたが何をしようとしているのか、まだ完全にはわかりません。反対票を投じられる危険を冒して、私はこれをそこに追い出し、人々がどう思うかを見るつもりです.

グラフを作成することから始めるかもしれません。各エンティティ (p、q など) には独自のノードがあります。「暗示」とは、2 つのノード間に線を引くことを意味します。したがって、任意の入力は、グラフをトラバースする方法を見つけることができるかどうかを確認するだけの問題です。したがって、例では、a => b、b => c、グラフには 3 つのノードがあり、a は b に接続されています。 cに接続されています。a と c の間にパスが存在するという事実は、a が c を含意することを意味します。

私はこのアイデアをこれ以上精査していませんが、興味深い見通しのようです。特に、グラフ理論はクールで、多くの人が興味を持っています (つまり、Facebook の幹部)。そして、Python にはグラフを分析するための優れたモジュールがあります。(C++ にも同じことが当てはまると思います。また、Gephi を使用していつでも手動で仕様を指定できます: https://gephi.org/ )

于 2013-02-14T03:31:48.590 に答える
1

問題の単純さを考えると、単純なmap. vectorはるかに高速なルックアップに存在することに対する主な利点。

// For "p":  { name: "p", positive: "true" }
// For "~q": { name: "q", positive: "false" }
struct Predicate {
    std::string _name;
    bool _positive;
};

using PredicateSetType = std::unordered_set<Predicate>;
using PredicateMapType = std::unordered_map<Predicate, PredicateSetType>;

マップは次のように使用しp => qます。{ "q", true }{ "p", true }

これは実際には有向グラフをエンコードするため、ステートメントの証明に関しては、グラフを探索する一般的な方法が適用されることに注意してください。

于 2013-02-14T08:00:14.237 に答える
1

多くの人がこの問題を何年も研究してきました。必要なのはSAT Solverです。ChaffまたはzChaffまたはその他の一般的に使用される SAT ソルバーを検索します。(p->q && q->r) -> (p -> r) のような句を取り、それらを否定して、それが満足できるかどうかを判断します。否定が充足可能でない場合は、常に真である定理があります。元の節が充足可能であり、節の否定が充足可能である場合、「結論を下すことはできません」を返す必要があります。元の条項が満足できない場合は、何かが間違っています。

これは実際によく研究されている問題です。優れたアルゴリズムはありますが、処理できる命題変数の数には厳しい制限があります。SAT は NP 困難問題の中心にあります。効率的なアルゴリズムが知られていない問題のクラス。

于 2013-02-14T04:15:20.960 に答える