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.
Example use case
Menyusun rute pengantaran cepat: dari titik sekarang menuju pelanggan terdekat berikutnya.
Syllabus
TSP Nearest-Neighbor menyusun rute keliling dengan selalu melompat ke kota terdekat yang belum dikunjungi, cepat tapi belum tentu paling optimal.
Objectives
- ·Memahami strategi serakah memilih kota terdekat berikutnya
- ·Menjelaskan trade-off antara kecepatan dan kualitas solusi
- ·Menerapkan heuristik nearest-neighbor untuk menyusun rute
How It Works
- ·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
Prerequisites
- ·Graf berbobot
- ·Algoritma greedy
Real-World Uses
- ·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
Complexity O(n^2) untuk n kota