Multistage Graph

Beberapa point tentang Multistage Graph yang saya garis bawahi dari berbagai referensi :

  • Multistage Graph G = (V,E) adalah sebuah graph berarah yang bentuknya dibagi dalam k ≥ 2 disjoint set V1, 1 ≤ i ≤ k  (atau Graph yang terdiri dari beberapa stage , CMIIW :)  )
  • | V1 | = | Vk | = 1
  • s (sumber) = V1 dan t (Muara)  = Vk
  • Biaya suatu path dari s ke t adalah jumlah biaya edge-edge pada suatu path.
  • Inti masalah dari Multistage Graph yaitu mencari biaya minimum path dari s ke t.

  • Setiap himpunan V1 menentukan sebuah stage dalam graph.

Ada 2 cara untuk mencari biaya minimum pada Multistage Graph yaitu :

  • Backward approach
  • Foward approach

Cara untuk mencari solusi dengan cara Backward approach (pendekatan kebelakang yang berarti dari s ke t ) yaitu :

Sedangkan secara Foward approach (pendekatan kedepan yang berarti dari t ke s ) yaitu :

0O0

Berikut ini adalah contoh penyelesaian untuk mencari biaya minimum berdasarkan Multistage Graph diatas🙂

:: Backward approach ::

STEP 1

BCOST (1,1) = 0

STEP II

BCOST (2,3) = 7

BCOST (2,4) = 3

BCOST (2,5) = 2

STEP III

BCOST (3,7)

= min { BCOST(2,2) + C(2,7), BCOST(2,3) + C(3,7), BCOST(2,5) + C(5,7) }

= min { 9+2, 7+7, 2+11 } = 11 -> the path 1 – 2 – 7

BCOST (3,8)

= min { BCOST(2,2) + C(2,8), BCOST(2,4) + C(4,8), BCOST(2,5) + C(5,8) }

= min { 9+1, 3+11, 2+8 } = 10 -> the path 1 – 2 – 8  atau  1 – 5 – 8

STEP IV

BCOST (4,9)

= min { BCOST(3,6) + C(6,9), BCOST(3,7) + C(7,9) }

= min { 9+6, 11+4 } = 15 -> the path 1 – 3 – 6 – 9 atau 1 –  2 – 7 – 9

BCOST (4,10)

= min { BCOST(3,6) + C(6,10), BCOST(3,7) + C(7,10), BCOST(3,8) + C(8,10) }

= min { 9+5, 11+3, 10+5 } = 14 -> the path 1-3-6-10 atau 1-2-7-10

BCOST (4,11)

= min { BCOST(3,8) + C(8,11) }

= min { 10 + 6 } = 16 -> the path 1-5-8-11


STEP V

BCOST (5,12)

= min {BCOST(4,9) + C(9,12), BCOST(4,10) + C(10,12), BCOST(4,11)+C(11,12)}

= min { 15+4, 14+2, 16+5 } = 16 -> the path 1-2-7-10-12 atau 1-3-6-10-12


:: Foward approach ::

STEP 1

COST (4,9) = 4

COST (4,10) = 2

COST (4,11) = 5

STEP II

COST (3,6)

= min { C(6,9) + COST(4,9), C(6,10) + COST(4,10) }

= min { 6+4, 5+2 } = 7 -> the path 6 – 10 – 12

COST (3,7)

= min { C(7,9) + COST(4,9), C(7,10) + COST(4,10) }

= min { 4+4, 3+2 } = 5 -> the path 7 – 10 -12

COST (3,8)

= min { C(8,10) + COST(4,10), C(8,11) + COST(4,11) }

= min { 5+2, 6+5 } = 7 -> the path 8 – 10 – 12

STEP III

COST (2,2)

= min { C(2,6) + COST(3,6), C(2,7) + COST(3,7), C(2,8) + COST(3,8) }

= min { 4+7, 2+5, 1+7 } = 7 -> the path 2 – 7 – 10 – 12

COST (2,3)

= min { C(3,6) + COST(3,6), C(3,7) + COST(3,7) }

=min { 2+7, 7+5 } = 9 ->  the path 3 – 6 – 10 – 12

COST (2,4)

= min { C(4,8) + COST(3,8) }

= min { 11+7} = 18 ->  the path 4 – 8 – 10 – 12

COST (2,5)

= min { C(5,7) + COST(3,7), C(5,8) + COST(3,8) }

= min { 11+5, 8+7 } = 15 ->  the path 5 – 8 – 10 – 12

STEP IV

COST (1,1)

= min { C(1,2) + COST(2,2), C(1,3) + COST(2,3), C(1,4) + COST(2,4), C(1,5) + COST(2,5) }

= min { 9+7, 7+9, 3+18, 2+15 }

= 16 ->  the path 1 – 2 – 7 – 10 – 12 atau 1 – 3 – 6 – 10 – 12

0 Responses to “Multistage Graph”



  1. Tinggalkan sebuah Komentar

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s




Me (^^)

About

Blog ini adalah catatan kuliah ku, tidak hanya mengenai materi kuliah tetapi juga tentang kegiatan, pengalaman aku selama kuliah :) .


=-=-=-=-=
image header = "Byousoku 5 cm " with edited :)

Liroesdy on Net (=^_^=)

Blog Stats

  • 59,078 hits
Click to view my 

Personality Profile page

My Personal Blog

Liroesdy Blog

Liroesdy Lab

Liroesdy Lab

%d blogger menyukai ini: