python - 使用 Python 在等效图上同时递归

Question

我有一个结构，看起来很像一个图表，但我可以“排序”它。因此，我可以有两张图，它们是等价的，但一张是排序的，另一张是排序的。我的目标是计算一个最小优势集（使用适合我特定问题的自定义算法，因此请不要链接到其他“有效”算法）。

问题是，我搜索大小为 1、然后为 2 等的主导集，直到找到一个。如果没有占主导地位的 size 集i，则使用排序图效率更高。如果有的话，使用未排序的图会好很多。

我考虑过使用线程/多处理，以便同时探索两个图，一旦找到答案（没有解决方案或特定解决方案），另一个停止，我们进入下一步或结束算法。这不起作用，它只会使过程变得更慢（尽管与使用没有线程/多处理的最佳图形相比，我希望它只会使每个步骤所需的时间增加一倍）。

我不知道为什么这不起作用，想知道是否有更好的方法，甚至可能不需要使用线程/多处理，有什么线索吗？

标签： pythonmultithreadingrecursiongraphmultiprocessing

Answer 1

如果您不想要算法建议，那么惰性评估似乎是可行的方法。

在数据结构中设置这两者，class_instance.next_step(work_to_do_this_step)以便类实例是一种图类型的求解器。你需要两个。您可以让每个图表向前移动一个“步骤”（无论您定义的步骤是什么）。通过仔细选择步骤是什么（可能动态地基于事情的进展），您可以有效地在排序和未排序图方法上花费多少工作/时间之间进行切换。当然，这仅在至少有一个算法可能在另一个算法之前完成的情况下才有用。

从理论上讲，如果您可以独立定义这些步骤是什么，那么您可以拆分工作以并行运行它们，但重要的是每个进程/线程正在执行大致相同数量的“工作”，因此它们都完成大致相同时间。尽管为这类事情编写并行算法可能有点棘手。