时间戳

首页 > 解决方案 > 负相关程序的一个例子

c++ - 负相关程序的一个例子

问题描述

我正在寻找构建 2 个负相关函数，这意味着例如

void program()
{
   f1(x);
   f2(x);
}

f1和f2函数都依赖于输入x ，我希望当f1的执行时间增加时，f2应该减少，反之亦然。

我将参数x视为随机生成的数组，将f1视为排序算法。但是，我想不出f2的例子。

谁能给我一个这样的功能对的例子？

编辑 1：实际上我为我的需要找到了f1和f2的示例。最初我忘了提到那些函数需要是现实的，这意味着我不是在每个函数中寻找一个简单的sleep()调用。我还写了x以表示一些“抽象”输入，它可以是现实中的任何东西。

我分别构建f1和f2如下：

void f1(x)
{
   //sort first x elements of an array
}

void f2(x)
{
   //sort last MAXSIZE - x elements of an array
}

这样，如果我在每次试验中随机创建一个数组和一个x ， f1和f2将执行完全负相关，并且f1和f2成为现实程序。下面分别是 f1 和 f2 的执行时间的相关图。

负相关函数

标签： c++calgorithm

解决方案

如果 f1() 是一个 O(nlogn) 排序过程，这将要求 f2() 是一个 O(1/(nlogn)) 过程。随着输入量的增加，这样的过程会变得更容易。我从未听说过这样的算法（不是说不存在）。

如果总执行时间有一些自然上限，f2() 可以等待一段时间 = UPPER_BOUND - f1() 执行时间的估计值。如果 f1() 对某个 k 有执行时间 knlogn，那么

void f2(x)
{
sleep (UPPER_BOUND - k * size(x) * log(size(x)));
}

似乎工作。

f1() 和 f2() 不是独立程序而是一起处理某个程序的情况是不同的。在这里，我正在考虑一个问题，例如 AI 搜索，它可以以正向链接方式或以反向链接方式进行。

如果 f1() 是通过前向链接https://en.wikipedia.org/wiki/Forward_chaining尝试到达目标节点，而 f2() 是通过后向链接https://en.wikipedia.org/wiki/Forward_chaining尝试将目标节点置于公理集中/en.wikipedia.org/wiki/Backward_chaining以便 f1() 和 f2() 一起尝试解决搜索，然后人们可能希望f1() 和 f2() 具有所需的行为。

如果 f1() 和 f2() 并行运行，那么如果问题对于 f1() 来说很容易，那么对于 f2() 来说就会很困难，反之亦然，因为搜索难度不会是对称的。

这类似于双向搜索问题。事实上，经过反思，这是一个比乍看起来更具问题的问题，因为它可以深入了解整个双向搜索问题的行为。

双向搜索的动机是 f1() 和 f2() 会以某种方式“在中间相遇”（参见 Bratko https://slideplayer.com/slide/3351420/），这意味着它们之间的通信

在此处输入图像描述

在您描述的情况下，我认为 f1() 和 f2() 不能同时进行通信，但又是不同的程序，但是如果一个方向的分支因子与另一个方向非常不同，但对于最便宜的方向一开始是未知的。

推荐阅读