2

15都市のリストがあります。可能な 15*14/2=105 組の都市から 70 組を無作為に抽出します。70 組のそれぞれについて、参加者に都市 A が都市 B よりも大きいかどうかを判断してもらいます。重要なことは、参加者が「間違い」を犯して、以前の回答と矛盾する回答をすることがあることです。(つまり、推移性に違反しています)。

推移性に違反する試行の数を最小限に抑える方法で、各参加者の応答に基づいて都市を並べ替える方法が必要です。

一意の解決策がない可能性があるため、都市の実際の順序は必要ありません。各参加者によって与えられた自動詞の回答の (最小) 数を計算する必要があるだけです。

徹底的な検索を使用する以外に、どうすればこれを行うことができますか?

編集: 例として、都市 A、B、C、D、および E を取り上げます。参加者のジョン ドウは、都市の正しい順序 (最小から最大) は ABCDE であると考えています。私は、彼が実際に正しいかどうかは気にしません。ただ、彼の反応 (以下にリストされています) が彼の信念とどれだけ一致しているかだけに関心があります。

3 回の独立した裁判で、ジョンは次のように答えました。

試行 1: A < B

試行 2: B < C (+)

試行 3: C < D

試行 4: D < E (+)

試行 5: E > B (*)

したがって、試行 5 の回答 (*) は、試行 2 および 4 の回答と矛盾します。1 つの試行 (番号 5) がジョンの信念と一致しなかったか、2 つの試行 (2 と 4) が一致しませんでした。どちらがジョンの信念 (ABCDE) であったかはわかりませんが、ジョン・ドウの「自動詞の最小数」が 1 であることを知る必要があるだけです。

4

1 に答える 1

2

だから...問題は面白いかもしれませんが、あなたが何を望んでいるのかは明らかではありません。都市を並べ替える必要がありますが、順序は必要ありませんか?

推移性に違反する試行の数を最小限に抑える...どうやってそれを行うのですか? 非推移性は、あなたが得た答えにあるのであって、それをどうするかではありません。

各参加者によって与えられた自動詞の回答の数を計算します...各被験者のすべての回答がある場合、矛盾は、ノードが都市であり、ノードが別のノードを指している直接グラフのサイクルです。都市は他の都市よりも大きいです。そのためのアルゴリズムがあります。この質問を参照してください。

もちろん、エッジは複数のサイクルの一部である可能性があり、この場合、非循環にするために削除する必要があるエッジの最小数を見つけようとすることができます。残念ながら、問題は完全な NPです。そのため、すぐに答えを見つけることはできません。ただし、数値がかなり低いため、かなり高速なソリューションを見つけることができる場合があります。

お役に立てれば。

于 2015-08-03T09:27:14.063 に答える