Skripsi

Penerapan algoritma auction untuk mengatasi masalah lintasan terpendek (shortest path) / Elvira Firdausi Nuzula

Abstrak
Firdausi Nuzula Elvira. 2013. Penerapan Algoritma Auction untuk Mengatasi Masalah Lintasan Terpendek (Shortest Path). Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (I) Prof. Drs. Purwanto Ph.D (II) Lucky Tri Oktoviana S.Si M.Kom Kata Kunci shortest path auction algoritma auction 12288 12288 12288 12288 Shortest Path Problem dideskripsikan sebagai masalah pencarian untuk menemukan lintasan terpendek antara dua atau beberapa simpul yang saling berhubungan. Terdapat beberapa algoritma yang dapat digunakan pada penyelesaian Shortest Path salah satu algoritma yang masih belum umum digunakan adalah Algoritma Auction. 12288 12288 12288 12288 Algoritma Auction merupakan algoritma yang merupakan perpaduan dua metode yaitu label setting (jarak terpendeknya ditemukan pada saat pertama kali titik diberi label seperti Algoritma Dijkstra ) dan label correcting (label titik dapat terus diperbarui setelah jarak terpendeknya ditemukan seperti Algoritma Bellman-Ford). 12288 12288 12288 12288 Algoritma Auction ini dimulai dengan inisialisasi semua bobot titik dengan nol. Dilanjutkan dengan pencarian dengan menentukan terlebih dahulu bobot sisi yang paling minimum dengan dimana adalah bobot sisi dari ke dan adalah bobot titik tujuan. Jika dari perhitungan diperoleh maka diperbarui yaitu . Namun apabila tidak memenuhi akan ditentukan titik yang dituju yaitu titik yang mempunyai bobot . Proses akan berlanjut dan apabila titik yang diperoleh merupakan titik tujuan akhir maka algoritma berhenti. Panjang lintasan yang diperoleh adalah bobot titik tujuan awal dikurangi bobot titik tujuan akhir yaitu . Sedangkan lintasan yang diperoleh adalah titik-titik yang terpilih dari titik awal hingga titik tujuan akhir. Batasan masalah yang digunakan pada algoritma ini yaitu graf berarah yang mempunyai bobot dengan tidak memuat sisi ganda dan loop. 12288 12288 12288 12288 Dari kedua contoh pada bab III dapat disimpulkan beberapa perbedaan dan persamaan antara Algoritma Auction dengan Algoritma Dijkstra. Pada contoh tersebut terlihat bahwa lintasan dan panjang lintasan yang diperoleh sama. Namun jumlah iterasi dan proses pencarian lebih banyak saat menggunakan Algoritma Auction. Dapat disimpullkan bahwa Algoritma Dijkstra lebih efisien dibandingkan dengan Algoritma Auction. Hal ini dikarenakan pada algoritma Auction selalu memperbarui bobot titik dengan cara memeriksa dari titik awal. Sedangkan Algoritma Dijkstra pencarian hanya dengan sekali jalan tanpa harus bergerak mundur 12288 12288 12288 12288 Implementasi program dari Algoritma Auction yang telah dibuat oleh penulis juga sangat membantu dalam menyelesaikan permasalahan shortest path khususnya dengan banyak titik.

Informasi Detail

DDC

Rs 511.8 NUZ p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2013.

Deskripsi Fisik

ix, 69 lembar : il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

04358/KI/13

Edisi

Skripsi (Sarjana). Universitas Negeri Malang, 2013

Subjek

1. ALGORITMA
2. LINTASAN TERPENDEK (SHORTEST PATH)

Pembimbing

1. Purwanto ; 2. Lucky Tri Oktoviana

Lampiran Berkas