作业调度算法

Question

在一次面试中回答了这个问题。想知道是否有更好的解决方案：

给定N个任务以及它们之间的依赖项，请提供一个执行序列，确保作业在不违反依赖关系的情况下被执行。

示例文件：

5 1<4 3<2 4<5

第一行是总任务数。1<4意味着任务1必须在任务4之前执行。

一个可能的顺序是:1 4 5 3 2

我的解决方案使用DAG来存储所有的数字，然后是拓扑排序。有没有一种不那么笨重的方法来解决这个问题？：

    DirectedAcyclicGraph<Integer, DefaultEdge> dag = new DirectedAcyclicGraph<Integer, DefaultEdge>(DefaultEdge.class); 
    Integer [] hm = new Integer[6];
    //Add integer objects to storage array for later edge creation and add vertices to DAG
    for(int x = 1; x <= numVertices; x++){
        Integer newInteger = new Integer(x);
        hm[x] = newInteger;
        dag.addVertex(newInteger);
    }
    for(int x = 1; x < lines.size()-1; x++){
        //Add edges between vertices
        String[] parts = lines.get(x).split("<");
        String firstVertex = parts[0];
        String secondVertex = parts[1];
        dag.addDagEdge(hm[Integer.valueOf(firstVertex)], hm[Integer.valueOf(secondVertex)]);
    }
    //Topological sort
    Iterator<Integer> itr = dag.iterator();
    while(itr.hasNext()){
        System.out.println(itr.next());
    }   

Answer 1

正如几个用户(Gassa、shekhar suman、mhum和Colonel )已经说过的那样，通过寻找拓扑排序解决了这个问题。只要dag中的迭代器按照这个顺序返回元素，它就正确。我不知道DirectedAcyclicGraph类是从哪里来的，所以我无法控制它。否则，这个方法会像你一样进行解析，并使用一个简单的算法(实际上，第一个在我脑海中浮现)。

public static int[] orderTasks (String[] lines){
    // parse
    int numTasks = Integer.parseInt(lines[0]);
    List<int[]> restrictions = new ArrayList<int[]>(lines.length-1);
    for (int i = 1; i < lines.length; i++){
        String[] strings = lines[i].split("<");
        restrictions.add(new int[]{Integer.parseInt(strings[0]), Integer.parseInt(strings[1])});
    }

    // ordered
    int[] tasks = new int[numTasks];
    int current = 0;

    Set<Integer> left = new HashSet<Integer>(numTasks);
    for (int i = 1; i <= numTasks; i++){
        left.add(i);
    }
    while (current < tasks.length){
        // these numbers can't be written yet
        Set<Integer> currentIteration = new HashSet<Integer>(left);
        for (int[] restriction : restrictions){
            // the second element has at least the first one as precondition
            currentIteration.remove(restriction[1]);
        }
        if (currentIteration.isEmpty()){
            // control for circular dependencies
            throw new IllegalArgumentException("There's circular dependencies");
        }
        for (Integer i : currentIteration){
            tasks[current++]=i;
        }
        // update tasks left
        left.removeAll(currentIteration);
        // update restrictions
        Iterator<int[]> iterator = restrictions.iterator();
        while (iterator.hasNext()){
            if (currentIteration.contains(iterator.next()[0])){
                iterator.remove();
            }
        }
    }
    return tasks;
}

顺便说一句，在您的hm数组初始化中，您定义了它有6个元素。它使0位置为空(这不是一个问题，因为您没有调用它无论如何)，但在一般情况下，任务的数量可能大于5，然后您将拥有和IndexOutOfBoundsException

在循环依赖的情况下，如果DAG引发的异常消息不够清楚，在添加边缘时，另一个注意事项可能会使用户感到困惑。再说一遍，既然我不知道那门课是从哪里来的，我就不知道了。