CPP- The Chinese postman problem atau Route inspection problem

CPP pertama di cetuskan oleh seorang matematikawan china bernama Mei-Ko pada tahun 1969.

CPP ialah masalah dalam mencari rute yang efisien dalam sebuah graph dimana

seorang tukang pos yang betugas mengambil surat dari kantor pos dan mengirimkannya ke masing-masing alamat. Rata-rata tukang pos akan melalui setiap jalan dalam wilayah kerjanya minimal satu kali.

 

Digaram rute tukag pos

 

 

kita dapat menyelesaikan masalah ini dengan algoritma fluery.

Algoritma Fluery

Jika G ialah Graph dengan vertex berderajat genap maka kita dapat menentukan Eurlian circuit (lintasan dari satu simpul, melewati semua sisi, kembali ke simpul tersebut dengan melewati suatu titik )

  1. Mulai dengan titik awal vertex sembarang
  2. Dari vertex tersebut tranvese edge yang berdekatan dengan vertex tersebut dimana penghilangan edge tersebut tidak membuat graph terputus (membentuk graph terpisah)
  3. Hilangkan edge yang telah di pilih pada graph. Jika sudha tidak ada graph stop , selain itu kembali ke step 2

Jika G ialah graph dengan dua buah vertex ganjil. Kita dapat mencari eurlier trail(lintasan dari suatu simpul, melewati semua sisi )

    1. Mulai dengan titik awal vertex ganjil
    2. Dari vertex tersebut tranvese edge yang berdekatan dengan vertex tersebut dimana penghilangan edge tersebut tidak membuat graph terputus (membentuk graph terpisah)
    3. Hilangkan edge yang telah di pilih pada graph. Jika sudha tidak ada graph stop , selain itu kembali ke step 2

 

karena pada masalah CPP ini kita diwajibkan mencari curcuit eurlian (dimana semua edge dikunjuni dan titik awal vertex akan menjadi titik akhir) maka kiat perlu membut vertex tersebut mejadi Eurlian graph dimana semua vertex berderajat genap dengan cara mencari pasangan edge mana yang mempunyai weight yang paling kecil., dalam CPP edge yang mempunyai derajat ganjil ialah f dan b

(note: banyak pasangan dapat dicari dengan ,n=jumlah vertex derajat ganjil, kemungkinan pasangan=(n-1)*(n-3)*(n-5)*1)

 

Iklan

Tinggalkan komentar

Filed under Uncategorized

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