Posted by: paulusharsono | May 27, 2009

PENYELESAIAN MUNDUR

PENYELESAIAN MUNDUR.

Pada umumnya dalam menyelesaikan suatu permasalahan diselesaikan dengan cara maju (forward solution);  artinya dimulai dari  awal yang betul-betul dari kosong hingga terselesaikannya masalah tersebut.

Tetapi dalam hal-hal tertentu terutama dalam mencari penyelesaian masalah optimasi, ada cara lain dalam menyelesaikannya, yaitu dengan penyelesaian mundur (backward solution).  Dalam penyelesaian mundur, dianggap masalah telah terselesaikan . Selanjutnya ditelusuri secara mundur sampai pada awal dari permasalahan.

Sebagai gambaran akan diketengahkan  tiga buah masalah, satu diantaranya ada kaitannya dengan permainan.

Masalah pertamaBermain dengan batang korek api.

Ada sejumlah batang korek api, kira-kira 50 batang yang disebar diatas meja.  Dua orang bermain dengan aturan,  yang bermain diharuskan mengambil satu, dua atau tiga batang korek api dari atas meja tersebut.  Pengambilan batang korek api  ini dilakukan oleh dua orang pemain secara bergantian.  Pemain yang mengambil terakhir, dinyatakan kalah.

Masalahnya adalah : Bagaimana teknik kita bermain agar kita menang.

Terlepas dari siapa yang mulai mengambilnya, yang terpenting adalah kita jangan sampai mengambil batang korek api terakhir. Artinya pengambilan terakhir harus lawan main kita.

Kita selesaikan secara mundur;  sebelum permainan berakhir, kita harus menyisakan satu batang. Mengapa, karena lawan bermain kita harus mengambilnya.  Apabila kita tinggalkan 2 batang, dia akan mengambil 1;  berarti kita kalah.

Permainan sebelumnya, kita menyisakan 5 batang;  bila dia mengambil 1 batang, kita ambil 3, dan sisa 1. Bila dia mengambil 2, kita ambil 2 ; dan bila dia ambil 3, kita ambil 1. Sehingga sebelum permainan terakhir batang korek api tersisa 1.

Permainan sebelumnya lagi, kita sisakan 9 ( yaitu 5+4) . Permainan selanjutnya dilakukan seperti sebelumnya. Kalau dia  ambil 1, kita ambil 3 dan seterusnya.

Sebelum ini, batang korek api disisakan 9+4=13.

Sebelumnya lagi disisakan 13+4=17.

Jadi dalam bermain dengan penyelesaian mundur ini strategi kita dalam bermain agar menang, adalah menyisakan batang korek api sejumlah berturut-turut  40, 37, 33, 29, 25, 21, 17, 13, 9, 5, terakhir 1.

Cari kesempatan sedini mungkin sebelum lawan kita bermain menemukan peneyelesaiannya untuk menang. Maksudnya, kita mencari kesempatan untuk secepatnya menyisakan batang korek api seperti deretan bilangan tersebut. Semakin cepat, semakin yakin bahwa kita akan menang.

Selamat mencoba.

 

Masalah ke duaAda  gelas ukuran dengan takaran 900 cc dan 400 cc.  Kalau kita membutuhkan 600 cc;  bagaimana menakarnya  dengan menggunakan  kedua gelas ukuran tersebut ? 

Masalah ini juga bisa kita selesaikan dengan penyelesaian mundur.

Dari kedua gelas ukuran tersebut, 600 cc hanya bisa ditempatkan di gelas ukuran 900 cc  ( tak muat di gelas ukuran 400 cc). Dengan penyelesaian mundur, diasumsikan hal ini telah dicapai. Kita mundur terus-menerus sehingga sampai kondisi salah satu gelas ukuran (tentu saja yang besar) terisi penuh; yaitu 900 cc.

Dengan demikian di gelas ukuran 900 cc memuat 600 cc. Apabila gelas ukuran yang 400 cc diisi penuh, dan dituangkan ke ukuran 900 cc yang telah terisi 600 cc hingga penuh, maka gelas ukuran 900 cc berisi penuh dan yang 400 cc tinggal memuat 100 cc

Gelas ukuran 900 cc dikosongkan; 100 cc yang di gelas ukuran 400 cc dituang ke gelas ukuran 900 cc.  Gelas ukuran 900 berisi 100 cc dan gelas ukuran 400 cc kosong.

Isi lagi gelas ukuran 400 cc ini hingga penuh, dan tuangkan ke gelas ukuran 900 cc. Gelas ukuran 900 cc berisi 500 cc dan gelas ukuran 400 cc kosong.

Isi gelas ukuran 400 cc yang kosong ini hingga penuh. Tuangkan ke gelas ukuran  900 cc.  Gelas ukuran 900 cc penuh dan gelas ukuran 400 cc menjadi kosong.

Perhatikan Tabel Isi dari gelas ukuran 900 cc dan 400 cc ini dari penyelesaian mundur tersebut. 

                                     UKUR1

Hitungan diatas adalah persiapannya. Dalam pelaksanaannya untuk bisa menghasilkan 600 cc zat cair  dimulai dari kedua gelas ukuran dalam keadaan kosong.  Kalau dalam penyelesaian kita dilakukan secara mundur, dalam melakukan  pengisian gelas ukuran dari bawah ke atas atau secara maju.

Masalah ke tigaMencari jarak terpendek

Akan dicari jarak terpendek dari simpul A ke simpul J pada graph berarah berikut.

DINAMIK

Simpul-simpul dalam graph tersebut kita bagi dalam beberapa tahap.

Tahap 1 adalah simpul A ; tahap 2 simpul B, C, dan D ; tahap 3 simpul E, F, dan G ; tahap 4 simpul H dan I dan yang terakahir tahap 5 adalah simpul J.

D1

f4 (H) dan f4 (I) adalah notasi  dari berturut-turut  jarak terpendek dari simpul H dan I yang berada di tahap 4 ke simpul J.

Jadi,

                                                            A4

Sedangkan  f3 (G) menunjukkan notasi dari  jarak terpendek dari simpul G yang berada di tahap 3 ke simpul J dengan

                                                            A3

 f3 (E) menunjukkan jarak terpendek dari simpul E (di tahap 3) ke simpul J . (perhatikan tanda *)

                                                          C1

Jadi jarak terpendek dari simpul E ke J sama dengan 4, dengan rute E-H-J

Dengan keterangan seperti diatas untuk  f3 (F) dan f3 (G) yang berada di

tahap 3

                                                      C2

Jarak terpendek dari simpul F ke J sama dengan 7,  dengan rute F-I-J

                                                     C3

Dan jarak terpendek dari simpul G ke J sama dengan 6, dengan rute G-H-J

Sesudah sampai tahap  3 berakhir, mundur ke tahap 2.  Tahap 2 terdiri dari simpul B, C dan D. Dengan demikian :

                                              B1

Jadi di tahap 2 dari simpul B ke simpul J jarak terpendeknya 11, dengan rute B-E-H-J atau B-F-I-J.

Dan dari simpul C

                                               B2

Di tahap 2 dari simpul C ke simpul J jarak terpendeknya 7,

dengan rute C-E-H-J       

Dan dari simpul D                                       

                                                B3

Di tahap 2 dari simpul D ke simpul J jarak terpendeknya 8, dengan rute 

D-E-H-J atau D-F-I-J.       

 Dan yang terakhir di tahap pertama 

       B4

Dengan demikian bisa disimpulhan bahwa jarak terpendek dari simpul A ke simpul J adalah 10 , dengan rute A-D-E-H-J atau A-D-F-I-J

 CatatanGraph adalah struktur yang terdiri dari himpunan titik-titik  yang disebut simpul dan himpunan sisi-sisi  yaitu garis yang menghubungkan dua buah simpul.

Bilangan pada sisi graph tersebut dinamakan bobot dari sisi. Graph yang sisinya diberi bobot disebut graph berbobot.

Graph yang sisinya mempunyai arah disebut graph berarah.

 


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: