multistage graph

خوارزمية المخطط متعدد المراحل المناظرة للطريقة التصاعدية

تفترض خوارزمية المخطط متعدد المراحل المناظرة للطريقة التصاعدية ان العقد v مرتبة من 1 الى n وان s تعطى الفهرس 1 ثم تعطى عقد المجموعة v2 فهارس وهكذا حتى t، اي ان الفهارس المعطاة لعقد المجموعة vi+1 تكون اكبر من تلك المعطاة لعقد المجموعة vi.
Algorithm FGraph(G, K, n):
Input:A k-stage digraph G=(V,E) with n vertices indexed
in order of stages.
Output:p, a minimum-cost path.
1. Comment: cost and D are auxiliary arrays.
2. cost[n] 0.0
3. for j n-1 to 1
4. let r be vertex such that <j,r> is an edge of G
and c[j][r]+cost[r] is minimum.
5. cost[j] c[j][r]+cost[r]
6. D[j] r
7. end for
8. p[1] 1; p[k] n
9. for j 2 to k-1
10. p[j] D[p[j-1]]
11.end for
12.return array p
تعقيدات الوقت :
اذا مثل المخطط بقوائم التجاور(adjacency lists) فان r يمكن ايجادها في وقت يتناسب مع درجة العقدة j واذا كان للمخطط من الحواف فان وقت دوارة for الاولى هو ووقت دوارة for الثانية يكون ?(k)، لهذا يكون وقت الخوارزمية الكلي .

الطريقة التناقصية(Backward approach)
تحل هذه الطريقة تصاعديا وكالتالي:



اذا كانت bp(i,j) هو مسار اقل كلفة من العقدة s الى العقدة j في vi وكانت bcost(i,j) هي كلفة المساروبوجود العلاقات اعلاه يمكن حساب bcost(i,j) وذلك بحساب bcost للقيمة i=3 و i=4 وهكذا

bcost(3,6)= min{bcost(2,2)+4, bcost(2,3)+2}=9
bcost(3,7)=11, bcost(3,8)=10, bcost(4,9)=15, bcost(4,10)=14, bcost(4,11)=16, bcost(5,12)=16

D[3,6]=3, D[3,7]=2, D[3,8]=2, D[4,9]=6, D[4,10]=6, D[4,11]=8, D[5,12]=10

v1=1 v2 v3 v4 v5=12

v4=D[5,12]=10, v3 =D[4,D[5,12]]=d[4,10]=6, v2=D[3,D[4,D[5,12]]]=D[3,6]=3

اذن المسار الامثل هو
1, 3, 6, 10, 12

خوارزمية المخطط متعدد المراحل المناظرة للطريقة التناقصية

Algorithm BGraph(G, K, n):
Input: A k-stage digraph G=(V,E) with n vertices indexed
in order of stages.
Output:bp, a minimum-cost path.
1. Comment: bcost and D are auxiliary arrays.
2. bcost[1] 0.0
3. for j 2 to n
4. let r be vertex such that <r,j> is an edge of G
and bcost[r]+c[r][j] is minimum.
5. bcost[j] bcost[r]+c[r][j]
6. D[j] r
7. end for
8. bp[1] 1; bp[k] n
9. for j k-1 to 2
10. bp[j] D[bp[j+1]]
11.end for
12.return array bp
تعقيدات الوقت :
لهذه الخوارزمية نفس تعقيدات وقت الخوارزمية FGraph شرط تمثيل G بقوائم تجاور معكوسة ( اي لكل عقدة v يكون لدينا قائمة عقد w بحيث ).