BAB I
PENDAHULUAN
1.1. Latar Belakang Permasalahan
Teori graph termasuk ilmu yang usianya sudah tua namun memiliki banyak terapan hingga saat ini. Graph sendiri merupakan suatu metode untuk memecahkan masalahmasalah diskrit yang ditemukan dalam kehidupan nyata. Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antar objek tersebut. Oleh karena kesederhanaannya, graph menjadi metode yang paling sering dipakai untuk mencari solusi permasalahan dalam berbagai bidang seperti ilmu rekayasa, ilmu pengetahuan alam, sosial, lingustik, dan lain-lain. Permasalahan pencarian rute terpendek merupakan suatu masalah yang sangat terkenal di dunia Informatika. Dari dahulu hingga sekarang telah dikembangkan berbagai algoritma untuk memecahkan permasalahan ini. Hingga saat ini telah banyak yang menemukan solusi untuk pencarian rute terpendek ini. Salah satunya yang terkenal adalah algoritma dynamic programming (algoritma Bellman � Ford), kemudian algoritma dijkstra yang juga merupakan algoritma yang cukup banyak dipakai dalam permasalahan ini.Penentuan rute terpendek dari satu titik ke titik yang lain adalah masalah yang sering ditemui dalam kehidupan sehari-hari. Berbagai kalangan menemui permasalahan serupa dengan variasi yang berbeda, contohnya seorang pengemudi yang mencari jalur terpendek dari tempat asal ke tempat tujuan, pengantar pesanan makanan cepat saji yang juga mencari jalur terpendek dari tempat asal ke tempat tujuan, dan juga seorang desainer jaringan komputer yang harus mendesain skema perutean pada jaringan yang dia tangani agar memaksimalkan performa jaringan dan meminimalkan beban yang harus ditangani oleh jaringan tersebut.
PENDAHULUAN
1.1. Latar Belakang Permasalahan
Teori graph termasuk ilmu yang usianya sudah tua namun memiliki banyak terapan hingga saat ini. Graph sendiri merupakan suatu metode untuk memecahkan masalahmasalah diskrit yang ditemukan dalam kehidupan nyata. Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antar objek tersebut. Oleh karena kesederhanaannya, graph menjadi metode yang paling sering dipakai untuk mencari solusi permasalahan dalam berbagai bidang seperti ilmu rekayasa, ilmu pengetahuan alam, sosial, lingustik, dan lain-lain. Permasalahan pencarian rute terpendek merupakan suatu masalah yang sangat terkenal di dunia Informatika. Dari dahulu hingga sekarang telah dikembangkan berbagai algoritma untuk memecahkan permasalahan ini. Hingga saat ini telah banyak yang menemukan solusi untuk pencarian rute terpendek ini. Salah satunya yang terkenal adalah algoritma dynamic programming (algoritma Bellman � Ford), kemudian algoritma dijkstra yang juga merupakan algoritma yang cukup banyak dipakai dalam permasalahan ini.Penentuan rute terpendek dari satu titik ke titik yang lain adalah masalah yang sering ditemui dalam kehidupan sehari-hari. Berbagai kalangan menemui permasalahan serupa dengan variasi yang berbeda, contohnya seorang pengemudi yang mencari jalur terpendek dari tempat asal ke tempat tujuan, pengantar pesanan makanan cepat saji yang juga mencari jalur terpendek dari tempat asal ke tempat tujuan, dan juga seorang desainer jaringan komputer yang harus mendesain skema perutean pada jaringan yang dia tangani agar memaksimalkan performa jaringan dan meminimalkan beban yang harus ditangani oleh jaringan tersebut.
Persoalan untuk menentukan rute terpendek pada graph multitahap (multistage graph) dan algoritma efisien yang tersedia untuk menghitung rute terpendek. Rute terpendek yang diperoleh akan meminimumkan fungsi linier lintasan jarak dan waktu. Perumusan persoalan ini akan menjadi salah satu kegunaan dari rute jarak terpendek. Algoritma yang digunakan untuk menentukan rute terpendek pada graph multitahap (multistage graph) adalah Dynamic Programming. Seiring dengan waktu yang berjalan dan juga perkembangan ilmu pengetahuan dan teknologi permasalahan pencarian rute terpendek ini telah terpecahkan dengan berbagai algoritma salah satunya dengan algoritma Dynamic Programming.Andaikan diberikan sebuah jaringan G dengan m titik dan n garis yang dihubungkan dengan tiap garis (i,j) dalam G. Masalahnya adalah menentukan rute terpendek dari titik 1 ke titik m dalam G.
Algoritma yang digunakan untuk menentukan rute terpendek pada graph multitahap (multistage graph) adalah Dynamic Programming. Pada algoritma ini memperlihatkan bahwa penyelesaian optimal yang diperoleh. Untuk itu penulis akan meninjau suatu algoritma untuk menentukan rute terpendek pada graph multitahap (multistage graph) , salah satu algoritma yang digunakan adalah Algoritma Dynamic Programming Pada algoritma ini memperlihatkan bahwa penyelesaian optimal yang diperoleh. Untuk itu penulis akan meninjau suatu algoritma untuk menentukan rute terpendek pada graph multitahap (multistage graph), salah satu algoritma yang digunakan adalah Algoritma Dynamic Programming. Algoritma Dynamic Programming adalah suatu metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Pada Algoritma Dynamic Programming rangkaian keputusan yang optimal dibuat dengan menggunakan prinsip optimalitas. Prinsip optimalitas yaitu jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal. Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal.Tulisan ini akan membahas bagaimana peranan Algoritma Dynamic Programming dalam menyelesaikan masalah rute terpendek pada graph multitahap (multistage graph), serta menerapkannya dalam suatu program. Berdasarkan latar belakang diatas makan penulis membuat judul Perancangan Simulasi Dynamic Programming Untuk Menentukan Rute Terpendek Pada Graph Multi Tahap (Multistage Graph).
1.2. Perumusan Masalah
Adapun perumusan masalah dalam tulisan ini adalah :
Adapun perumusan masalah dalam tulisan ini adalah :
- Bagaimana penerapan Algoritma Dynamic Programming dalam menyelesaikan masalah rute terpendek pada Graph Multi Tahap (Multistage Graph) ?
- Bagaimana merancang aplikasi penentuan rute terpendek pada graph dengan menggunakan algoritma dynamic programming ?
1.3. Batasan Masalah
Adapun batasan masalah dari skripsi ini adalah :
- Dalam kasus ini yang diteliti yaitu sebuah graph berarah terhubung (directed connected graph).
- Algoritma yang digunakan dalam menyelesaikan permasalahan ini adalah algoritma Dynamic Programming
1.4. Tujuan dan Manfaat Penelitian
Adapun tujuan dalam penelitian ini adalah :
- Untuk menerapkan suatu Algoritma Dynamic Programming dalam menyelesaikan masalah rute terpendek pada Graph Multi Tahap (Multistage Graph)
- Untuk merancang aplikasi penentuan rute terpendek pada Graph dengan menggunakan Algoritma Dynamic Programming
Adapun manfaat dari penelitian ini adalah :
- Memperoleh jarak yang terdekat untuk sampai ke tempat tujuan
- Mempermudah pencarian rute terpendek yang akan dilalui
1.5. Metode Penelitian
Dalam pengumpulan data yang diperlukan untuk tugas akhir ini, penulis menggunakan metode sebagai berikut :
- Studi literatur. Penulisan ini dimulai dengan studi kepustakaan, yaitu dengan mengumpulkan bahan-bahan referensi baik dari buku, artikel, paper, jurnal, makalah, situs internet mengenai Multistage Graph dan konsep matematis yang mendasarinya serta pemrograman untuk pembuatan aplikasinya, dan beberapa referensi lainnya untuk menunjang pencapaian tujuan skripsi yang dibuat.
- Analisis permasalahan. Pada tahap ini dilakukan analisis terhadap Metode Multistage Graph baik dari aspek matematis maupun proses komputerisasinya.
- Perancangan Sistem. Perancangan sistem yang dapat mengolah data dalam proses pengolahan data.
- Implementasi sistem yang dirancang kedalam sebuah bahasa pemrograman. Testing Program. Untuk mengetahui sejauh manakah tingkat kesuksesan program yang dibuat.
1.6. Sistematika Penulisan
Sistematika penulisan dari skripsi ini terdiri dari beberapa bagian utama sebagai berikut:
BAB I : PENDAHULUAN
Bab ini akan menjelaskan mengenai latar belakang masalah perumusan masalah, batasan masalah, tujuan dan manfaat penelitian, metode penelitian, dan sistematika penulisan.
Bab ini akan menjelaskan mengenai latar belakang masalah perumusan masalah, batasan masalah, tujuan dan manfaat penelitian, metode penelitian, dan sistematika penulisan.
BAB II : LANDASAN TEORI
Bab ini akan membahas mengenai teori-teori yang berkaitan dengan Algoritma Dynamic Programming�.
Bab ini akan membahas mengenai teori-teori yang berkaitan dengan Algoritma Dynamic Programming�.
BAB III : ANALISIS DAN PERANCANGAN SISTEM
Bab ini akan membahas mengenai analisis kebutuhan sistem yang meliputi analisis kasus dan analisis algoritma. Selain itu, dibahas mengenai perancangan sistem baik perancangan alur, perancangan aplikasi, dan perancangan antarmuka.
Bab ini akan membahas mengenai analisis kebutuhan sistem yang meliputi analisis kasus dan analisis algoritma. Selain itu, dibahas mengenai perancangan sistem baik perancangan alur, perancangan aplikasi, dan perancangan antarmuka.
BAB IV : ALGORITMA DAN IMPLEMENTASI
Bab ini akan membahas mengenai bagaimana hasil implementasi aplikasi yang dirancang ini beserta pengujian terhadap aplikasi tersebut
Bab ini akan membahas mengenai bagaimana hasil implementasi aplikasi yang dirancang ini beserta pengujian terhadap aplikasi tersebut
BAB V : KESIMPULAN DAN SARAN
Bab ini akan memuat kesimpulan isi dari keseluruhan uraian bab-bab sebelumnya dan saran-saran dari hasil yang diperoleh yang diharapkan dapat bermanfaat untuk pengembangan selanjutnya.
Bab ini akan memuat kesimpulan isi dari keseluruhan uraian bab-bab sebelumnya dan saran-saran dari hasil yang diperoleh yang diharapkan dapat bermanfaat untuk pengembangan selanjutnya.
Tidak ada komentar:
Posting Komentar