Dian Ayu Anggraeni (2009) Penggunaan metode farthest insertion heuristic dan metode arbitrary insertion heuristic dalam menyelesaikan traveling salesman problem / Dian Ayu Anggraeni. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Teori graph merupakan salah satu cabang matematika yang banyak bermanfaat kerena dengan menggunakan rumusan atau metode dari teori graph yang tepat maka kita dapat menyelesaikan suatu masalah lebih mudah. Salah satu masalah yang dapat diselesaikan dengan bantuan teori graph adalah Traveling Salesman Problem (TSP). TSP merupakan suatu masalah dalam menemukan sikel Hamilton dengan jumlah bobot sisi minimum. Terdapat beberapa metode yang dapat digunakan dalam menyelesaikan masalah TSP. Metode yang akan dibahas dalam menentukan sikel Hamilton adalah metode Farthest Insertion Heuristic dan Arbitrary Insertion Heuristic. Metode Farthest Insertion Heuristic ini membangun suatu tour dari sikel kecil dengan bobot maksimal dan secara berturut-turut ditambah dengan titik baru yang terjauh dari sikel. Titik baru tersebut disisipkan di antara dua titik dalam sikel yang mempunyai nilai penyisipan yang minimum. Sedangkan Metode Arbitrary Insertion Heuristic membangun suatu tour dari sikel kecil dengan bobot minimum dan secara berturut-turut ditambah dengan titik baru yang dipilih secara sembarang dan tidak dalam sikel. Titik baru tersebut disisipkan di antara dua titik dalam sikel yang mempunyai nilai penyisipan yang minimum. Pada skripsi ini kedua metode akan dibandingkan dengan metode Cheapest Link Nearest Neighbor Heuristic dan metode Nearest Insertion Heuristic. Solusi yang diperoleh dengan menggunakan kelima metode tersebut dapat berbeda hal ini dikarenakan perbedaan konstruksi atau langkah-langkah pada masing-masing metode dalam menemukan sikel Hamilton dengan bobot minimum. Dengan demikian metode Farthest Insertion Heuristic dan Arbitrary Insertion Heuristic dapat digunakan sebagai alternatif untuk mencari sikel Hamilton selain metode Cheapest Link Nearest Neighbor Heuristic dan metode Nearest Insertion Heuristic. Agar lebih mudah dalam menyelesaikan TSP metode Farthest Insertion Heuristic dan Arbitrary Insertion Heuristic dapat direpresentasikan dalam program komputer yaitu menggunakan Borland Delphi.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 19 Jan 2009 04:29 |
| Last Modified: | 09 Sep 2009 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/16775 |
Actions (login required)
 |
View Item |