Konstruksi batas bawah solusi optimal TSP menggunakan pelabelan ajaib
Hutagalung, Milka;
Silaban, Denny Riama, supervisor; Kiki Ariyanti Sugeng
(Universitas Indonesia, 2007)
|
| Traveling salesman problem (TSP) adalah permasalahan mencari rute perjalanan terpendek yang melalui sejumlah berhingga kota dengan syarat setiap kota hanya dikunjungi tepat satu kali dan perjalanan harus dimulai dan diakhiri pada kota yang sama. TSP dapat direpresentasikan dengan graf berbobot G = (V, E), dimana V adalah himpunan simpul yang menyatakan kota, E adalah himpunan busur yang menyatakan jalur penghubung antar kota, dan bobot tiap busur menyatakan jarak antar kota. TSP yang dibahas adalah TSP yang direpresentasikan dengan graf lengkap dan memenuhi ketaksamaan segitiga: untuk sembarang 2 simpul, bobot busur langsung lebih kecil dari total bobot melalui kota lain. Tiap busur pada graf TSP dapat diberikan nilai/label berupa bilangan bulat non negatif sedemikian sehingga untuk setiap simpul jumlah label busur-busur yang menempel pada simpul tersebut adalah sama, yaitu suatu konstanta k. Pemberian nilai seperti ini disebut sebagai pelabelan ajaib-k. Suatu graf berbobot dapat dilabel dengan banyak cara pelabelan ajaib-k. Skripsi ini membahas konstruksi batas bawah solusi optimal TSP yang memenuhi ketaksamaan segitiga menggunakan pelabelan ajaib. Pelabelan ajaib yang digunakan adalah pelabelan ajaib berkapasitas, yaitu kasus dimana diberikan batas atas label busur: r Î 6 - 2007). |
 064-07-Kosntruksi batas.pdf :: Unduh
|
| No. Panggil : | S27753 |
| Entri utama-Nama orang : | |
| Entri tambahan-Nama orang : | |
| Entri tambahan-Nama badan : | |
| Subjek : | |
| Penerbitan : | Depok: Universitas Indonesia, 2007 |
| Program Studi : |
| Bahasa : | ind |
| Sumber Pengatalogan : | |
| Tipe Konten : | |
| Tipe Media : | |
| Tipe Carrier : | |
| Deskripsi Fisik : | vii, 61 hlm. ; 30 cm. |
| Naskah Ringkas : | |
| Lembaga Pemilik : | Universitas Indonesia |
| Lokasi : | Perpustakaan UI, Lantai 3 |
| No. Panggil | No. Barkod | Ketersediaan |
|---|---|---|
| S27753 | 14-20-474783028 | TERSEDIA |
| Ulasan: |
| Tidak ada ulasan pada koleksi ini: 20180971 |
