Penyelesaian travelling salesman problem (TSP) dengan menggunakan algoritma hill climbing / Aimmatul Mufarricha
| Main Author: | Mufarricha, Aimmatul |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2010
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17901/ |
Daftar Isi:
- KatakunciGraphTravellingSalesmanProblem(TSP)SimpleHillClimbingSteepestHillClimbing.TravellingSalesmanProblem(TSP)merupakansalahsatumasalahoptimalisasi.TravelingSalesmanProblemadalahsebagaisuatupermasalahanuntukmenemukansikelHamiltonyangmemilikitotalbobotsisiminimum.TSPmencarirutedarikotaasalkekota-kotayangditujudengansyaratsetiapkotahanyadapatdikunjungisatukalikecualikotaawal.BanyakalgoritmayangditerapkanpadapermasalahanTSPdiantaranyaadalahnearestneighborcheapestlinknearestinsertionheuristic.TerdapatalgoritmalainyangdapatdigambarkansebagaimetodeuntukmenemukansolusidarisuatupermasalahanTSP.Algoritmatersebutmerupakanbagiandariteknikpelacakandimanacarakerjanyamemberikankemungkinanbanyaksolusidanakandicarisolusiyangterbaik.Algoritmatersebutadalahalgoritmahillclimbing.Algoritmahillclimbingdimulaidenganmemilihsebaranglintasandanmembuatiterasiperubahankecilpadasolusisetiaplangkahmencarisolusiyangterbaik.Ketikaalgoritmatidakdapatmelihatperbaikanlagimakaakanberhenti.Padasaatituditemukansolusioptimal.DalampenulisanskripsiinibertujuanuntukmenyelesaikanpermasalahanTSPdenganmenggunakanalgoritmahillclimbing.Algoritmahillclimbingdibedakanmenjadiduayaitusimplehillclimbingdansteepesthillclimbing.Penyelesaiandaricontoh5titikyangdiperolehdenganmenggunakanalgoritmasimplehillclimbingdansteepesthillclimbingmemberikansolusiyangsamadenganpenyelesaianmenggunakanalgoritmagreedyalgoritmanearestneighboralgoritmacheapestlinkalgoritmafarthestinsertionheuristicalgoritmanearestinsertionheuristicdanalgoritmaarbitraryinsertionheuristic.SedangkanpadacontohTSPyanglainyaituuntuk1015dan20titikmenghasilkanrutedanjarakyangberbeda.Halinidikarenakanmetodepencariantitiknyayangberbeda.Kelebihandarialgoritmahillclimbingadalahdapatmenentukanbeberapakemungkinanlintasanyangterjadisehinggadapatdicarikemungkinansolusiyangterbaikdaribeberapakemungkinantersebut.Kelemahannyaadalahmembutuhkanwaktuyangrelatiflamakarenaharusmenghitungkemungkinanbanyaklintasan.Olehkarenaitualgoritmahillclimbingmerupakanmasalahyangberbasiskomputasi.UntukmempermudahdalamperhitunganmakadalamskripsiinialgoritmahillclimbingdibuatdalamsuatubahasaprogramdenganbahasapemrogramanDelphi.i