Algoritma Dijkstra

Algoritme Dijkstra

~ ~ SIDS ~ ~

Algoritme Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritme rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

Djikstra merupakan salah satu varian bentuk algoritma popular dalam pemecahan persoalan terkait masalah optimasi pencarian  lintasan terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a ke z dalam graph berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka penyelesaian yang diberikan adalah infiniti (Tak Hingga). Pada algoritma Dijkstra, node digunakan karena algoritma Dijkstra menggunakan graph berarah untuk penentuan rute listasan terpendek. Berikut Pseudo Code dan Flowchart Algoritma Djikstra:

Djikstra Flowchart

Urutan logika algoritma Dijkstra :

1.  Greader berikan nilai bobot Guntuk setiap titik hingga ke titik yang lain, berikan nilai 0 pada node awal dan nilai tak hingga terhadap node yang lain.

2.  Setelah itu Greader berikan nilai pada semua node dan berikan node awal sebagai node keberangkatan.

3.  Dari node keberangkatan, hitung nilai jarak antara node keberangkatan ke node yang lain.

4.  Berikan pertimbangan untuk setiap node / langkah dari node keberangkatan ke node yang di tuju, dan berikan tanda yang gunanya untuk menandai agar node yang telah di lalui, tidak terlalui kembali. Setelah itu simpan hasil nilai bobot jarak terakhir dan gunakan bobot yang paling minimal.

5.  Carilah node yang belum dilalui dengan jarak terkecil dari node keberangkatan itu, lanjutkan kembali langkah ke 3.

6.  Kompleksitas algoritma Dijkstra merupakan O(n2), n merupakan simpul pada graf. Kompleksitas ini bisa diperbaiki dengan penggunaan struktur data senarai ketanggan atau antrian prioritas guna untuk memperoleh kompleksitas O((m+n) log n).

Contoh penerapan Algoritma Dijkstra dalam kehidupan sehari-hari :

1.  Aplikasi Pencarian Lokasi Rumah Kos Dan Jalur Terpendek Menggunakan Algoritma Dijkstra.

2.  Pencarian Solusi Maksimum Flow Problem Dengan Penerapan Algoritma Dijkstra.

3.  Penggunaan Algoritma Dijkstra Terhadap Sebuah Sistem Informasi Geografis

4.  Sekolah Luar Biasa Kota Pekanbaru Berbasis Online.

5.  Menemukan Jarak Terdekat Dari Lokasi Pengguna ke Lokasi Taman Yang Di Tuju Berbasis Android (Studi Kasus Taman Raya Kantor Gubernur Pekanbaru, Riau).

6.  Animasi 3D Lintasan Terpendek Menggunakan Algoritma

7.  Penggunaan Algoritma Dijkstra Dalam Mencari dan Menghindari Jalur Kemacetan Di Kota pekanbaru.

8.  Pencarian Rute Terpendek Angkutan Kota Dengan Menggunakan Algoritma Dijkstra (Studi Kasus Kota Medan).

9.  Menetukan Rute Terpendek Dalam Pengambilan Sampah (Studi Kasus Kecamatan Singingi, Kabupaten Kuantan Singingi).

10.  Penggunaan Algoritma Dijkstra Dalam Menentukan Jalur Terpendek Dalam Pencarian Lokasi Rumah Sakit Awal Bross (Studi Kasus Di Kota Sumatera Barat).

11.  Penerapan Algoritma Dijkstra Untuk Pencarian Rute Bus Transmetro Pekanbaru.

12.  Aplikasi Untuk Mengetahui Lokasi Tempat Ibadah Umat Muslim Dengan Menggunakan Algoritma Dijkstra (Studi Kasus Kota Bandung, Jawa Barat).

13.  Implementasi Algoritma Dijkstra Dalam Mencari dan Menentukan Rumah Makan Terdekat Dari Lokasi Pengguna.

14.  Menentukan Rute Terpendek Tempat Wisata Di Kota Malang Berbasis Android Dengan Menggunaan Algoritma Dijkstra.

15.  Implementasi Algoritma Dijkstra Dalam Perencanaan Rute Evakuasi Bencana Gempa Bumi Di Lombok Berbasis Android.

16.  Penggunaan Algoritma Dijkstra Dalam Pencarian Ojek Online Terdekat dari Lokasi Pengguna Berbasis Android.

Read More

Algoritma Ant Colony

Algoritma Ant Colony

==SIDS==

            Assalamualaikum Wr. Wb. Hallo readers kali ini oe akan membahas tentang suatu algoritma yang biasanya digunakan untuk mencari rute terpendek dan lain-lainnya. Untuk langsung saja kita menuju ke pembahasan.

Ø  Definisi

Algoritma ACO (Ant Colony Optimization) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh permasalahan yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik tujuan dengan jarak tempuh paling Singkat. Ant Colony Optimization adalah teknik probabilitas untuk menyelesaikan permasalahan, berdasarkan tingkah laku semut dalam sebuah koloni yang mencari sumber makanan.

Ø  Siapa sih yang mencetuskan Algoritma Ant Colony tersebut ?? Langsung saja kita baca dibawah ini.

Algoritma semut ini pertama kali diperkenalkan oleh Moyson dan Manderick dan secara meluas dikembangkan oleh Marco Dorigo pada tahun 1996, merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik. Algoritma ini terinspirasi oleh perilaku semut dalam menemukan jalur dari koloninya menuju makanan.

Ø  Dimana saja Algoritma Ant Colony ini bisa di teraokan ??

Algoritma Ant Colony ini sudah banyak di terapkan di berbagai bidang untuk mencari rute terpendek dari tempat-tempat yang akan kita tuju. Adapun beberapa bidang yang telah menerapkan metode Ant Colony tersebut, yaitu :

1. Traveling Salesman Problem (TSP), yaitu mencari rute terpendek dalam sebuah graph menggunakan rute Hamilton.

2. Quadratic Assignment Problem (QAP), yaitu menugaskan sejumlah n resources untuk ditempatkan pada sejumlah m lokasi dengan meminimalisasi biaya penugasan (assignment).

3. Job-shop Scheduling Problem (JSP) juga salah satu contoh aplikasi Ant Colony Optimization, yaitu untuk mencari lintasan sejumlah n pekerjaan menggunakan sejumlah m mesin demikian sehingga seluruh pekerjaan diselesaikan dalam waktu yang seminimal mungkin.

4. Vehicle Routing Problem (VRP)

5. Pengaturan rute kendaraan

6. Pewarnaan graph

7. Implementasi pada jaringan komunikasi

8. Network routing, dll.

            Sekian penjelasan oe mengenai Algoritma Ant Colony ini kurang lebihnya oe minta maaf dan terimakasih.

Wassalamualaikum Wr.Wb.

Untuk temen-temen yang ingin mencari informasi tentang Algoritma Djikstra bisa klik link dibawah ini.

-----Algoritma Dijksrra-----

Read More

Measurement Spasial

MEASUREMENT SPASIAL

==SIDS==

Assalamualaikum readerss.... selamat datang di postingan oe saat ini, pada pos kali ini oe akan membahas tentang measurement. Oke langsung saja kita menuju ke pembahasannya

 

Measurement

Measurement atau pengukuran adalah proses pemberian angka atau usaha memperoleh deskripsi numeric dari suatu tingkatan dimana seseorang peserta didik telah mencapai karakteristik tertentu. Pengukuran berkaitan erat dengan proses pencarian atau penentuan nilai kuantitatif.

Perhitungan

- jarak antara dua titik

- jarak terpendek antara dua titik

- luas area/polygon

Dalam topik kali ini measurement yang dimaksud adalah pengukuran atau perhitungan jarak dua titik lokasi, jarak terpendek dua titik, luas area. Perhitungannya dapat dilakukan dengan menggunakan Euclidean Distance atau yang lainnya, perhitungan dilakukan untuk mengukur jarak lurus dari setiap sel dari sumber lokasi ke tujuan. Didasari oleh teori Pythagoras

Euclidean Distance

Euclidean distance adalah perhitungan jarak dari 2 buah titik dalam Euclidean space. Euclidean space diperkenalkan oleh Euclid, seorang matematikawan dari Yunani sekitar tahun 300 B.C.E. untuk mempelajari hubungan antara sudut dan jarak. Euclidean ini berkaitan dengan Teorema Phytagoras dan biasanya diterapkan pada 1, 2 dan 3 dimensi. Tapi juga sederhana jika diterapkan pada dimensi yang lebih tinggi.

Pada 1 dimensi

Misalkan kita ingin menghitung jarak Euclidean 1 dimensi. Titik pertama adalah 4, titik kedua adalah -10. Caranya adalah kurangkan -10 dengan 4. sehingga menghasilkan -14. Carilah nilai absolut dari nilai -14 dengan cara mempangkatkannya sehingga mendapat nilai 196. Kemudian akarkan sehingga mendapatkan nilai 14. Sehingga jarak euclidean dari 2 titik tersebut adalah 14.

 Pada 2 dimensi

Koordinat jarak

Caranya hampir sama. Misalkan titik pertama mempunyai kordinat (1,2). Titik kedua ada di kordinat (5,5). Caranya adalah kurangkan setiap kordinat titik kedua dengan titik yang pertama. Yaitu, (5-1,5-2) sehingga menjadi (4,3). Kemudian pangkatkan masing-masing sehingga memperoleh (16,9). Kemudian tambahkan semuanya sehingga memperoleh nilai 16+9 = 25. Hasil ini kemudian diakarkan menjadi 5. Sehingga jarak euclideannya adalah 5.

Rumus Euclid

Sehingga dari Formula diatas dapat kita implementasi untuk menghitung jarak menjadi :

Rumus Jarak Euclide

Raster GIS Measurement

1. Pythagorean Distance / Euclidean Distance

Menghitung panjang atau jarak antara dua titik menggunakan rumus pythagoras.

2. Manhattan Distance

Menghitung panjang atau jarak antara dua titik dengan menghitung jumlab sel yang dilalui oleh garis tersebut.

3. Proximity Distance

Menghitung panjang atau jarak antara dua titik dengan perkiraan. Proximity mirip dengan pythagorean, tetapi diterapkan pada setiap pixel. 

4. Perimeter and Area

Menghitung keliling (perimeter) dan luas (area) dari sebuah polygon dengan menggunakan rumus geometri dengan satuan cell unit.

contoh dari masing-masing pengukuran:

Vector GIS Measurement

Pada pengukuran vektor, pengukuran panjang atau jarak menggunakan rumus pythagoras, dan pengukuran luas dan keliling menggunakan rumus geometri.

contoh pengukuran vektor:

Sekian pembahasan oe kali untuk kurang lebihnya oe mohon maaf.....

Wassalamualaikum Wr.Wb

Read More