Implementasi algoritma backtracking dengan menggunakan metode DFS (Depth First Search) pada penyelesaian traveling salesman problem suatu digraph / Pipin Mega Ayuning Tyas
| Main Author: | Tyas, Pipin Mega Ayuning |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2010
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17907/ |
Daftar Isi:
- KatakunciAlgoritmaBacktrackingTravelingSalesmanProblem.Teorigraphmerupakansalahsatucabangmatematikayangbanyakdimanfaatkandalammemecahkanmasalahdalamkehidupansehari-hari.SalahsatuterapannyaadalahTravelingSalesmanProblemyaitupermasalahandarisalesmanyanginginmenyelesaikanperjalanannyadimulaidarikotaasalsalesmanberadalaluberkunjungkekota-kotayangditujudankembalikekotaasalsalesmanberadatadidenganruteterpendek.DengankatalainpermasalahanTSPadalahpermasalahanmenemukansikelHamilton.PersoalanTSPtidakhanyadapatdiperlakukanuntukmasalahgraphtidaberarahsajatetapijugauntukgraphberarahdangraphkomplitmaupungraphtidakkomplit.Salahsatuteknikyangdapatdigunakanuntukmempercepatpencariansolusiadalahdenganteknikpencarianpadapohonruangstatus.Teknikiniselaludapatmemecahkanmasalahdanjikaadabeberapasolusimakadapatdiketahuiseluruhsolusiyangada.AlgoritmayangmenggunakanteknikinisalahsatunyaadalahAlgoritmaBacktrackingyangdibahaspadaskripsiini.AlgoritmaBacktrackinginimelakukanpenelusurandenganmenggunakanmetodeDFS(DepthFirstSearch).Penelusurandimulaidarisatusimpulawalkemudianmembangkitkansimpulberikutnyayangmerupakansolusi.Solusiiniditentukanolehfungsipembatasyangtelahditentukansebelumnya.Apabilabukansolusimakasimpultersebuttidakdiperhitungkanatauakandimatikandanakandilakukanbacktrackkesimpulsebelumnyabegituseterusnyahinggasemuasimpultelahdibangkitkandantelahditemukansolusinya.DarihasilpenyelesaiancontohTSPdenganmenggunakanmetodematriksbentuknormalmetodebranchandbounddanalgoritmabaktrackingdiperolehsikelhamiltondanbobotminimumyangsama.AlgoritmaBacktrackingjugadapatmenemukanlebihbanyaksolusidaripadaalgoritmalaintetapitidaksemuayangdiselesaikandenganmetodebranchandbounddanalgoritmabacktrackingdapatdiselesaikanjugadenganmetodematriksbentuknormal.Padamatriksbentuknormalberlakupadajenisdigraphtertentusaja.Dengandemikianalgoritmabaktrackingdalamskripsiinidapatdigunakansebagaialternatif.UntuklebihmudahnyaalgoritmabacktrackingalgoritmabranchandbounddanmetodematriksbentuknormaldiimplementasikankedalamsebuahprogramdenganmenggunakanbahasapemrogramanBorlandDelphi7.0.