GreedyMenengahFase D–FE1E5

TSP Nearest-Neighbor

Traveling Salesman versi heuristik serakah: dari kota sekarang selalu lompat ke kota terdekat yang belum dikunjungi, lalu kembali ke awal. Cepat dan mudah, walau tak selalu optimal. Contoh klasik trade-off antara kecepatan dan kualitas solusi.

Contoh kasus

Menyusun rute pengantaran cepat: dari titik sekarang menuju pelanggan terdekat berikutnya.

Silabus

TSP Nearest-Neighbor menyusun rute keliling dengan selalu melompat ke kota terdekat yang belum dikunjungi, cepat tapi belum tentu paling optimal.

Tujuan Belajar

·Memahami strategi serakah memilih kota terdekat berikutnya
·Menjelaskan trade-off antara kecepatan dan kualitas solusi
·Menerapkan heuristik nearest-neighbor untuk menyusun rute

Cara Kerja

·Mulai dari satu kota sebagai titik awal
·Dari kota sekarang, pilih kota terdekat yang belum dikunjungi
·Pindah ke kota itu dan tandai sudah dikunjungi
·Ulangi sampai semua kota terlewati
·Kembali ke kota awal untuk menutup rute keliling

Prasyarat

·Graf berbobot
·Algoritma greedy

Contoh Nyata

·Kurir menyusun urutan antar paket ke pelanggan terdekat berikutnya
·Driver Gojek mengambil orderan terdekat agar cepat sampai
·Merencanakan urutan kunjungan tempat wisata paling dekat saat liburan

Kompleksitas O(n^2) untuk n kota