寻找独立集的算法

1 投票

2 回答

1568 浏览

提问于 2025-04-15 20:06

大家好，

我遇到一个问题。我正在用Python写一个脚本，这个脚本由几个模块组成。有些模块依赖于其他模块，所以这些模块必须在依赖的模块成功运行后才能运行。每个模块都继承自一个基础类模块，并重写了一个叫做DEPENDENCIES的列表，这个列表列出了在运行这个模块之前必须满足的依赖关系。有一个模块需要在所有其他模块之前运行。目前我做的事情是这样的：

modules_to_run.append(a)
modules_to_run.append(b)
modules_to_run.append(c)
.....
.....     
modules_to_run.append(z)


# Very simplistically just run the Analysis modules sequentially in
# an order that respects their dependencies
foundOne = True
while foundOne and len(modules_to_run) > 0:
    foundOne = False
    for module in modules_to_run:
        if len(module.DEPENDENCIES) == 0:
            foundOne = True
            print_log("Executing module %s..." % module.__name__, log)
            try:
                module().execute()
                modules_to_run.remove(module)
                for module2 in modules_to_run:
                    try:
                        module2.DEPENDENCIES.remove(module)
                    except:
                        #module may not be in module2's DEPENDENCIES
                        pass
            except Exception as e:
                print_log("ERROR: %s did not run to completion" % module.__name__, log)
                modules_to_run.remove(module)
                print_log(e, log)

for module in modules_to_run:
    name = module.__name__
    print_log("ERROR: %s has unmet dependencies and could not be run:" % name, log)
    print_log(module.DEPENDENCIES, log)

现在我发现有些模块执行的时间很长，整个脚本的运行时间也太长了。所以我想把它改成多线程，这样独立的模块可以同时运行，从而节省时间。我想要一个解决方案，就是在每次迭代后，我会重新计算'n'个独立模块（'n'是最大线程数，通常从2开始），并让它们并行执行，然后等它们完成后再进行下一次迭代。我对算法不太了解，所以现在卡住了。大家能帮我找一个算法吗？这个算法可以在每次迭代后找到最大'n'个互不依赖的独立模块。

多线程算法优化并行计算模块化设计依赖关系任务调度运行时间优化独立集

2 个回答

根据你的设置描述，你也可以直接这样做。

看起来每个模块都知道自己的依赖关系。然后在每个模块里加一个判断函数，说明它是否可以运行，这样做其实很简单。一个模块只有在它所有的前置依赖都满足的情况下才能运行。

顶层模块没有依赖关系，所以它们可以直接运行。

基本上，这就是一种简单的部分拓扑排序实现（你不需要探索所有的依赖关系图，只需关注顶层的部分）。

有两个需要注意的陷阱：

如果你的依赖关系中有循环（比如A依赖B，B又依赖C，而C又依赖A），那么可能会导致无限循环（这意味着问题没有解决方案）。你应该检测到这种情况并报告错误。

你可以运行的模块数量可能会少于线程的数量。这并不算错误。你找到解决方案的方式要么是当你有n个可用的模块可以运行，要么是当你询问每个模块它们是否可以运行的时候。

回答于 2025-04-15 由 Python大师

分享举报

我最近在一个关于拓扑排序的问题中提到了一些内容，正好碰巧提到了这个话题！从维基百科的文章中可以了解到：

拓扑排序的主要应用是安排一系列的工作或任务；拓扑排序算法最早是在1960年代初期被研究的，当时是为了项目管理中的PERT技术来进行调度（Jarnagin 1960）。在这个过程中，工作被表示为图中的点，如果工作x必须在工作y之前完成，那么就会有一条从x到y的边（比如，洗衣服时，洗衣机必须先完成洗涤，才能把衣服拿去晾干）。通过拓扑排序，我们可以得到一个执行工作的顺序。

大致步骤如下：

建立一个依赖关系图。
找出那些没有依赖关系的模块，这些模块可以现在并行执行。
把这些模块从图中移除。
重复第二步，直到所有工作完成。

想了解更多详细信息，可以查看那些链接。

回答于 2025-04-15 由 Python大师

分享举报

寻找独立集的算法

2 个回答

撰写回答