Skripsi

Penyelesaian masalah lintasan terpendek (Shortest Path) menggunakan algoritma A* (A star search) / Erna Vianti

Abstrak
Kata kunci graph Shortest Path UCS Greedy Algoritma A Search Lintasan Terpendek (Shortest Path) merupakan lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graph. Dalam jurnal yang ditulis oleh Graham Kendall terdapat pembahasan salah satu algoritma pencarian permasalahan Shortest Path. Algoritma ini dipilih karena bekerja dari sebuah perkiraan terbaik biaya yang dimiliki jalur-jalur yang melewati sebuah kota sehingga biaya dari kota tersebut menuju ke kota tujuan adalah biaya yang paling minimum. Algoritma ini terkenal dengan sebutan algoritma A . Dalam penyelesaiannya algoritma A melibatkan algoritma Uniform Cost Search (UCS) dan algoritma Greedy. Algoritma A tidak akan pernah mengabaikan kemungkinan adanya jalur lain yang memiliki biaya lebih rendah. Penulisan skripsi ini bertujuan untuk menyelesaikan permasalahan Shortest Path dengan menggunakan algoritma A Search dimana solusi yang diberikan tunggal dan optimum. Dalam pengerjaanya diperlukan ketelitian dalam menghitung nilai heuristiknya. Oleh karena itu untuk mempermudah dalam perhitungan maka dalam skripsi ini algoritma A Search diimplementasikan dengan menggunakan bahasa Delphi. Pada penerapannya algoritma A Search lebih cocok digunakan dalam mencari lintasan terpendek pada jalur udara. Jika digunakan dalam jalur darat maka harus ada transportasi yang menghubungkan masing-masing kota secara langsung (misal pesawat terbang). Untuk mengetahui keoptimalan algoritma A search maka dibandingkan dengan alat bantu Grin. Jika diterapkan dengan masalah yang sama implementasi algoritma A ini menghasilkan solusi yang sama dengan alat bantu Grin. . i

Informasi Detail

DDC

Rs 511.8 VIA p

Prodi

Universitas Negeri Malang. Jurusan Matematika, 2010.

Deskripsi Fisik

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

Bahasa

Indonesia

No Reg

03499/KI/10

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2010

Subjek

1. ALGORITMA
2. GRAPH

Pembimbing

1. SAPTI WAHYUNINGSIH ; 2. DARMAWAN SATYANANDA

Lampiran Berkas