問題タブ [np-hard]

これは私が長い間頭に浮かんだ問題です。教師とプログラマーの息子である私は、早い段階でそれを思いつきました...しかし、私はまだそれに対する解決策を見つけていません。

これが問題です。いくつかの制約を使用して、学校のタイムスケジュールを作成する必要があります。これらは一般的に2つのカテゴリに分けられます。

健全性チェック

• 教師は2つのクラスを同時に教えることはできません
• 生徒は同時に2つのレッスンに従うことはできません
• 一部の教師は、週の間に少なくとも1日休む必要があります
• 曜日はすべてタイムテーブルでカバーする必要があります
• 被験者Xは毎週正確にまあまあの時間を持っている必要があります
• ..。

環境設定

• 各教師のスケジュールは可能な限りコンパクトにする必要があります（つまり、教師は1日中、可能であれば一時停止せずに1日中すべての時間作業する必要があります）
• 休日のある教師は、どの日に好みを表現できる必要があります
• アルバイトをしている教師は、学校の一日の初めと終わりのどちらで働くかという好みを表現できる必要があります。
• ..。

さて、解決策を見つけられなかった（そしてその間に1つか2つのことを学んだ...）数年後、私はこれがNP困難な問題のように聞こえることに気づきました。

NP困難として証明されていますか？

誰かがこのことをクラックする方法についてのアイデアを持っていますか？

この質問を見て、私はこの問題について、そしてこの場合に遺伝的アルゴリズムが使用できるかどうかについて考えさせられました。ただし、健全性チェックのルールを維持しながら可能性を変更することはかなり困難です。また、互換性のない要件を区別する方法もわかりません。

問題をより適切に特定するための小さな補遺。これは、すべての生徒が異なるクラス（たとえば、1年目のセクションA）に関連付けられ、教師がクラス間を移動するイタリアの学校スタイルの教室に適用されます。同じクラスのすべての生徒は同じスケジュールを持っており、どのレッスンに参加するかを選択することはできません。

私は大学で NP 完全性の文脈で TSP を学びました。実際の問題に適用される状況は実際にはありませんでした。少しの調査によると、ドリルを移動するための最も安価な経路、つまり回路基板に穴をあける方法を選択するために使用されていることが示されています。それは私が見つけることができたほとんどすべてです。

使っていますか？TSA には他にどのような実用的なアプリケーションがありますか?

valueそれぞれがとを持つアイテムの配列が与えられた場合、最小コストで最小値に到達するために必要なアイテムを決定する最適なアルゴリズムは何ですかcost? 例えば：

最後の全体的な価値: コストの比率は無関係であることに注意してください (A + Aお金に見合う最高の価値が得られますがA + B + B、最小値に達するより安価なオプションです)。

1,000 万人のプレイヤーがいるオンライン ポーカー サイトの共謀検出のアルゴリズムの複雑さを説明する最良の方法は何ですか?

仮定します（これらの仮定は大きな違いを生むとは思わないので、無視してかまいませんが、明確にするために）：

• サイトの登録ユーザー数が 10,000,000 であること。
• これらのプレイヤーが合計 50 億回のハンドをプレイしたこと。
• 提供される唯一の情報は、サイトの「マスターハンド履歴データベース」であり、すべてのプレーヤーのホールカードと各ハンドの賭けアクションが含まれています.
• 言い換えれば、IP アドレスを調べたり、異常なレーキ/利益パターンを探したりするなどの近道をすることはできません。
• ちょうど N 人 (N は 2 から 10 の間) のプレーヤーのグループを渡すと、グループ内のすべてのプレーヤーが共謀した場合に TRUE を返す関数が与えられたと仮定します。すべてのプレイヤーではなく一部のプレイヤーが共謀者である場合、関数は FALSE を返します。TRUE の戻り値は、(たとえば) 75% の信頼度で作成されます。

あなたの仕事は、共謀したすべてのプレイヤーの完全なリストと、彼が共謀したプレイヤーの完全なリストを作成することです。最近、この問題が NP 困難であると説明されているのを耳にしましたが、これは正確ですか? 単に「難しい」ものを「NP」または「NP-hard」と呼ぶことがあります。

ありがとう！

これが私が会計システムで作業しているように見える問題です。

私は一連のトランザクションを持っていますが、それらの合計は、経理部門がそうすべきだと考える金額と等しくありません。彼らは数学に疑問を投げかけているのではなく、含まれているのはトランザクションだけです：p

合計が特定の金額と一致するために、セット内のどのトランザクションを含めるべきでないかを判断するのに役立つアルゴリズムはありますか？

編集： セットに含まれるトランザクションは100未満です。XKCDの質問でNP完全問題を解くことに関するものがないので、誰かがC＃の例を持っていますか？

男、私はCSの学位を取得する必要がありました。

強く接続された有向グラフがあります（つまり、グラフGのノード（i、j）の各ペアに対してiからjおよびjからiへのパスがあります）。このグラフから、すべてのエッジの合計が最小になるように、強く接続されたグラフを見つけたいと思います。

別の言い方をすれば、エッジを削除した後でもグラフが強力に接続され、エッジの合計のコストが最小になるように、エッジを削除する必要があります。

NP困難な問題だと思います。20ノードのような小さなデータセットに対して、近似ではなく最適なソリューションを探しています。

編集

より一般的な説明：グラフG（V、E）が与えられた場合、Gにv1からv2へのパスが存在する場合、Gにv1とv2の間にパスが存在するように、グラフG'（V、E'）を見つけます。 'およびE'の各eiの合計は可能な限り最小です。したがって、最小の同等のグラフを見つけるのと似ていますが、ここでのみ、エッジの合計ではなく、エッジの重みの合計を最小化します。

編集：

これまでの私のアプローチ：複数回の訪問でTSPを使用して解決することを考えましたが、正しくありません。ここでの私の目標は、各都市をカバーすることですが、最小コストのパスを使用します。ですから、それはカバーセット問題のようなものだと思いますが、正確にはわかりません。総費用が最小の小道を使ってすべての都市をカバーする必要があるので、すでに訪れた小道を何度も訪れても費用は増えません。

NP 困難な問題を (おおよそ) 解決するプログラム (大学向けのプロジェクト) を作成する必要があります。これは線形順序付け問題のバリエーションです。一般に、(グラフとして) 非常に大きな入力があり、(各ソリューションを「評価」する関数に基づいて) 最適なソリューションを見つけようとします。

これを C スタイルのコード (1 つのメインと関数) で記述するか、Solver クラスを構築し、インスタンスを作成してメインから「実行」メソッドを呼び出すと、違いはありますか (Java に似ています)。

また、反復ごとに多くの浮動小数点演算が行われます。

ありがとう！

NP、NP-Complete、NP-Hardの違いは何ですか?

私はウェブ全体に多くのリソースがあることを知っています。あなたの説明を読みたいのですが、その理由は、それらがそこにあるものとは異なるか、または私が認識していない何かがあるからです.

私は 3 次元のビン パッキングの問題に直面しており、現在どのアルゴリズム/ヒューリスティックが最良の結果をもたらしているかについて予備的な調査を行っています。問題はNP困難であるため、すべての場合に最適な解決策が見つかるとは思っていませんが、疑問に思っていました:

1) 最適な正確なソルバーは何ですか? 分岐限定？妥当なコンピューティング リソースで解決できる問題のインスタンス サイズはどれくらいですか?
2) 最高のヒューリスティック ソルバーは何ですか?
3) いくつかの実験を行うための既製のソリューションには、どのようなものがありますか?

申し訳ありませんが、質問のタイトルが明確ではありません。これは、より具体的な例を提供しないと難しい質問です。次のシナリオを検討してください。

私には、誕生日が近い日付 (d1..dn) の友人が何人かいて、コスト (c1..cn) で購入したいギフトをいくつか考え出すことができました。残念ながら、これらのギフトを購入するために 1 日に節約できる金額 (m) は決まっています。私が聞きたい質問は次のとおりです。

友人の誕生日と私が十分なお金を貯めた日付との間の合計偏差を最小限に抑えるために、ギフトごとの貯蓄の理想的な配分 (mi、1..n == m からの mi の合計) は何ですか?そのギフトを購入する。

私が探しているのは、この問題の解決策、またはこの質問に決定論的に答えるために利用できる解決済みの問題へのマッピングです。ご検討いただきありがとうございます。さらに説明できることがあればお知らせください。