問題タブ [np-hard]

私が作成しているゲームの値でランク付けしたい ~ 1000 の異なるアセットのリストがあります。

プレーヤーには、2 つのアセット バスケットのいずれかを選択する機会が与えられます。たとえば、A + B または C のどちらを希望するかを尋ねられる場合があります。

バスケットの好みの膨大なリストから、認識された価値によって資産をランク付けしたいと考えています。

以下は入力の例で、それに応じてプレイヤーは次のように言っています。

つまり、彼らは B よりも A を好む。B と C よりも 2 つの As を好む。

この入力から、最も可能性の高い値のランキングは次のようになると思います。

この問題を解決するには、どのクラスのアルゴリズムを使用する必要がありますか?

場合によっては、好みのリストが矛盾することがあります (A > B と考えるプレイヤーもいれば、B > A と考えるプレイヤーもいます)。プレーヤーのスキル レベルの別の測定値がある場合、これをどのように活用してより正確なランキングを取得できますか?

また、バスケット間の関係に「島」がある場合も処理できる必要があります。例えば：

つまり、A <> C かどうかはわかりません。

これは、さまざまなパッキング アルゴリズムに似た最適化問題のように思えます。このランキング問題は NP 困難ですか?

私は NP 困難な問題アルゴリズム (手売り問題など) に取り組んでいますが、適切なアルゴリズムが見つかりません。誰かが私を助けてくれれば幸いです。マトリックスが(x,y)あり、ブロックにはロボットがあり(n,m)、マトリックス ブロックにはゴミがあります。

ロボットがゴミのある各ブロックに移動し、すべてのブロックを通過した後、最初のブロックに戻るようにします。関連する質問には2つの条件があります。

1. ロボットは水平方向と垂直方向にのみ移動できます。
2. 出力は、交差したパスの長さである整数です。このパスには最小の長さが必要です。

たとえば、入力は次のとおりです。

ゴミの位置:

出力は次のとおりです。

タブー検索を使用して巡回購入者/巡回セールスマンを解決しているのをよく見かけます。調べてみたいのですが、常に進行状況と停止条件を理解できません。これを達成する方法について誰か説明してもらえますか? ?

PS: 出力には、他のサブセットであるセットは含まれていません。1)If X = {1, 2, 3}はソリューションの 1 つです。その場合、 のすべてのサブセットX {1} {2} {3} {1, 2} {1, 3} {2, 3}は省略されます。

それを解決するアルゴリズムがいくつかあることは知っていますが、多項式アルゴリズムがあるかどうかは疑問です。存在する場合、どのように機能しますか? そうでない場合、それを NP 困難な問題として証明する方法。

ありがとう！

ゲーム Final Fantasy XIII-3 では、プレイヤーにいくつかのパズルが提示されます。導入された最初のパズルはTile Trialと呼ばれ、プレイヤーにタイルのグリッドを提示し、その中にはクリスタルが付いているものもあります。目標は、すべてのクリスタルを回収して出口に到達することですが、各タイルを 1 回しか踏まないでください。

http://arxiv.org/pdf/1203.1633v1.pdfの著者は、特定のケースがハミルトンサイクルに還元できるため、この問題は NP 困難であると述べています。彼は特定のパズルを開発したため、これは単純な仮定であることがわかりました。これは、ゲームのルールには合っていますが、たまたまハミルトニアン サイクルを含んでいるだけです。

一般的なケースを見ると、パズルの各タイルをグラフの頂点としてモデル化できます。2 つのタイルが隣接している場合、頂点には別の頂点へのエッジがあります。問題は、結晶を持つすべての頂点を横断し、どの頂点にも 2 回以上アクセスしないようにしながら、開始タイルから終了タイルまでのパスを見つけることです。

これは、都市のサブセットのみを訪問する必要がある TSP (巡回セールスマン問題) に還元できると思います。n都市の通常の TSP 問題を想定します。ただし、この特定の問題では、 n 個の都市すべてを訪れる必要はなく、m<=nである特定のサブセット m のみを訪問する必要があります。mではなくnにある都市を訪れる必要はありませんが、たとえばパスm1->m2がm1->n1->m2よりも大きい場合は、訪問する必要があります。

しかし、この「単純な」TSP 問題はまだ NP 困難ですか? リダクションとして使用できる、より優れた NP 困難な問題を知っている人はいますか?

nセットの整数が与えられた場合、重複しないセットの数を最大化する方法は?

たとえば、与えられたsetsものを、

すると答えは4、

{1,2,3}1 は両方のセットで共通であるため、重複し{1,4,5}ないセットで構成することはできません。それはNPが聞いた問題ですか？その問題に対する効率的な解決策があれば、少し詳しく説明します。

[NB]入力セットの数は最大1000で、各セットには最大1000 個の整数が含まれます。

私はアルゴリズムを勉強していて、この演習に出くわしました:

「プログラム P が与えられた入力 x で初期化されていない変数を使用するかどうかを決定するプログラム/アルゴリズムがないことを証明してください。」

これが私が思いついた証拠です：

プログラム P が特定の入力 x で初期化されていない変数を使用しているかどうかを判断するアルゴリズム Det があると仮定しましょう。

プログラムを

P(x) Det(P,x) が true の場合、何もしません variable i print i

ここに矛盾が見られます。Det(P,x) が false の場合、初期化されていない変数が使用されています。初期化されていない変数を他の場所で使用していないため、true を返すたびに間違っています。

正しい方法で考えているかどうかはわかりません。