Matematika Diskrit: METODE TETANGGA TERDEKAT

Contoh soal:

Misalkan gambar tersebut diberikan cara perhitungan untuk menyelesaikan permasalahan perjalanan bus tersebut dengan metode tetangga terdekat, adapun langkah-langkahnya sebagai berikut:

1.  Diambil A sebagai terminal
2.  Dipilih halte pertama yang paling dekat dengan A, yaitu C, bobot AC adalah 6 km
3.  Ambil halte C untuk dihubungkan dengan halte lain yang terdekat yaitu halte F, bobot CF adalah 2,5 km
4. Ambil halte F untuk dihubungkan dengan halte lain yang terdekat yaitu halte B, bobot FB adalah 4 km
5. Ambil halte B untuk dihubungkan dengan halte lain yang terdekat yaitu halte G, bobot BG adalah 7,5 km
6. Ambil halte G untuk dihubungkan dengan halte lain yang terdekat yaitu halte H atau I, karena dua halte tersebut bobotnya sama ke halte G, kemudian dipilh yang mempunyai bobot lebih kecil, tetapi tidak boleh memilih halte yang pernah dipilih. Diambil halte I, bobot GI adalah 4,5 km
7. Ambil halte I untuk dihubungkan dengan halte lain yang terdekat yaitu H, bobot IH adalah 1 km
8. Ambil halte I untuk dihubungkan dengan halte lain yang terdekat yaitu J, bobot HJ adalah 2,5 km
9. Ambil halte J untuk dihubungkan dengan halte lain yang terdekat yaitu E, bobot JE adalah 3,5 km
10. Ambil halte E untuk dihubungkan dengan halte lain yang terdekat yaitu D, bobot ED adalah 4 km
11. Dari halte terakhir yang dipilh langsung kembali ke terminal, yaitu halte A dengan bobot 7 km

Maka penyelesaian yang mungkin dengan metode tetangga terdekat adalah: A-C-F-B-G-I-H-J-E-D-A. Jadi total bobot rute yang ditempuh oleh bus tersebut adalah 6+2,5+4+7,5+4,5+1+2,5+3,5+4+7=42,5 km dengan perjalanan dimulai dari titik A atau terminal Giwangan. Jika digambarkan dalam bentuk graf rute perjalanan bus tersebut membentuk sebuah sikel Hamilton seperti ini: