Alfian, Alfian (2020) Studi Banding Algoritma Penyelesaian Permasalahan Minimum Path of All Edge Coverage Pada Directed Acyclic Graph Planar: Studi Kasus SPOJ - Skiver1 (Skiers). Other thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111640000073_Undergraduate_Thesis.pdf Download (2MB) | Preview |
Abstract
Minimum Path of All Edges Coverage (MPAEC) adalahpermasalahan meminimalkan jumlah path yang dibutuhkanuntukmencakup semua edge yang ada pada Directed AcyclicGraph(DAG) dengan ketentuan sebuah jalur mungkin saja dilewati lebihdari sekali. Permasalahan ini bisa diselesaikan dengan pendekatanMinimum Path Cover. Permasalahan SPOJ - Skiver1 (Skiers) adalah permasalahanMPAEC dengan vertex 1 sebagai vertex awal dan vertex Nsebagaivertex terakhir di mana N adalah nomor vertex terakhir padaDAG. Proses traversing (penelusuran) dimulai dari vertex 1 danberakhirdi vertex N, dan edge pada data masukan sudah terurut daripermukaan paling kiri ke permukaan paling kanan. Sehinggadengan keteraturan data tersebut bisa dianalisis apakahketeraturan tersebut bisa dimanfaatkan sehingga bisa ditemukanalgoritma penyelesaian yang lebih efisien. Pada Tugas Akhir (TA) ini dirancang dua penyelesaianuntukpermasalahan SPOJ - Skiver1 (Skiers), yaitu: (1) penyelesaian dengan Minimum Path Cover, dan (2) pendekatan DFS(DepthFirsh Search) dengan Greedy Pruning, Perbandinganduapendekatan tersebut dalam menyelesaikan permasalahanMPAECpada studi kasus SPOJ - Skiver1 (Skiers) dibahas lebihlanjutdalam TA ini, di mana diperlihatkan bahwa pendekatan(2) lebihbaik dibandingkan (1) dalam studi kasus SPOJ - Skiver1
================================================================================================================================
Minimum Path of All Edges Coverage (MPAEC) is a minimizationproblem that minimizes the required paths for covering all edgesofthe Directed Acyclic Graph (DAG) where an edge may bepassedmore than once. This problem can be solved by MinimumPathCover approach. SPOJ - Skiver1 (Skiers) problem is an MPAECproblemwherevertex 1 is the first vertex and vertex N is the last vertex of theDAG. Traversing process start from vertex 1 and ended at vertexN, andthe input’s edges are sorted from left most face to the right-mostface. Thus, by its structured data, it can be analyzed whetherthatcharacteristic can be an advantage to be used for findingmoreef icient solution’s algorithm. In this thesis, two solutions for SPOJ - Skiver1 (Skiers) havebeendesigned: (1) the solution by using MinimumPath Cover, and(2)DFS (Depth First Search) with Greedy Pruning. The comparison between these two solutions to solve MPAEC probleminthecasestudy of SPOJ - Skiver1 (Skiers) has been discussed in this thesis, where it can be shown that (2) is better than (1).
| Item Type: | Thesis (Other) |
|---|---|
| Additional Information: | RSIf 005.1 Alf s-1 2020 |
| Uncontrolled Keywords: | DAG, Greedy, Minimum Path Cover |
| Subjects: | T Technology > T Technology (General) > T57.5 Data Processing T Technology > T Technology (General) > T57.62 Simulation T Technology > T Technology (General) > T58.8 Productivity. Efficiency |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | alfian alfian |
| Date Deposited: | 11 Mar 2025 03:17 |
| Last Modified: | 11 Mar 2025 03:17 |
| URI: | http://repository.its.ac.id/id/eprint/73158 |
Actions (login required)
 |
View Item |