Pramana, Agus Ari (1997) Penentuan Lintasan Terpendek Untuk Postman Postman Problem Dengan Algoritma Edmonds Dan Johnson. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
2690100043-Undergraduate_Theses.pdf - Published Version Download (2MB) | Preview |
Abstract
Dalam Tugas Akhir ini akan dibuat perangkat lunak pada salah satu aspek riset operasional yaitu menentukan lintasan terpendek dari Postman Problem dengan menggunakan algoritma pendekatan dari perpaduan antara algoritma Johnson dengan kebalikan dati algoritma tadi Algoritma Edmonds dan Johnson menyatakan bahwa setiap vertek dalam sebuah graf harus mempunyai jumlah degree yang genap untuk graf tidak berarah. Dan untuk graf yang berarah setiap vertek harus mempunyai degree yang genap, serta jumlah indegree sama dengan outdegree. Jadi algoritma ini terdiri dari tiga langkah yaitu, langkah pertama adalah mengubah graf asal sehingga setiap vertec mempunyai degree genap, dimana setiap arc dianggap sebagai edge. Langkah indegree sama dengan outdegree. Langkah ketiga mertg(;:mt,att.IWll satu aspek ri.set dengan Edmonds dan mempunyai degree genap sambil mempertahankan indegree sama ucu~1 outdegree. Algoritma yang kedua adalah kebalikan dari algoritma di yaitu langkah pertama yang dilakukan adalah langkah kedua dari algoritma dan Johnson. Langkah kedua yang dilakukan adalah J.angkah pertama dari Edmond dan Johnson sambil mempertahankan indegree sama dengan outdegree. Setelah kedua algoritma di atas digunakan untuk me-nyt::n;s;illlUjiJl suatu Postman Problem, maka dipilih penyelesaian yang paling baik
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.1 Pra p 19.720/H/04 |
| Uncontrolled Keywords: | Algoritma Edmonds dan Johnson, Postman problem |
| Subjects: | H Social Sciences > HE Transportation and Communications > HE336.R68 Route choice T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.546 Computer algorithms |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | - Davi Wah |
| Date Deposited: | 06 Sep 2019 06:49 |
| Last Modified: | 06 Sep 2019 06:49 |
| URI: | http://repository.its.ac.id/id/eprint/70640 |
Actions (login required)
 |
View Item |