当前位置：文江博客话题详情

什么是超越贪婪算法的有效方法

发布于 2024-07-19 15:54:49 字数 529 浏览 9 评论 0原文

这个问题的领域是在受限硬件上调度操作。结果的分辨率是调度所适应的时钟周期数。搜索空间增长非常迅速，早期决策限制了未来决策，并且可能的调度总数快速呈指数增长。许多可能的调度是等效的，因为仅交换两个指令的顺序通常会导致相同的时序约束。

基本上，问题是在不花费太多时间的情况下探索广阔的搜索空间的好策略是什么。我希望只搜索一小部分，但希望在这样做的同时探索搜索空间的不同部分。

当前的贪婪算法有时往往会在早期做出愚蠢的决定，并且分支定界的尝试速度非常慢。

编辑：想要指出的是，结果是非常二元的，贪婪算法可能最终使用 8 个周期，而存在使用分支定界仅使用 7 个周期的解决方案。

第二点是指令之间的数据路由和指令之间的依赖关系存在显着的限制，这限制了解决方案之间的通用性。将其视为具有大量排序约束的背包问题，以及一些由于路由拥塞而完全失败的解决方案。

澄清：在每个周期中，每种类型的操作数量都有限制，并且某些操作有两种可能的类型。有一组路由约束，可以变化为相当严格或相当宽松，并且限制取决于路由拥塞。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

浅笑轻吟梦一曲 2024-07-26 15:54:49

NP 难题的整数线性优化

根据您的侧面约束，您也许可以使用关键路径方法或
（如先前答案中所建议）动态编程。但是许多调度问题都是 NP 困难的，就像经典的旅行推销员一样——精确的解决方案具有指数搜索时间的最坏情况，正如您在问题中所描述的那样。

重要的是要知道，虽然 NP 困难问题仍然有一个非常糟糕的最坏情况解决时间，但有一种方法通常可以通过非常短的计算产生精确的答案（平均情况） > 是可以接受的，并且您通常不会看到最坏的情况）。

这种方法是将您的问题转换为具有整数变量的线性优化问题。有一些免费软件包（例如 lp-solve）可以有效地解决此类问题。

这种方法的优点是它可以在可接受的时间内为您提供 NP 难题的准确答案。我在几个项目中使用了这种方法。

由于您的问题陈述未包含有关侧面约束的更多详细信息，因此我无法更详细地介绍如何应用该方法。

编辑/添加：示例实现

以下是有关如何在您的案例中实现此方法的一些详细信息（当然，我做了一些假设，可能不适用于您的实际问题 --- 我只知道细节形成你的问题）：

假设你有 50 条指令 cmd(i) (i=1..50) 被安排在 10 个或更少的周期 Cycle(t) (t=1..10) 中。我们引入了 500 个二进制变量 v(i,t) (i=1..50; t=1..10)，它们指示指令 cmd(i) 是否在 Cycle(t) 执行。这个基本设置给出了以下线性约束：

v_it integer variables
0<=v_it; v_it<=1;       # 1000 constraints: i=1..50; t=1..10
sum(v_it: t=1..10)==1   # 50 constraints:   i=1..50

现在，我们必须指定您的附加条件。假设操作 cmd(1)...cmd(5) 是乘法运算，并且您恰好有两个乘法器 --- 在任何循环中，您最多可以并行执行其中两个操作：

sum(v_it: i=1..5)<=2    # 10 constraints: t=1..10

对于每个资源，需要添加相应的约束。

另外，我们假设操作 cmd(7) 依赖于操作 cmd(2) 并且需要在它之后执行。为了使方程更有趣一点，我们还要求它们之间有两个周期间隙：

sum(t*v(2,t): t=1..10) + 3 <= sum(t*v(7,t): t=1..10)   # one constraint

注意：sum(t*v(2,t): t=1..10) 是周期 t，其中 v(2,t ) 等于一。

最后，我们希望最大限度地减少循环次数。这有点棘手，因为按照我建议的方式你会得到相当大的数字：我们给每个 v(i,t) 分配一个随时间呈指数增长的价格：将操作推迟到未来比提前执行它们要昂贵得多：

sum(6^t * v(i,t): i=1..50; t=1..10) --> 最低限度。 # 一个目标函数

我选择 6 大于 5，以确保向系统添加一个周期比将所有内容压缩到更少的周期中更昂贵。副作用是该程序将不遗余力地尽早安排操作。您可以通过执行两步优化来避免这种情况：首先，使用此目标函数找到所需周期的最小数量。然后，使用不同的目标函数再次提出相同的问题——从一开始就限制可用周期的数量，并对以后的操作施加更温和的价格惩罚。你必须玩这个，我希望你明白了。

希望您可以将所有要求表达为二进制变量中的此类线性约束。当然，可能有很多机会可以利用您对特定问题的洞察力来减少约束或变量。

然后，将您的问题交给 lp-solve 或 cplex，让他们找到最佳解决方案！

Integer linear optimization for NP-hard problems

Depending on your side constraints, you may be able to use the critical path method or
(as suggested in a previous answer) dynamic programming. But many scheduling problems are NP-hard just like the classical traveling sales man --- a precise solution has a worst case of exponential search time, just as you describe in your problem.

It's important to know that while NP-hard problems still have a very bad worst case solution time there is an approach that very often produces exact answers with very short computations (the average case is acceptable and you often don't see the worst case).

This approach is to convert your problem to a linear optimization problem with integer variables. There are free-software packages (such as lp-solve) that can solve such problems efficiently.

The advantage of this approach is that it may give you exact answers to NP-hard problems in acceptable time. I used this approach in a few projects.

As your problem statement does not include more details about the side constraints, I cannot go into more detail how to apply the method.

Edit/addition: Sample implementation

Here are some details about how to implement this method in your case (of course, I make some assumptions that may not apply to your actual problem --- I only know the details form your question):

Let's assume that you have 50 instructions cmd(i) (i=1..50) to be scheduled in 10 or less cycles cycle(t) (t=1..10). We introduce 500 binary variables v(i,t) (i=1..50; t=1..10) which indicate whether instruction cmd(i) is executed at cycle(t) or not. This basic setup gives the following linear constraints:

v_it integer variables
0<=v_it; v_it<=1;       # 1000 constraints: i=1..50; t=1..10
sum(v_it: t=1..10)==1   # 50 constraints:   i=1..50

Now, we have to specify your side conditions. Let's assume that operations cmd(1)...cmd(5) are multiplication operations and that you have exactly two multipliers --- in any cycle, you may perform at most two of these operations in parallel:

sum(v_it: i=1..5)<=2    # 10 constraints: t=1..10

For each of your resources, you need to add the corresponding constraints.

Also, let's assume that operation cmd(7) depends on operation cmd(2) and needs to be executed after it. To make the equation a little bit more interesting, lets also require a two cycle gap between them:

sum(t*v(2,t): t=1..10) + 3 <= sum(t*v(7,t): t=1..10)   # one constraint

Note: sum(t*v(2,t): t=1..10) is the cycle t where v(2,t) is equal to one.

Finally, we want to minimize the number of cycles. This is somewhat tricky because you get quite big numbers in the way that I propose: We give assign each v(i,t) a price that grows exponentially with time: pushing off operations into the future is much more expensive than performing them early:

sum(6^t * v(i,t): i=1..50; t=1..10) --> minimum. # one target function

I choose 6 to be bigger than 5 to ensure that adding one cycle to the system makes it more expensive than squeezing everything into less cycles. A side-effect is that the program will go out of it's way to schedule operations as early as possible. You may avoid this by performing a two-step optimization: First, use this target function to find the minimal number of necessary cycles. Then, ask the same problem again with a different target function --- limiting the number of available cycles at the outset and imposing a more moderate price penalty for later operations. You have to play with this, I hope you got the idea.

Hopefully, you can express all your requirements as such linear constraints in your binary variables. Of course, there may be many opportunities to exploit your insight into your specific problem to do with less constraints or less variables.

Then, hand your problem off to lp-solve or cplex and let them find the best solution!

回复收藏 0 原文