回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我想解决一个与图论有关的问题,但似乎记不起/找到/理解正确的/最好的方法,所以我想我应该问问专家。。。在</p>
<p>我有两个节点(示例代码中为1和10)的路径列表。我正在尝试找到要删除的最小节点数,以切断所有路径。我也只能删除某些节点。在</p>
<p>我目前已经实现了(下面)作为一个暴力搜索。这在我的测试集上运行得很好,但是当扩展到路径为100K且可用节点为100的图时,这将成为一个问题(阶乘问题)。现在,我不关心移除节点的顺序,但我会在某个时候考虑到这一点(在下面的代码中要列出开关集)。在</p>
<p>我认为应该有一种方法来解决这个问题,使用最大流量/最小切割算法。不过,我读到的每一件事都在某种程度上超出了我的想象。做这种事已经好几年了,我好像什么都记不起来了。在</p>
<p>所以我的问题是:</p>
<p>1)除了测试所有的组合和取最小的集合之外,有没有更好的方法来解决这个问题?在</p>
<p>2)如果是这样的话,你能解释一下吗?还是最好给出伪代码来帮助解释?我猜可能有一个库已经在某种程度上做到了这一点(我最近一直在寻找并使用networkX,但对其他人开放)</p>
<p>3)如果不是(或甚至是),建议如何多线程/进程解决方案?我想尽量从电脑中得到我能得到的每一点性能。(我在这个问题上找到了一些很好的线索,但我还没有机会去实现,所以我想我会同时问这个问题,只是碰巧而已。在优化之前,我首先想让一切正常运行。)</p>
<p>4)关于使代码更“Pythonic”的一般建议(可能也有助于提高性能)。我知道我可以做一些改进,而且对Python还是个新手。在</p>
<p>谢谢你的帮助。在</p>
<pre><code>#!/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.<a href="https://www.cnpython.com/list/append" class="inner-link">append</a>(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
</code></pre>
<p>更新:
我用itertool重新编写了代码以生成组合。更简洁,更容易处理。现在我们来尝试找出所建议的支配节点和多进程函数。在</p>
^{pr2}$