algorithm - 複雑な組み合わせアルゴリズム

Question

したがって、ウェンディーズはサンドイッチに 256 の組み合わせがあると宣伝しています。

一般化されたアプローチにより、各選択のさまざまな状態を掛け合わせることができ、より複雑な組み合わせが可能になります。この場合、Wendy のアイテムは含めるか除外することしかできません。ただし、一部のサンドイッチには、2 種類のマスタードのオプションがある場合があります (コストを節約するため、両方ではありません)。

これらはかなり簡単です。オプションの数を掛け合わせると、Wendy's の場合は次のようになります。

2*2*2*2*2*2*2*2 = 256

上記のようにマスタードの選択を多様化すると、次のようになります。

2*2*3*2*2*2*2*2 = 384

さらに先に進むのは難しいようです。

ごまを別のアイテムにする場合は、パンのアイテムが必要です。饅頭を入れるとごまのみ、饅頭なしでも食べられますが、饅頭なしではごまは食べられません。これは、3 つの状態 (なし、種ありのパン、種なしのバン) を持つ 1 つのパンアイテムに単純化できますが、それができない状況もあります。

たとえば、Dell のコンピュータコンフィギュレータでは、特定の組み合わせが許可されていません (スロットがすべて埋まっている、アイテムを同じシステムに入れると互換性がないなど)。

アイテムが競合する可能性がある、非常に複雑なシステムを扱う場合の適切な組み合わせアプローチは何ですか?
製品/組み合わせ/アイテムごとにコードを作成して競合をキャッチすることなく、そのような情報を保存するための優れた一般化されたアプローチは何ですか?
システムが複雑な競合する組み合わせに対処する必要がある場合、「システム/サンドイッチを構成する方法は X 通りあります」と言う簡単な方法はありますか?

score 5 · Accepted Answer

カリフォルニアにある HP のハイエンドサーバー製造施設では、これを実現するためにカスタムルールベースのシステムを長年使用していました。

工場の現場でのビルドサイクルプロセスには、ビルド担当者とテスターにリリースする前に、オーダーがビルド可能であることを確認するための事前チェックが含まれていました。

これらのチェックの 1 つは、注文の部品表 (BOM) がプロセスエンジニアによって指定された規則のリストに準拠しているかどうかを判断しました。たとえば、顧客がプロセッサを注文する場合、十分な数の DC コンバータ部品も注文したことを確認します。または、一定量のメモリー DIMM を注文した場合は、追加容量に対応するドーターボードも注文したことを確認してください。

コンパイラのバックグラウンドを持つコンピューターサイエンスの学生は、コードを認識していたでしょう。コードは BOM を解析し、タイプ別にグループ化されたパーツのスレッド化されたツリーを内部的に生成しました。次に、ルールを内部ツリーに適用して、順序が一致しているかどうかを判断しました。

副作用として、システムは、各システムを構築する際に労働者が引き上げた各注文の構築ドキュメントも生成しました。また、ビルド後のバーンインプロセスで予想されるテスト結果も生成されるため、テストベイはそれらを参照して、すべてが正しくビルドされたかどうかを判断できます。

score 4 · Accepted Answer

Adam Davis：私が正しく理解していれば、ユーザーが互換性のある部品を購入するのを支援するショッピングカートに実際に使用できるある種のシステムを開発するつもりです。

問題の定義

これはグラフの問題です（すべてではありません）。他のアイテムと互換性のあるアイテムがあります。たとえば、はPentium i3-2020任意Socket 1155 Motherboardの、と互換性があります。これは2xDDR3（速度= 1066）と互換性があり、、、などが必要です。Asrock H61M-VS Socket 1155 MotherboardPCI-Express GPUDDR3 PC RAM{Total(size) <= 16GB}4 pin ATX 12V power

（a）バスケット内の各アイテムがバスケット内の別のアイテムによって満たされているかどうかを識別できる必要があります（つまり、RAMカードに互換性のあるマザーボードがあります）。（b）最も適切なアイテムを割り当てます（つまり、USBハブをマザーボードUSBに割り当てます）。マザーボードがUSBポートを使い果たした場合は、ポートとプリンタをUSBハブに接続します。逆にすると、ハブを乾いたままにするのではなく）、（c）満足のいくコンポーネントのリストを見つける機能をユーザーに提供します。おそらく、USBハブは拡張機能であるため、常に優先される可能性があります（ただし、注意してください）。

必要なデータ構造

単純な分類システムが必要になります。つまり、H61M-VSは-マザーボード、H61M-VSは- DDR3メモリスロット（各スロットの速度プロパティ付き）です。

分類と構成の次に、要件を特定する必要があります。これは非常に簡単です。これで、単純な分類により、単純なSQLクエリで分類に適合するすべてのアイテムを見つけることができます。

満足のいくバスケットのテスト

バスケットをテストするには、構成を作成して、どのアイテムがどのアイテムと一致するかを特定する必要があります（つまり、マザーボードのDDR3スロットは4GB Ramモジュールと一致し、SATAHDDケーブルはマザーボードのSATAポートとPSUのSATA電源ケーブルに接続します。PSUの4ピンATXは12V電源ケーブルがマザーボードに接続されます。

最も簡単なのは、別の満足のいくアイテムが存在するかどうかを確認することです。

デルのコンピュータコンフィギュレータ

プロセッサなど、1つのアイテムから始めます。プロセッサにはマザーボードとファンが必要なので、マザーボードを選択できます（プロセッサファンをに追加しますlist_of_things_to_be_satisfied）。これは、で保持されているアイテムがなくなるまで続きlist_of_things_to_be_satisfiedます。もちろん、これはすべてあなたの正確な要件と、ユーザーのためにどのような問題を解決するかを知っているかどうかに依存します。

score 3 · Accepted Answer

これをコードで実装するには多くの方法がありますが、私の謙虚な意見では、何かをプログラミングする前に問題を解決するための最良の方法は次のとおりです。

部品と製品の定義 (プリコード)

すべての「パーツ」を定義するときは、パーツの階層と分類を識別することが最も重要です。これは、一部のルールが固有の部分(例: 「ブラウンマスタードのみ」)、一部のカテゴリ(例: 「すべてのマスタード」)、タイプごと(例: 「すべての調味料」)などに限定される場合があるためです。

ルールセットの構築 (事前コード)

固有の部品、カテゴリ、タイプ、完成品ごとにルールセット (前提条件、除外など) を定義します。

ばかげているように聞こえるかもしれませんが、ルールが適切な範囲で定義されるように、多くの注意を払う必要があります。たとえば、完成品が次の場合Burger:

固有のアイテムルール - 「キノコはブルーチーズを選択した場合のみ入手可能」 prerequisite
定型ルール - 「マスタードは 1 つだけ選択できます」 exclusive
タイプルール - 「ピクルスはペッパーと相性が悪い」 exclusive

「パーツ」の一意/カテゴリ/タイプのルールに多くの時間を費やした後、多くの設計者は、パーツに競合がない場合でも、完成品にのみ適用されるルールを見落とします。

商品ルール - 「調味料は最大5個まで」 condition
商品ルール - 「バーガーにはバンズが必要」 prerequisite

このルールのグラフは、すぐに非常に複雑になる可能性があります。

データ構造を構築するための提案 (コード)

構造が階層と分類に対応していることを確認してください。たとえば、「ブラウンマスタード」と「ディジョンマスタード」は個別のオブジェクトであり、どちらもマスタードであり、調味料でもあります。

これを機能させるには、継承モデリング (基本クラス) とオブジェクト属性 (CategoryプロパティやHasCondimentsフラグなど) の適切な組み合わせを慎重に選択してください。
各階層オブジェクトレベルでプライベートフィールドを作成します。RuleSets
フラグとコレクションのパブリックプロパティを作成します。HasConflictsRuleViolations
部品が製品に追加されると、すべてのレベルのルール (部品自体、カテゴリ、タイプ、および製品) をチェックします。これは、製品から呼び出すことができるパブリック関数を介して行います。または、より良い内部化のために、パーツ自体にイベントハンドラーを作成できます。

アルゴリズムを書く (コード)

これは私が嫌いなところです。それはあなたの質問の範囲を超えているので良いことです。

このステップの秘訣は、ツリー/グラフを上に移動するルールをコードに実装する方法です。たとえば、特定の部分にその範囲外の別の部分の問題がある場合、または別の部分が問題になっているときに検証を実行する方法などです。追加した？私の考え：

各部分にパブリック関数の方法論を使用します。製品のCurrentPartsコレクションに渡します。
Product オブジェクトで、とを処理するハンドラーを定義しOnPartAdded、コレクションをOnPartRemoved列挙してCurrentParts各パーツの検証関数を呼び出すようにします。

必要最小限のプロトタイプの例

interface IProduct
{
    void AddPart();
    void OnAddPart();
}
// base class for products
public class Product() : IProduct
{
     // private or no setter. write functions as you like to add/remove parts.
    public ICollection<Part> CurrentParts { get; };
    // Add part function adds to collection and triggers a handler.
    public void AddPart(Part p)
    {
        CurrentParts.Add(p);
        OnAddParts();
    }
    // handler for adding a part should trigger part validations
    public void OnAddPart()
    {
        // validate part-scope rules, you'll want to return some message/exception
        foreach(var part in CurrentParts) {
            part.ValidateRules(CurrentParts); 
        }
        ValidateRules(); // validate Product-scope rules.
    }
}

interface IProduct
{
    // "object" should be replaced with whatever way you implement your rules
    void object RuleSet; 
    void ValidateRules(ICollection<Part> otherParts);
}
// base class for parts
public class Part : IPart
{
    public object RuleSet; // see note in interface.

    public ValidateRules(ICollection<Part> otherParts)
    {
        // insert your algorithms here for validating 
        // the product parts against this part's rule set.
    }
}

素敵できれい。

score 2 · Accepted Answer

プログラマーとして、私は次のことを行います（ただし、実際にこれを行う必要はありませんでした）。

組み合わせの総数を計算します。通常は、質問に記載されているオプションを単純に乗算するだけで十分です。これらすべての組み合わせを保存する必要はありません。
次に、合計を例外で割ります。例外は、ルールのセットとして保存でき、どの組み合わせが許可されていないかを効果的に示します。
許容される組み合わせの総数を計算するには、例外ルールのセット全体を実行する必要があります。

すべての組み合わせをセットと考えると、例外はそのセットのメンバーを削除するだけです。ただし、セットのサイズは非常に簡単に計算できるため、例外だけを除いて、セット全体を保存する必要はありません。

score 2 · Accepted Answer

この種の問題を解決する際に使用できる構造の 1 つとして、「関数の生成」が思い浮かびます。必要なものに応じて、いくつかの異なる生成関数があることに注意してください。

北米では、車のナンバープレートは、ナンバープレートを取得する場所に応じて、ナンバープレートの長さである 6 または 7 の各場所に 36 の可能な値があるすべての順列を数えることにおいて、興味深い組み合わせ問題になる可能性があります。ただし、一部の組み合わせには、悪口や人種差別的な言葉が含まれているために失格となり、問題が少し難しくなります. たとえば、私が思うに、ナンバープレートでは許可されていない、少なくとも 2 つの異なるスペルを含む悪名高い N ワードがあります。

もう 1 つの例は、複数回繰り返されるいくつかの項目を含む特定のアルファベットを使用して、単語のさまざまな順序をすべて決定することです。たとえば、「文字」という単語の文字をさまざまな方法で配置したい場合、それは 6 つだけではありません。これは、"abcdef" の場合に当てはまります。これは、2 組の文字があり、計算が少し難しくなるためです。

L33tは、不適切な単語の特定をより複雑にするもう 1 つの方法です。お尻が検閲される一方で、a$$ や @ss は、基本的に同じ用語が異なる方法で表現されていても、必ずしも同じように扱われるとは限りません。$ や @ などの多くの特殊文字がナンバープレートに表示されるかどうかはわかりませんが、Web コンテンツのペアレンタルコントロールは、検閲する用語を識別するためにこれらの種類のアルゴリズムが必要であると考えることができます。

score 1 · Accepted Answer

個々の構成を一意に表すデータ構造を作成することをお勧めします。次に、各互換性ルールは、そのルールに失敗するすべての個別の構成を含むセットを生成できるように定義する必要があります。次に、すべてのルールによって生成されたすべてのセットの和集合を取得して、ルールに失敗したすべての構成のセットを取得します。次に、そのセットのサイズを数え、それをセットのすべての可能な構成のサイズから差し引きます。

難しいのは、ルールによって生成でき、設定された操作を実行できるようにデータ構造を定義することです。それは読者のための練習です、別名私は何も持っていません。

score 1 · Accepted Answer

私が今考えることができる唯一のことは、単純な解決策を持つパーツ間の依存関係を定義するツリーを構築できるかどうかです。

sandwitch
|
|__Bun(2)__sesame(1)
|
|__Mustard(3)
|
|__Mayo(2)
|
|__Ketchup(2)
|
|__Olives(3)

これは単に、パンに 2 つのオプションがあることを示しています (パンまたはパンなし) - ゴマに 1 つ (パンがある場合のみ - 依存関係を示します - ここに 7 がある場合は、7 つのタイプが存在することを意味します。パンを持っています）

マスタード用3..など

次に、すべてのブランチの合計を単純に掛けます。

score 1 · Accepted Answer

この問題をk-sat 問題として形式化することはおそらく可能です。場合によっては、問題が NP 完全であるように見え、すべての可能性を列挙して、それらがすべての条件を満たしているかどうかを確認する必要があります。他のいくつかのケースでは、問題は簡単に解決できます (たとえば、必要な条件がほとんどない場合)。これは活発な研究分野です。Google Scholar で関連する参考文献を見つけることができます。

マスタードの場合、マスタードタイプのバイナリエントリ「mustard_type」を追加し、次の条件を導入します。not (not mustard and mustard_type)wheremustardはマスタードのバイナリエントリです。を選択すると、デフォルトの選択が強制されmustard_type == 0ますnot mustard。

ゴマの選択については、これはより明確です: not (sesame and not bun).

したがって、あなたが提案するケースは、問題の 2-sat ファミリーに分類されるようです。