Алгоритм установления порядка среди набора предметов

Question

У меня есть набор учеников (именуемые в названии предметы для общности). Среди этих студентов некоторые имеют репутацию буйных. Нам рассказывают о множестве отношений ненависти в форме «я ненавижу j». «я ненавижу j» означает , а не означает «j ненавидит меня». Мы должны расположить студентов в ряды (передний крайний ряд с номером 1) таким образом, чтобы, если «я ненавижу j», то меня помещали в ряд, который на строго меньше, чем на j (другими словами: в некоторой строке перед строкой j), чтобы я ничего не бросал в j (возврат назад запрещен). Каким был бы эффективный алгоритм для нахождения минимального необходимого количества строк (в каждой строке не должно быть одинакового количества студентов)?

Мы сделаем следующие предположения:

1) Если мы смоделируем это как ориентированный граф, в графе нет циклов. Самый простой цикл: если «я ненавижу j» - это правда, «j ненавидит i» - это ложь. Потому что в противном случае я думаю, что заказ станет невозможным.

2) Каждый студент в группе, по крайней мере, ненавидится одним другим студентом ИЛИ, по крайней мере, ненавидит одного другого студента. Конечно, найдутся студенты, которых ненавидят одни и которые, в свою очередь, ненавидят других. Это означает, что нет бездомных студентов, которые не составляют часть графика.

Обновление: Я уже думал о построении ориентированного графа с i -> j, если 'я ненавижу j, и выполнении топологической сортировки. Однако, поскольку общая топологическая сортировка была бы лучше, если бы я выстроил всех студентов в одну строку. Поскольку здесь есть варианты строк, я пытаюсь выяснить, как включить изменение в топологическую сортировку, чтобы оно дало мне то, что я хочу.

Когда вы отвечаете, пожалуйста, укажите сложность вашего решения. Если кто-то даёт код, а вы не против языка, то я бы предпочел Java, но, конечно, любой другой язык так же хорош.

JFYI Это не для каких-либо домашних заданий (кстати, я не студент):

Answer 1

Мне кажется, вам нужно изучить топологическую сортировку .

Answer 2

Количество строк - это длина самого длинного пути в ориентированном графе плюс одна. В качестве предельного случая, если нет отношений ненависти, каждый может поместиться в одном ряду.

Чтобы распределить строки, поместите всех, кого никто не ненавидит, в строку один. Это «корни» вашего графика. Все остальные помещаются в строку N + 1, если N - длина самого длинного пути от любого из корней до этого человека (этот путь имеет длину как минимум один).

Простой алгоритм 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

Answer 3

Это из теории управления проектами (или теории планирования, я не знаю точного термина). Там задача состоит в сортировке заданий (вершина - это задание, дуга - это отношение к порядку заданий).

Очевидно, у нас есть некоторый связный ориентированный граф без петель. Существует дуга от вершины a до вершины b тогда и только тогда, когда a ненавидит b. Предположим, что есть исходная (без входящих дуг) и конечная (без исходящих дуг) вершина. Если это не так, просто добавьте воображаемые. Теперь мы хотим найти длину самого длинного пути от источника до места назначения (это будет число строк - 1, но помните о воображаемых вершинах).

Мы определим ранг вершины (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

На каждом шаге хотя бы одна вершина увеличивает свой ранг. Поэтому в этой форме сложность составляет 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).

Answer 4

Эта проблема - в основном другой способ поставить самый длинный путь в задачу ориентированного графа . Количество строк фактически является количеством узлов в пути (количество ребер + 1).

Если предположить, что график равен ациклично , решение будет топологическая сортировка Acyclic немного сильнее вашего предположения 1. Не только A -> B и B -> A недействительны. Также A -> B, B -> C, C -> A и любой цикл любой длины.

СОВЕТ: вопрос , сколько строк необходимо, а не какой студент в каком ряду. Ответ на вопрос - длина самого длинного пути.

Answer 5

В предположении №1 важно, что в этом графе не должно быть циклов. Если есть какие-либо циклы, вы не можете решить эту проблему.

Я бы начал с того, что рассадил всех учеников, которые не ненавидят других учеников в заднем ряду. Затем вы можете расположить учеников, которые ненавидят этих учеников, в следующем ряду и т. Д.

Answer 6

Построить граф отношений, где я ненавижу, j будет иметь направленное ребро от i до j. Таким образом, конечный результат - ориентированный граф. Это должен быть DAG, в противном случае нет решений, так как невозможно разрешить круговые отношения ненависти.

Теперь просто выполните поиск DFS и во время обратных вызовов после узла, что означает, что после того, как DFS всех дочерних элементов завершена, и перед возвратом из вызова DFS к этому узлу просто проверьте номер строки всех дочерних элементов и назначьте номер строки этого узла как строка max max строки дочернего элемента + 1. Если, если есть кто-то, кто никого не ненавидит, в основном узел без списка смежности, просто назначьте ему строку 0.

Как только все узлы обработаны, поменяйте местами номера строк. Это должно быть легко, поскольку речь идет только о поиске максимума и назначении номеров строк как максимум уже назначенных номеров строк.

Вот пример кода.

postNodeCb( graph g, int node )
{
    if ( /* No adj list */ )
        row[ node ] = 0;
    else
        row[ node ] = max( row number of all children ) + 1;
}

main()
{
.
.

    for ( int i = 0; i < NUM_VER; i++ )
        if ( !visited[ i ] )
            graphTraverseDfs( g, i );`enter code here`
.
.
}

Answer 7

Простой ответ = 1 строка.

Поместите всех студентов в один ряд.

На самом деле это может не решить вопрос, как указано - меньшая строка, а не равная строка ...

1. Поместите всех студентов в ряд 1
2. Для каждого отношения ненависти ставьте ученика без ненависти в ряд позади ученика ненавидящего
3. Повторяйте, пока у вас нет активности, или повторяйте Num (отношение) раз.

Но я уверен, что есть лучшие алгоритмы - посмотрите на ациклические графы.