2

我有一组学生（为了概括起见，在标题中称为项目）。在这些学生中，有些人以粗暴着称。我们被告知一组“我讨厌 j”形式的仇恨关系。“我讨厌 j”并不意味着“j 讨厌我”。我们应该将学生排成一排（最前面的一排编号为 1），如果“我讨厌 j”，那么我应该排在编号严格小于 j 的排中（换句话说：在j 行前面的某行），这样我就不会向 j 扔任何东西（不允许转身）。找到所需的最小行数（每行不必有相同数量的学生）的有效算法是什么？

我们将做出以下假设：

1）如果我们将其建模为有向图，则图中没有环。最基本的循环是：如果“我讨厌 j”为真，“j 讨厌我”为假。因为否则，我认为订购将变得不可能。

2）小组中的每个学生至少被另一个学生讨厌或至少讨厌另一个学生。当然，也会有学生既被一些学生讨厌，又反过来讨厌其他学生。这意味着没有不属于图表一部分的流浪学生。

更新：我已经考虑过用 i --> j if 'i hats j 构建有向图并进行拓扑排序。但是，如果我必须将所有学生排成一行，则一般拓扑排序会更适合。由于这里的行有所不同，我试图弄清楚如何将变化因素考虑到拓扑排序中，这样它就给了我想要的东西。

当您回答时，请说明您的解决方案的复杂性。如果有人提供代码并且您不介意该语言，那么我更喜欢 Java，但当然任何其他语言都一样好。

JFYI 这不适用于任何类型的作业（顺便说一句，我不是学生：））。

4

7 回答 7

3

在我看来，您需要研究拓扑排序。

于 2009-03-27T12:16:10.837 回答
2

这个问题基本上是将最长路径放入有向图问题的另一种方法。行数实际上是路径中的节点数（边数 + 1）。

假设图是无环的，解决方案是拓扑排序。您的假设 1 的非循环要强一些。不仅 A -> B 和 B -> A 无效。还有 A -> B, B -> C, C -> A 和任何长度的任何循环。

提示：问题是需要多少行，而不是哪个学生在哪一行。问题的答案是最长路径的长度。

于 2009-03-27T12:28:43.287 回答
1

本质上，假设 #1 中的重要一点是该图中不能有任何循环。如果有任何循环，您将无法解决此问题。

我会先让所有不讨厌任何其他学生的学生坐在后排。然后你可以让讨厌这些学生的学生坐在下排等。

于 2009-03-27T12:17:30.430 回答
1

它来自项目管理理论（或调度理论，我不知道确切的术语）。那里的任务是关于排序作业（顶点是作业，弧是作业顺序关系）。

显然，我们有一些没有循环的连通图。当且仅当hats时，从顶点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

每一步至少有一个顶点增加它的等级。因此这种形式的复杂度是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

行数是有向图中最长路径的长度加一。作为一个极限情况，如果没有仇恨关系，每个人都可以坐在同一排。

要分配行，请将不被其他任何人讨厌的每个人放在第一行。这些是图表的“根”。如果 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 回答
0

简单答案 = 1 行。

将所有学生放在同一行。

实际上，这可能无法解决上述问题-较少的行，而不是相等的行...

  1. 将所有学生放在第 1 行
  2. 对于每个仇恨关系，将不讨厌的学生排在讨厌的学生后面
  3. 迭代直到你没有活动，或者迭代 Num(relation) 次。

但我确信有更好的算法——看看无环图。

于 2009-03-27T12:18:02.020 回答
0

构造一个关系图，其中 i 讨厌 j 将具有从 i 到 j 的有向边。所以最终结果是一个有向图。它应该是一个 DAG，否则没有解决方案，因为它不可能解决循环仇恨关系船。

现在只需进行 DFS 搜索并在后节点回调期间，意味着一旦所有子节点的 DFS 完成并且在从 DFS 调用返回到该节点之前，只需检查所有子节点的行号并分配这个节点作为孩子的最大行+ 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`
.
.
}
于 2015-01-14T03:16:17.423 回答