我正在尝试解决与图论相关的问题，但似乎无法记住/找到/理解正确/最佳方法，因此我想向专家们请教...
我有一组来自两个节点（示例代码中的1和10）的路径列表。 我试图找到去除节点的最小数量以切断所有路径。 我也只能删除某些节点。
我目前已经实现了它（如下所示）作为一种暴力搜索。 在我的测试集上，这很好用，但是在将规模扩大到具有100K路径和100可用节点的图形时，这将成为一个问题（阶乘问题）。 目前，我不关心删除节点的顺序，但我会在某些时候考虑到这一点（在下面的代码中将集合切换为列表）。
我相信应该有一种使用最大流/最小割算法来解决这个问题的方法。 但我读到的所有内容都以某种方式超出了我的头脑。 这类工作已经过了几年（SEVERAL），我似乎什么都想不起来了。
所以我的问题是：
1）是否有更好的方法来解决这个问题，而不是测试所有组合并取最小集？
2）如果有的话，可以解释一下还是最好给出伪代码来帮助解释？ 我猜可能有一个库已经以某种方式执行了这项工作（我最近一直在寻找和使用networkX，但也可选其他库）
3）如果没有（或者即使是），有多线程/进程解决方案的建议吗？ 我想尽可能地从计算机中获得每一点性能。 （我已经找到了一些好的线程关于这个问题，只是还没有时间实现，所以我想在同一时间问一下。我首先想让所有东西都正常工作，然后再进行优化。）
4）使代码更符合“Pythonic”的一般建议（可能还有助于性能）。 我知道可以做出改进，并且对Python仍然很陌生。
谢谢帮助。
我有一组来自两个节点（示例代码中的1和10）的路径列表。 我试图找到去除节点的最小数量以切断所有路径。 我也只能删除某些节点。
我目前已经实现了它（如下所示）作为一种暴力搜索。 在我的测试集上，这很好用，但是在将规模扩大到具有100K路径和100可用节点的图形时，这将成为一个问题（阶乘问题）。 目前，我不关心删除节点的顺序，但我会在某些时候考虑到这一点（在下面的代码中将集合切换为列表）。
我相信应该有一种使用最大流/最小割算法来解决这个问题的方法。 但我读到的所有内容都以某种方式超出了我的头脑。 这类工作已经过了几年（SEVERAL），我似乎什么都想不起来了。
所以我的问题是：
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
更新： 我使用itertools重构了代码来生成组合，这使得代码更清晰、更快(应该更容易进行多进程处理)。现在尝试实现建议中的主导节点并多进程化函数。
def bruteForcePaths3(paths, availableNodes, results):
#start by taking each combination 2 at a time, then 3, etc
for i in range(1,len(availableNodes)+1):
print "combo number: %d" % i
currentCombos = combinations(availableNodes, i)
for combo in currentCombos:
#get a fresh copy of paths for this combiniation
currentPaths = list(paths)
currentRemainingPaths = []
# print combo
for node in combo:
#determine better way to remove nodes, for now- if it's in, we remove
currentRemainingPaths = [path for path in currentPaths if not (node in path)]
currentPaths = currentRemainingPaths
#if there are no paths left
if len(currentRemainingPaths) == 0:
#save this combination
print combo
results.append(frozenset(combo))
return None