Analisis kinerja algoritma pemrograman dinamik pada masalah multystage graph / Wawan Setiawan
| Main Author: | Setiawan, Wawan |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2013
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17190/ |
Daftar Isi:
- SetiawanWawan.2013.AnalisisKinerjaAlgoritmaPemrogramanDinamikPadaMasalahMultistageGraph.Skripsi.ProgramStudiMatematikaFMIPAUniversitasNegeriMalang.Pembimbing(1)Dra.SusyKuspambudiAndainiM.Kom.(2)Dra.SaptiWahyuningsihM.SiKataKunciAlgoritmaRunningTimeMultistageProblemPemrogramandinamikA.Suatuperusahaanmemilikimasalahyangberagamdiantaranyaadalahmasalahyangberbentukmultitage.Masalahmultistageadalahmasalahyangterdiridaribeberapatahapan.Bentukmasalahmultistagesepertimasalahperencanaanpenerbangan(flightplan)yaitupemilihanketinggiankecepatandanruteyangdiambil.Untukmenyelesaikanmasalahmultistageperlusuatucarayangtepatsepertipenggunaanalgoritmayangsesuai.Algoritmayangdapatdigunakanmenyelesaikanmasalahmultitageyaitualgoritmapemrogramandinamik.Untukmengetahuialgoritmatersebutsesuaiperlupengkajianlebihmendalampadaalgoritmatersebut.Tujuanpengkajianiniadalahuntukmengetahuikinerjaalgoritmapemrogramandinamikdanimplementasinyadalambentukprogram.Penerapanprogramjugadilakukanuntukmengetahuihasildariprogram.Pengkajianalgoritmapemrogramandinamikuntukmasalahmultistageyaituberupapenerapanmanualanalisiskinerjayangberupaanalisiswaktuyangdiperlukanalgoritmauntukmelakukaneksekusi(runningtime)danperhitunganmenggunakanprogramyangdidesainmenggunakanalgoritmatersebut.BerdasaranalisisalgoritmayangsudahdilakukanAlgoritmapemrogramandinamikmenunjukkansolusiyangoptimalbesertasemuaalternatifsolusidarimasalahmultistage.SedangkanalgoritmaA(sebagaipembanding)memberikansolusioptimaltanpaalternatifsolusi.PadaanalisisrunningtimealgoritmapemrogramandinamikrelatifbesaryaituO(12310(n-2)12311(n-2)).BerbedadenganalgoritmaAyangmemilikiwakturunningO(n2)Algoritmapemrogramandinamistidakmemberikanwakturunninglebihbaiknamunmemberikankelebihandalambentukalternatifsolusi.SedangkanalgoritmaAmemberikasolusitunggaldenganwaktutercepat.SecaraumumalgoritmapemrogramandinamislebihbaikdariAdalamhalmenyelesaikanmasalahmultistageyangmemilikialternatifsolusi.