TRAVELING SALESMAN PROBLEM (TSP)

Resume Individu: TRAVELING SALESMAN PROBLEM(TSP)

Nama: Komarudin Tasdik

NRP: G651100341

Penyaji (kelompokku):

Andi Hasad, dkk. 2010. Slide Presentasi: Traveling Salesman Problem (TSP). Institut Pertanian Bogor: Departemen Ilmu Komputer

  • Traveling Salesman Problem (TSP) merupakan pencarian urutan semua lokasi (misalnya kota) yang harus dikunjungi, mulai dari suatu kota tertentu dan kembali ke kota tersebut, dengan meminimalkan total biaya dan setiap kota harus dikunjungi satu kali (tidak boleh kurang atau lebih).
  • Untuk masalah TSP, nilai biaya perkiraan (estimated cost) untuk setiap simpul dihitung dengan menggunakan matriks biaya-tereduksi (reduced cost matrix) dari graph G.
  • Sebuah matriks dikatakan tereduksi jika setiap kolom dan barisnya mengandung minimal satu nilai nol dan semua elemen lainnya non-negatif
  • Representasi Matriks

Matriks di atas dapat direduksi dengan dua langkah berurutan, reduksi baris dan reduksi kolom

Contoh langkah reduksi:

¢  Reduksi Baris

Setiap elemen pada setiap baris dikurangi dengan elemen terkecil pada baris tersebut. Sebagai contoh, elemen terkecil pada baris ke-I adalah 3, maka semua elemen pada baris ke-I dikurangi 3 (dilambangkan 1 3).


 

¢  Reduksi Kolom

Dari matriks yang dihasilkan oleh reduksi baris di atas, setiap elemen pada setiap kolom dikurangi dengan elemen terkecil pada kolom tersebut. Sebagai contoh, elemen terkecil pada kolom ke-4 adalah 5, maka semua elemen pada kolom ke-4 dikurangi dengan 5 (dilambangkan K – 5).

¢  Dari ke dua langkah (reduksi baris dan kolom) di atas, jumlah semua pengurang baris dan kolom = (3 + 4 + 3 + 4 + 2) + (5) = 21.

¢  Solusi yang berupa jalur kunjungan(1, 2, 4, 5, 3,1) dengan total Biaya = 23

***

Terima kasih kepada teman-teman penyaji. Apabila ada kesalahan dalam resume ini, mohon koreksinya.

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