计算机问题求解一论题4.8 优化问题的近似解 陶先平 2017年5月8日
计算机问题求解—论题4.8 优化问题的近似解 陶先平 2017年5月8日
生产调度问题的一个近似解 Algorithm 4.2.1.3 (GMS (GREEDY MAKESPAN SCHEDULE)). Input:I=(p1,...,Pn,m),n,m,p1,...,Pn positive integers and m2. Step 1:Sort p1,...,Pn. To simplify the notation we assume p1≥p2≥.≥pn in the rest of the algorithm. Step 2:for i=1 to m do begin Ta={); Time(T:):=Pi end [In the initialization step the m largest jobs are distributed to the m machines.At the end,Ti should contain the indices of all jobs assigned to the ith machine for i=1,...,m.} Step 3:for i=m+1 to n do begin compute an I such that Time(T):=min{Time(Til1≤j≤m T:=nUi): Time(T):=Time(Ti)+pi end Output:(T1,T2,...,Tm)
生产调度问题的一个近似解
算法图例： cost(GMS(I)) P1 P2 Pk
算法图例：
这段文字中的quality是什么意思？ mally and roughly,an approximation algorithm for an optimization problem is an algorithm that provides a feasible solution whose quality does not differ too much from the quality of an optimal solution. 这个公式中的cost是什么意思？ EA(x)= cost(A(x)）-Optu(x Optu(x)
这段文字中的quality是什么意思？ 这个公式中的cost是什么意思？
问题1 n代表什么意思？ For any n E N,we define the relative error of A as eA(n)=max{EA(x)x∈Lr∩（∑r)"}. For every x E LI,the approximation ratio RA(x)of A on x is defined as aa=mr{智a}-
问题1 n代表什么意思？