:: UI - Skripsi Membership :: Kembali

UI - Skripsi Membership :: Kembali

Konstruksi batas bawah solusi optimal TSP menggunakan pelabelan ajaib

Hutagalung, Milka; Silaban, Denny Riama, supervisor; Kiki Ariyanti Sugeng (Universitas Indonesia, 2007)

 Abstrak

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).

 File Digital: 1

Shelf
 064-07-Kosntruksi batas.pdf :: Unduh

LOGIN required

 Metadata

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
  • Ketersediaan
  • Ulasan
No. Panggil No. Barkod Ketersediaan
S27753 14-20-474783028 TERSEDIA
Ulasan:
Tidak ada ulasan pada koleksi ini: 20180971