Python中A-to-B算法的最小删除节点数

Question

我想解决一个与图论有关的问题，但似乎记不起/找到/理解正确的/最好的方法，所以我想我应该问问专家。。。在

我有两个节点（示例代码中为1和10）的路径列表。我正在尝试找到要删除的最小节点数，以切断所有路径。我也只能删除某些节点。在

我目前已经实现了（下面）作为一个暴力搜索。这在我的测试集上运行得很好，但是当扩展到路径为100K且可用节点为100的图时，这将成为一个问题（阶乘问题）。现在，我不关心移除节点的顺序，但我会在某个时候考虑到这一点（在下面的代码中要列出开关集）。在

我认为应该有一种方法来解决这个问题，使用最大流量/最小切割算法。不过，我读到的每一件事都在某种程度上超出了我的想象。做这种事已经好几年了，我好像什么都记不起来了。在

所以我的问题是：

1）除了测试所有的组合和取最小的集合之外，有没有更好的方法来解决这个问题？在

2）如果是这样的话，你能解释一下吗？还是最好给出伪代码来帮助解释？我猜可能有一个库已经在某种程度上做到了这一点（我最近一直在寻找并使用networkX，但对其他人开放）

3）如果不是（或甚至是），建议如何多线程/进程解决方案？我想尽量从电脑中得到我能得到的每一点性能。（我在这个问题上找到了一些很好的线索，但我还没有机会去实现，所以我想我会同时问这个问题，只是碰巧而已。在优化之前，我首先想让一切正常运行。）

4）关于使代码更“Pythonic”的一般建议（可能也有助于提高性能）。我知道我可以做一些改进，而且对Python还是个新手。在

谢谢你的帮助。在

#!/usr/bin/env python


def bruteForcePaths(paths, availableNodes, setsTested, testCombination, results, loopId):

    #for each node available, we are going to
    # check if we have already tested set with node
    # if true- move to next node
    # if false- remove the paths effected,
    #           if there are paths left,
    #               record combo, continue removing with current combo,
    #           if there are no paths left,
    #               record success, record combo, continue to next node

    #local copy
    currentPaths = list(paths)
    currentAvailableNodes = list(availableNodes)
    currentSetsTested = set(setsTested)
    currentTestCombination= set(testCombination)

    currentLoopId = loopId+1

    print "loop ID: %d" %(currentLoopId)
    print "currentAvailableNodes:"
    for set1 in currentAvailableNodes:
        print "  %s" %(set1)

    for node in currentAvailableNodes:
        #add to the current test set
        print "%d-current node: %s current combo: %s" % (currentLoopId, node, currentTestCombination)
        currentTestCombination.add(node)
        # print "Testing: %s" % currentTestCombination
        # print "Sets tested:"
        # for set1 in currentSetsTested:
        #     print "  %s" % set1

        if currentTestCombination in currentSetsTested:
            #we already tested this combination of nodes so go to next node
            print "Already test: %s" % currentTestCombination
            currentTestCombination.remove(node)
            continue

        #get all the paths that don't have node in it
        currentRemainingPaths = [path for path in currentPaths if not (node in path)]

        #if there are no paths left
        if len(currentRemainingPaths) == 0:
            #save this combination
            print "successful combination: %s" % currentTestCombination
            results.append(frozenset(currentTestCombination))
            #add to remember we tested combo
            currentSetsTested.add(frozenset(currentTestCombination))
            #now remove the node that was add, and go to the next one
            currentTestCombination.remove(node)
        else:
            #this combo didn't work, save it so we don't test it again
            currentSetsTested.add(frozenset(currentTestCombination))
            newAvailableNodes = list(currentAvailableNodes)
            newAvailableNodes.remove(node)
            bruteForcePaths(currentRemainingPaths,
                            newAvailableNodes,
                            currentSetsTested,
                            currentTestCombination,
                            results,
                            currentLoopId)

            currentTestCombination.remove(node)

    print "-------------------"
    #need to pass "up" the tested sets from this loop
    setsTested.update(currentSetsTested)

    return None

if __name__ == '__main__':

    testPaths = [
        [1,2,14,15,16,18,9,10],
        [1,2,24,25,26,28,9,10],
        [1,2,34,35,36,38,9,10],
        [1,3,44,45,46,48,9,10],
        [1,3,54,55,56,58,9,10],
        [1,3,64,65,66,68,9,10],

        [1,2,14,15,16,7,10],
        [1,2,24,7,10],
        [1,3,34,35,7,10],

        [1,3,44,35,6,10],
        ]


    setsTested = set()
    availableNodes = [2, 3, 6, 7, 9]
    results = list()
    currentTestCombination = set()

    bruteForcePaths(testPaths, availableNodes, setsTested, currentTestCombination, results, 0)

    print "results:"
    for result in sorted(results, key=len):
        print result

更新： 我用itertool重新编写了代码以生成组合。更简洁，更容易处理。现在我们来尝试找出所建议的支配节点和多进程函数。在

^{pr2}$

Answer 1

下面是一个忽略路径列表的答案。它只需要一个网络、一个源节点和一个目标节点，然后找到网络中的最小节点集，而不是源节点或目标节点，因此删除这些节点会断开源节点与目标节点的连接。在

如果我想找到最小边集，我可以通过搜索Max Flow min cut来找到。注意，Wikipedia上的文章http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Generalized_max-flow_min-cut_theorem指出有一个广义的最大流最小割定理，它考虑了顶点容量和边容量，这至少是令人鼓舞的。还请注意，边缘容量以Cuv表示，其中Cuv是从u到v的最大容量。在图中，它们似乎被绘制为u/v。因此，向前方向的边缘容量可能不同于向后方向的边缘容量。在

为了将最小顶点切割问题伪装成最小边切割问题，我建议利用这种不对称性。首先，给所有现有的边一个巨大的容量-例如100倍于图中的节点数。现在用两个顶点Xi和Xo替换每个顶点X，我将其称为传入和传出顶点。对于X和Y之间的每一条边，在Xo和Yi之间创建一条边，现有容量向前，而容量为0，这是单向的。现在为每个X在Xi和Xo之间创建一个边缘，容量1向前，容量0向后。在

现在在结果图上运行max flow min cut。因为所有的原始链路都有巨大的容量，最小割必须全部由容量为1的链路组成（实际上最小割被定义为将一组节点分成两部分：您真正想要的是一组节点对Xi，其中一半是Xi的Xo，另一半是Xo，但是您可以很容易地从另一组中获取一个）。如果断开这些链接，则将图形断开为两部分，就像标准的max flow min cut一样，因此删除这些节点将断开源与目标的连接。因为你有最小的切割，所以这是最小的节点集。在

如果你能找到max flow min cut的代码，比如http://www.cs.sunysb.edu/~algorith/files/network-flow.shtml所指的代码，我希望它能给你最小切割。如果不是，例如，如果你通过解决一个线性规划问题来解决，因为你碰巧有一个线性规划解算器在手边，请注意，例如，从http://www.cse.yorku.ca/~aaw/Wang/MaxFlowMinCutAlg.html中可以看出，当对图进行修改以减去解决方案实际使用的边缘容量时，最小切割的一半是可从源节点访问的集-因此，只要给定在max flow中使用的边缘容量，就可以很容易地找到它。在

Answer 2

编辑：如果您想销毁所有路径，而不是来自给定列表的路径，那么mcdowella解释的最大流技术比这种方法要好得多。在

正如mcdowella所提到的，这个问题一般是NP难的。然而，从您的例子看来，一个精确的方法可能是可行的。在

首先，可以从路径中删除不可删除的所有顶点。然后，通过消除控制顶点来减少实例。例如，每个包含15的路径也包含2，因此删除15是没有意义的。在本例中，如果所有顶点都可用，则2、3、9和35将支配所有其他顶点，因此问题将减少到4个顶点。在

然后从最短路径取一个顶点，递归地分为两种情况：删除它（删除包含它的所有路径）或不删除它（从所有路径中删除它）。（如果路径长度为1，则省略第二种情况。）然后可以再次检查优势度。在

这在最坏的情况下是指数级的，但对于您的示例来说可能已经足够了。在

Answer 3

如果没有提供路径作为问题的一部分，我同意应该有某种方法通过http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem来实现这一点，给定一个足够巧妙的网络结构。但是，因为你没有给出任何关于什么是合理路径和什么不是合理路径的指示，我不得不担心，一个足够恶意的对手可能会找到奇怪的路径集合，而这些路径不是来自任何可能的网络。在

在最坏的情况下，这可能会使你的问题变得像http://en.wikipedia.org/wiki/Set_cover_problem一样困难，在这个意义上，有人可以找到一组路径和节点，这些路径和节点产生了一个路径切割问题，其解可以转化为原始集覆盖问题的解。在

如果是这样的话——我甚至没有试图证明它——你的问题是NP完全的，但是由于你只有100个节点，你在集合封面上找到的许多论文中有可能会指向一种在实践中有效的方法，或者可以为你提供一个足够好的近似值。除了Wikipedia文章，http://www.cs.sunysb.edu/~algorith/files/set-cover.shtml为您指出了两个实现，快速搜索会在http://www.ise.ufl.edu/glan/files/2011/12/EJORpaper.pdf中的一篇论文开头找到以下摘要：

SCP是一个强意义的NP难问题（Garey和Johnson，1979）和许多算法 为解决SCP而开发的。精确算法（Fisher和Kedia，1990；Beasley和 JØrnsten，1992；Balas and Carrera，1996）主要基于分枝定界和分枝切割。 Caprara等人。（2000）比较了SCP的不同精确算法。他们显示出最好的精确性 SCP的算法是CPLEX。因为精确的方法需要大量的计算工作来解决 在大规模SCP实例中，经常使用启发式算法来寻找一个好的或接近最优的解 合理的时间。贪婪算法可能是最自然的启发式方法，以快速解决大型 组合问题。对于SCP，最简单的方法是Chvatal的贪婪算法 （1979年）。贪婪算法虽然简单、快速、易于编码，但却很少能产生好的解决方案 质量。。。。在