最有效的算法,为长凳生成随机座位表？

Question

我正在为一位教师的家庭成员编写应用程序.她要求一个应用程序,允许她进入一群孩子,设定他们的惯用手,设置他们不能坐在旁边的人,指定每个工作台有多少个座位,然后为孩子们生成一个随机的布局,这样就没有了 - 汉德斯坐在右手边的右边,不应该坐在一起的孩子们不会坐在长凳上.

这与通用表座位算法的问题并不完全相同,因为一个工作台有2个端点,并且因为节点没有"值"来创建任何优先分组.

我决定创建一个有向图,其中边表示谁可以坐在给定孩子的右边.然后我从每个节点做一个递归DFS而不触摸节点两次,直到我得到一个触摸每个节点的路径.一个问题是,在每个工作台的"尽头",任何人都可以坐到他们的"右边".

这个算法似乎总是有效,这很好.但是,一旦我超过10个孩子在一个长凳上,假设长椅可以说20个孩子,那么运行时似乎会变得非常糟糕.我做错了什么,还是有更好的方法来解决这个问题？Java代码如下.

编辑:对不起,我没有说清楚,但我希望每次都能实现RANDOM座位安排,这样孩子们就不会被困在同一个地方或同一个长凳上或者在同一个孩子旁边.此外,我的应用程序运行此算法:

http://kcraigie.com/sittychart

目前我正在强制执行1,000,000个节点触摸的上限,这样我的服务器就不会受到冲击.您可以看到算法似乎正确缩放,直到您将每个工作台的座位设置为9左右,此时它立即变得难以处理.

private static class Person {
    private String m_name = null;
    private Handedness m_handedness = null;
    private Set<Person> m_nonadjacents = null;
}

private static class Node {
    private Person m_person = null;
    private List<Node> m_possibleRightNodes = null;
    private boolean m_isInPath = false;
}

private Stack<Node> generateSeatingArrangement() {
    // Generate randomized directed graph, start with all nodes as root nodes
    for(Person leftPerson: people.values()) {
        Node node = new Node(leftPerson);
        nodes.put(leftPerson, node);
    }
    // Create all edges based on constraints
    for(Node leftNode: nodes.values()) {
        List<Node> possibleRightNodes = new LinkedList<>();
        for(Node rightNode: nodes.values()) {
            Person leftPerson = leftNode.getPerson();
            Person rightPerson = rightNode.getPerson();
            if(leftNode==rightNode) {
                log.fine("Can't seat '" + leftPerson.getName() + "' next to himself");
                continue;
            }
            if(leftPerson.getHandedness()==Person.Handedness.RIGHT_HANDED &&
               rightPerson.getHandedness()==Person.Handedness.LEFT_HANDED) {
                log.fine("Can't seat right-handed '" + leftPerson.getName()
                         + "' to the left of left-handed '" + rightPerson.getName() + "'");
                continue;
            }
            if(leftPerson.getNonadjacents().contains(rightPerson)) {
                log.fine("Can't seat '" + leftPerson.getName() + "' next to '" + rightPerson.getName() + "'");
                continue;
            }
            if(rightPerson.getNonadjacents().contains(leftPerson)) {
                // TODO: This should be redundant but not enforcing right now...
                log.fine("Can't seat '" + rightPerson.getName() + "' next to '" + leftPerson.getName() + "'");
                continue;
            }
            log.fine("Can seat '" + leftPerson.getName() + "' to the left of '" + rightPerson.getName() + "'");
            possibleRightNodes.add(rightNode);
        }
        Collections.shuffle(possibleRightNodes);
        leftNode.setPossibleRightNodes(possibleRightNodes);
    }
    List<Node> nodes2 = new LinkedList<>(nodes.values());
    Collections.shuffle(nodes2);

    // Perform recursive graph traversal
    Stack<Node> pathStack = new Stack<>();
    for(Node node: nodes2) {
        TraversalStatistics stats = new TraversalStatistics();
        boolean isPathFound = depthFirstSearchRecur(numSeatsPerBench, nodes2, pathStack, node, stats);
        if(isPathFound) {
            break;
        }
        pathStack.clear();
    }
}

// The resursive DFS method
private boolean depthFirstSearchRecur(int numSeatsPerBench,
                                      List<Node> allNodes,
                                      Stack<Node> pathStack,
                                      Node node,
                                      TraversalStatistics stats) {
    stats.numNodesTouched++;
    if(node.isInPath()) {
        stats.numLeavesReached++;
        return false;
    }
    pathStack.push(node);
    node.setIsInPath(true);
    if(pathStack.size() >= allNodes.size()) {
        return true; // We win!
    }
    if(pathStack.size() % numSeatsPerBench == 0) {
        // "End" of a bench, anyone can "sit to the right of" me
        for(Node node2: allNodes) {
            if(node == node2) {
                // Can't sit next to myself
                continue;
            }
            if(depthFirstSearchRecur(numSeatsPerBench, allNodes, pathStack, node2, stats)) {
                return true;
            }
        }
    } else {
        for(Node node2: node.getPossibleRightNodes()) {
            if(depthFirstSearchRecur(numSeatsPerBench, allNodes, pathStack, node2, stats)) {
                return true;
            }
        }
    }
    pathStack.pop();
    node.setIsInPath(false);
    return false;
}

Answer 1

我认为您不需要为每个节点生成可能的左节点列表。相反，可以通过带有引用的递归算法动态执行此操作。

第一个座位上是第一个节点。在节点列表中搜索第一个可能的邻居并将其安置在那里。重复此过程，直到计划完成或陷入死胡同。在这种情况下，请返回一个座位并为下一个可能的人安排座位（例如，如果是节点 4，请将其更改为节点 5）。尝试从那里开始下一个节点，或者，如果无法找到下一个节点（例如，列表中已经是最后一个节点），则返回一步，直到出现下一个节点。

使用此方法，您应该在统计上必须计算 n!/2 名学生 n 才能找到答案的可能性。

PS：希望你能理解我对算法的描述。如果我有更多时间，我会制作一个图表。