相关疑难解决方法(0)

我正在考虑为我想解决的一个问题利用并行性.问题大致如下:给定输入(点序列)找到最佳输出(由这些点组成的最大三角形,最长线等).在点序列中有3种不同的"形状",但我只对"最佳得分"(通常是某种形式的"长度"倍数系数)感兴趣.我们称之为形状S1,S2,S3.

我有2种不同的算法来解决S1 - 'S1a'在O(n ²)中,'S1b'大多表现得更好,但最坏的情况是O(n ⁴).

第一个问题:是否有一些简单的方法可以并行运行S1a和S1b,使用先完成并停止另一个的方法？至于我正在阅读文档,这可以使用一些forkIO编程并在获得结果时杀死线程 - 只是询问是否有更简单的东西？

第二个问题 - 更加困难:我以这种方式调用优化函数:

optimize valueOfSx input

valueOfSx特定于每个形状,并返回"得分"(或得分的猜测)可能的解决方案.优化调用此函数以找出最佳解决方案.我感兴趣的是:

s1 = optimize valueOfS1 input
s2 = optimize valueOfS2 input
s3 = optimize valueOfS3 input
<- maximum [s1,s2,s3]

但是,如果我知道S1的结果,我可以丢弃所有较小的解决方案,从而使s2和s3收敛得更快,如果不存在更好的解决方案(或者至少丢弃最差的解决方案,从而提高空间效率).我现在在做的是:

zeroOn threshold f = decide .f
    where decide x = if (x < threshold) then 0 else x
s1 = optimize valueOfS1 input
s2 = optimize (zeroOn s1 valueOfS2) input
s3 = optimize (zeroOn (max s1 s2) valueOfS3) input

现在的问题是:我能以这样的方式如运行S2和S3并行,无论哪完成第一次将更新其他线程运行的得分功能的"门槛"参数？在某种意义上的东西:

threshold = 0 …