考虑以下标记为 A、B、C、D 的重叠图像的示例结构。可能的重叠用灰色标记：

该结构可以用加权无向图表示（图像是节点，边表示重叠，权重表示重叠区域或处理它们所需的时间）：

图像将在表面上渲染，而重叠则需要额外的处理（例如平均像素以获得透明度）。

例如，我们可以决定先合并 A,B。情况变成：

每次合并后，必须更新图形。在这种情况下，只有图像 C、D 将被合并，算法以单个合成图像结束。

您可以观察到，如果合并算法并行运行，它现在可以同时处理 C 和 D。

但是，如果我们先开始合并 A、C，那么 B 和 D 被阻塞，算法只能顺序运行（考虑到单个图像可以由单个线程使用/不能共享）。

给定图表，我想安排并行计算$N$计算单元（例如 CPU 内核）。

时间表为$N=2$看起来像这样

iteration #1
    core 1: A-B
    core 2: waiting
iteration #2
    core 1: (A-B)C
    core 2: (A-B)D

我认为调度程序应该针对两个目标：

1. 最小化迭代次数（即在任何给定时间利用最大数量的核心）
2. 在任何给定的迭代中平衡所有内核的负载（即为它们分配大致相同的重叠区域，以便它们大致同时完成；不必要的等待会破坏并行计算的好处）。

第一个目标很重要，而第二个目标是“很高兴”（处理重叠所需的时间与其面积成正比）。

我遇到了两个主要问题：

• 使用什么算法？通过存储当前最佳解决方案进行回溯？
• 安排任务是否更容易$N=\infty$（最大化并行性）而不是$N$是否对应于可用的实际处理单元数量？
• 只有图像对之间的重叠区域是已知的，但是由于图像在过程中被合并，如何计算新的重叠（例如C（AB））？

算法的贪心版本如下所示：

Grab as much overlapping image pairs as possible such that no two pairs themselves are overlapping.
Sort the pairs in N bins such that each bin contains roughly same total area.
Merge images in parallel.
Update graph and repeat until single node remains.

我知道这个问题可能太宽泛了。我相信这个问题在并行计算项目中肯定已经解决了很多次了，所以很多来自并行计算领域的人应该有一些直接的想法和提示。

解决后，我计划写一个详尽的答案以使您也受益。但首先我需要一些东西来开始。谢谢。