Dynamic programming question

I am stuck with one of the algorithm homework problem. Can anyone give me some开发者_运维百科 hint to solve it? Here is the question:

Consider a chain structured computation represented by a weighted graph G = (V;E) where V = {v1; v2; ... ; vn} and E = {(vi; vi+1) such that 1<= i <= n-1. We are also given a chain-structure m identical processors P = {P1; ... ; Pm} (i.e., there exists a communication link between Pk and Pk+1 for 1 <= k <= m - 1).

The set of vertices V represents computation modules, and the set of edges E represents communication between the two modules. Each node vi is assigned a weight wi denoting the execution time of the module on a single processor. Each edge (vi; vi+1) is assigned a weight ci denoting the amount of communication time between the two modules if they are assigned two different processors. If multiple modules are assigned to the same processor, the modules assigned to the same processor must be consecutive. Suppose modules va; va+1; .. ; vb are assigned to Processor Pk. Then, the time taken by Pk, denoted by Tk, is the time to compute assigned modules plus the time to communicate between neighboring processors. Hence, Tk = wa+...+ wb + ca-1 + cb. Note here that ca-1 = 0 if a = 1 and cb = 0 if b = n.

The objective of the problem is to find an assignment V to P such that max1<=k<=m Tk is minimized, where we assume that each processor must take at least one module. (This assumption can be relaxed by adding m dummy modules with zero weight on computational and communication time.) Develop a dynamic programming algorithm to solve this problem in polynomial time(i.e O(mn))

I tried to find the minimum execution time for each Pk and then find the max, but I doubt my solution is dynamic programming since there is no recursive formula. Please give me some hints! Thanks!

I think you might be able to modify the Viterbi algorithm to solve this problem.

okay. this is easy. decompose your problem to be a function you need to minimise, say F(n,k). which results into the minimum assignment of the first n nodes to k first processors. Then derive your formula like this, collecting the number of nodes on the kth processor.

F(n,k) = min[i=0..n]( max(F(i,k-1), w[i]+...+w[n]+c[i-1]+c[n]) )
c[0] = 0
F(*,0) = inf
F(0,*) = inf