3

あなたは以前に頭の体操を注文するのを見たことがあるかもしれません：

BrainBashersトライアスロンの最新ラウンドでは、キースは4位でした。エイドリアンは最年長ではありませんが、2番目ではなかったダンカンよりも年上です。最年少の次の年齢の子供は2番目に終わった。3位で終わった子供は1位で終わった子供より年上です。ビリーは3位で終わった子供より若いです。誰がどこで終わったかを判断し、年齢順に子供を配置できますか？[ソース]

非常によく似た問題のように見えるものを解決するためのアルゴリズム的アプローチを探しています。

オブジェクトを相互に関連付けるルールに基づいて並べ替えたいオブジェクトのセットがあります。特定のルールセットに対して、複数の解決策が存在する場合があります。そして、有効なソリューションでは、すべてのルールが満たされています。一連のルールに有効なソリューションがない可能性もあります。

例：

オブジェクト：A, B, C, D, E, and F

ルール：

  • C> A
  • C <D
  • F <C
  • A> F
  • E> F
  • D> E

考えられる解決策の1つ：

 F A C E D B

オブジェクトBは他のどのオブジェクトとも関連していないため、シーケンスのどこに表示されるかは問題ではないことに注意してください。

確かにこれは以前に行われたことがあります。誰かが私を正しい方向に向けることができますか？最終的には、この並べ替えをJavaで実行します。

関連する質問： Java partially ordered Collection<E>

4

3 に答える 3

6

1つのオプションは、ルールを使用して有向グラフを作成し、トポロジカルソートを実行することです。

注：これが最も効率的な方法であるかどうかはわかりません。これは私が最初に考えた方法です。ただし、これはO（N）であるため、漸近的な観点からはそれほどうまくいくことはありません。

于 2013-01-03T16:56:16.213 に答える
3

効率的ではありませんが、単純なブルートフォース攻撃の方法は

List<String> names = Arrays.asList("A", "B", "C", "D", "E", "F");
do {
    Collections.shuffle(names);
} while (!(
        names.indexOf("C") < names.indexOf("A") &&
                names.indexOf("C") > names.indexOf("D") &&
                names.indexOf("F") > names.indexOf("C") &&
                names.indexOf("A") < names.indexOf("F") &&
                names.indexOf("E") < names.indexOf("F") &&
                names.indexOf("D") < names.indexOf("E")));
System.out.println("A solution is " + names);

プリント

A solution is [D, C, A, B, E, F]
于 2013-01-03T16:57:59.740 に答える
1

[編集、より適切な説明]先行オブジェクトがないオブジェクトを使用してから、先行オブジェクトがなく、すでに使用されているオブジェクトを使用する、というように続きます。

オブジェクトのすべての先行オブジェクトを調べてから、先行オブジェクトがないオブジェクトを見つけて最初の位置に配置することができます。次に、すでに使用されているもの以外の先行オブジェクトがないオブジェクトを探します。等々...

于 2013-01-03T16:59:19.473 に答える