2

私は学生のセットを持っています (一般性のためにタイトルでアイテムと呼ばれます)。これらの学生の中には、やんちゃであるという評判がある学生もいます。「私はjが嫌い」という形の一連の憎悪関係について話されます。「私は j が嫌い」は、 「j は私が嫌い」という意味ではありません。「iがjを嫌う」場合、iがjの番号よりも厳密に小さい番号の列に配置されるように、生徒を列に並べます（最前列の番号は1） 。 j の行の前にある行) を使用して、j に何もスローしないようにします (後戻りは許可されません)。必要な行の最小数を見つけるための効率的なアルゴリズムは何でしょうか (各行の生徒数が同じである必要はありません)。

次の仮定を行います。

1) これを有向グラフとしてモデル化すると、グラフにサイクルはありません。最も基本的なサイクルは次のようになります。「i は j が嫌い」が true の場合、「j は i が嫌い」は false です。そうしないと発注できなくなると思うからです。

2) グループ内のすべての生徒が、少なくとも 1 人の他の生徒に嫌われている、または少なくとも 1 人の他の生徒を嫌っている。もちろん、一部の人に嫌われている生徒と、他の生徒を嫌っている生徒がいるでしょう。これは、グラフの一部を形成しない迷子の生徒がいないことを意味します。

更新: 'i が j を嫌う場合、i --> j を使用して有向グラフを作成し、トポロジカル ソートを行うことを既に考えています。ただし、すべての生徒を一列に並べる必要がある場合は、一般的なトポロジカルソートの方が適しているためです。ここには行のバリエーションがあるため、トポロジーソートへの変更を考慮して、必要なものを得る方法を見つけようとしています。

回答するときは、ソリューションの複雑さを述べてください。誰かがコードを提供していて、言語を気にしないのであれば、私は Java を好みますが、もちろん他の言語でも問題ありません。

JFYI これは宿題用ではありません (私は学生ではありません :))。

4

7 に答える 7

3

トポロジカル ソートを調査する必要があるように思えます。

于 2009-03-27T12:16:10.837 に答える
2

この問題は基本的に、有向グラフの問題で最長パスを配置する別の方法です。行数は、実際にはパス内のノード数 (エッジ数 + 1) です。

グラフが非循環的であると仮定すると、ソリューションはトポロジカル ソートになります。A-> B と B -> A だけが無効ではありません。また、A -> B、B -> C、C -> A、および任意の長さの任意のサイクル。

ヒント: 問題は、どの生徒がどの列にいるかではなく、何列必要かということです。質問に対する答えは、最長パスの長さです。

于 2009-03-27T12:28:43.287 に答える
1

それはプロジェクト管理理論（またはスケジューリング理論、正確な用語はわかりません）からのものです。そこでのタスクは、ジョブの並べ替えに関するものです（頂点はジョブ、アークはジョブの順序関係です）。

明らかに、ループのない接続された有向グラフがいくつかあります。嫌いな場合に限り、a頂点から頂点への弧があります。ソース（入力アークなし）と宛先（出力アークなし）の頂点があると仮定しましょう。そうでない場合は、架空のものを追加してください。ここで、ソースから宛先までの最長パスの長さを見つけたいと思います（行数は-1になりますが、架空の頂点に注意してください）。bab

頂点ランク（r[v]）を、ソースとこの頂点の間の最長パスにある円弧の数として定義しますv。明らかに私たちは知りたいですr[destination]。ランクを見つけるためのアルゴリズム：

0) r_0[v] := 0  for all verteces v
repeat
t) r_t[end(j)] := max( r_{t-1}[end(j)], r_{t-1}[start(j)] + 1 )  for all arcs j
until for all arcs j r_{t+1}[end(j)] = r_t[end(j)]    // i.e. no changes on this iteration

各ステップで、少なくとも1つの頂点がランクを上げます。したがって、この形式では複雑さはO(n^3)です。

ちなみに、このアルゴリズムは、行間のスチューデント分布も提供します。生徒をそれぞれのランクでグループ化するだけです。

編集：同じ考えを持つ別のコード。おそらくそれはよりよく理解できます。

# Python
# V is a list of vertex indices, let it be something like V = range(N)
# source has index 0, destination has index N-1
# E is a list of edges, i.e. tuples of the form (start vertex, end vertex)
R = [0] * len(V)
do:
    changes = False
    for e in E:
        if R[e[1]] < R[e[0]] + 1:
            changes = True
            R[e[1]] = R[e[0]] + 1
while changes
# The answer is derived from value of R[N-1]

もちろん、これは最も単純な実装です。最適化することができ、時間の見積もりを改善することができます。

Edit2：明らかな最適化-前のステップで更新された頂点に隣接する頂点のみを更新します。つまり、ランクが更新された頂点を持つキューを導入します。また、エッジストアの場合は、隣接リストを使用する必要があります。このような最適化では、複雑さはになりますO(N^2)。実際、各頂点はほとんどの場合キューに表示される可能性がありますrank。ただし、頂点ランクがN-頂点の数を超えることはありません。したがって、アルゴリズムステップの総数はを超えませんO(N^2)。

于 2009-03-27T12:42:56.827 に答える
1

行数は、有向グラフの最長パスの長さに 1 を加えたものです。極限のケースとして、ヘイト関係がなければ、全員が同じ列に収まる可能性があります。

行を割り当てるには、他の誰にも嫌われていない人をすべて行 1 に配置します。これらは、グラフの「根」です。N がいずれかのルートからその人までの最長パスの長さである場合 (このパスの長さは少なくとも 1 です)、他のすべての人は行 N + 1 に置かれます。

単純な O(N^3) アルゴリズムは次のとおりです。

S = set of students
for s in S: s.row = -1        # initialize row field
rownum = 0                    # start from first row below
flag = true                   # when to finish
while (flag):
  rownum = rownum + 1         # proceed to next row
  flag = false
  for s in S:
    if (s.row != -1) continue # already allocated
    ok = true
    foreach q in S:
      # Check if there is student q who will sit
      # on this or later row who hates s
      if ((q.row == -1 or q.row = rownum)
          and s hated by q) ok = false; break
    if (ok):                  # can put s here
      s.row = rownum
      flag = true
于 2009-03-27T17:58:57.627 に答える
1

本質的に、仮定 #1 で重要なことは、このグラフに循環があってはならないということです。循環がある場合、この問題は解決できません。

私は、後ろの列に他の生徒を嫌いではないすべての生徒を座らせることから始めます. 次に、これらの学生を嫌う学生を次の列などに座らせることができます。

于 2009-03-27T12:17:30.430 に答える
0

簡単な答え = 1 行。

すべての生徒を同じ列に並べます。

実際、それは述べられているように質問を解決しないかもしれません-等しい行ではなく、より少ない行...

  1. すべての生徒を行 1 に配置します
  2. 嫌いな関係ごとに、嫌いでない生徒を嫌いな生徒の後ろに一列に並べます
  3. アクティビティがなくなるまで繰り返すか、Num(relation) 回繰り返します。

しかし、より良いアルゴリズムがあると確信しています - 非循環グラフを見てください。

于 2009-03-27T12:18:02.020 に答える