Skripsi

Penyelesaian travelling salesman problem (TSP) dengan menggunakan algoritma hill climbing / Aimmatul Mufarricha

Abstrak
Kata kunci Graph Travelling Salesman Problem (TSP) Simple Hill Climbing Steepest Hill Climbing. Travelling Salesman Problem (TSP) merupakan salah satu masalah optimalisasi. Traveling Salesman Problem adalah sebagai suatu permasalahan untuk menemukan sikel Hamilton yang memiliki total bobot sisi minimum. TSP mencari rute dari kota asal ke kota-kota yang dituju dengan syarat setiap kota hanya dapat dikunjungi satu kali kecuali kota awal. Banyak algoritma yang diterapkan pada permasalahan TSP diantaranya adalah nearest neighbor cheapest link nearest insertion heuristic. Terdapat algoritma lain yang dapat digambarkan sebagai metode untuk menemukan solusi dari suatu permasalahan TSP. Algoritma tersebut merupakan bagian dari teknik pelacakan dimana cara kerjanya memberikan kemungkinan banyak solusi dan akan dicari solusi yang terbaik. Algoritma tersebut adalah algoritma hill climbing. Algoritma hill climbing dimulai dengan memilih sebarang lintasan dan membuat iterasi perubahan kecil pada solusi setiap langkah mencari solusi yang terbaik. Ketika algoritma tidak dapat melihat perbaikan lagi maka akan berhenti. Pada saat itu ditemukan solusi optimal. Dalam penulisan skripsi ini bertujuan untuk menyelesaikan permasalahan TSP dengan menggunakan algoritma hill climbing. Algoritma hill climbing dibedakan menjadi dua yaitu simple hill climbing dan steepest hill climbing. Penyelesaian dari contoh 5 titik yang diperoleh dengan menggunakan algoritma simple hill climbing dan steepest hill climbing memberikan solusi yang sama dengan penyelesaian menggunakan algoritma greedy algoritma nearest neighbor algoritma cheapest link algoritma farthest insertion heuristic algoritma nearest insertion heuristic dan algoritma arbitrary insertion heuristic. Sedangkan pada contoh TSP yang lain yaitu untuk 10 15 dan 20 titik menghasilkan rute dan jarak yang berbeda. Hal ini dikarenakan metode pencarian titiknya yang berbeda. Kelebihan dari algoritma hill climbing adalah dapat menentukan beberapa kemungkinan lintasan yang terjadi sehingga dapat dicari kemungkinan solusi yang terbaik dari beberapa kemungkinan tersebut. Kelemahannya adalah membutuhkan waktu yang relatif lama karena harus menghitung kemungkinan banyak lintasan. Oleh karena itu algoritma hill climbing merupakan masalah yang berbasis komputasi. Untuk mempermudah dalam perhitungan maka dalam skripsi ini algoritma hill climbing dibuat dalam suatu bahasa program dengan bahasa pemrograman Delphi. i

Informasi Detail

DDC

Rs 511.5 MUF p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2010.

Deskripsi Fisik

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

Bahasa

Indonesia

No Reg

03721/KI/10

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2010

Subjek

1. TEORI GRAPH
2. HILL CLIMBING - ALOGARITMA

Pembimbing

1. Purwanto 2. Darmawan Satyananda

Lampiran Berkas