动态规划问题

Question

我被其中一个算法作业问题所困扰。有人能给我一些提示来解决这个问题吗？下面是问题：

考虑由加权图G= (V;E)表示的链式结构化计算，其中V= {v1；v2；...；vn}且E= {(vi；vi+1)使得1<= i <= n-1。我们还给出了链结构m个相同的处理器P= {P1；...；Pm} (即，对于1 <= k <= m-1，在Pk和Pk+1之间存在通信链路)。

顶点集合V表示计算模块，边集合E表示两个模块之间的通信。每个节点vi被分配一个权重wi，该权重wi表示模块在单个处理器上的执行时间。每个边(vi；vi+1)被分配一个权重ci，该权重ci表示如果两个模块被分配了两个不同的处理器，则两个模块之间的通信时间量。如果将多个模块分配给同一处理器，则分配给同一处理器的模块必须是连续的。假设模块va；va+1；..；vb被分配给处理器Pk。然后，Pk所用的时间，用Tk表示，是计算分配的模块的时间加上相邻处理器之间通信的时间。因此，Tk = wa+...+ wb + ca-1 + cb。请注意，如果a=1，则ca-1 =0；如果b= n，则cb =0。

问题的目标是找到一个分配V到P，使得max1<=k<=m Tk最小化，其中我们假设每个处理器必须至少取一个模块。(可以通过添加m个在计算和通信时间上没有权重的虚拟模块来放松这一假设。)开发一个动态规划算法来在多项式时间内解决这个问题(即O(mn))

我试图找到每个Pk的最小执行时间，然后找到最大值，但我怀疑我的解决方案是动态编程，因为没有递归公式。请给我一些提示！谢谢!

Answer 1

我认为你可以修改Viterbi算法来解决这个问题。