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

Analisis Spasial

ANALISIS SPASIAL

==SIDS==

Assalamualaikum readers, jumpa lagi dengan oe, sudah cukup lama oe tidak ngepos di blog dan kali ini oe akan memposting tentang Spasial Analisis. Buat yang penasaran apa itu spasial analisis langsung aja dibawah ini penjelasannya......

·         Definisi

Definisi dari Analisis Spasial adalah teknik - teknik yang dapat digunakan dalam pengolahan data SIG. Hasil analisis data spasial ini sangat bergantung dari lokasi objek yang dianalisisi.

·         Manfaat

Manfaat dari analisis spasial ini tergantung dari fungsi yang dilakukan. Ringkasan dari manfaat tersebut adalah sebagai berikut :

-          Membuat, memilih, memetakan, dan menganalisis data raster berbasis sel.

-          Melaksanakan analisis data vektor/raster yang terintegrasi.

-          Mendapatkan informasi baru dari data yang sudah ada.

-          Memilih informasi dari beberapa layer data.

-          Mengintegrasikan sumber data raster dengan data vektor.

·         Jenis Analisis Spasial

1.      Query basis data Query basisdata digunakan untuk memanggil atau mendapatkan kembali atribut data tanpa mengganggu atau mengubah data yang sudah ada. Fungsi dari query basisdata ini dapat dilakukan dengan mudah dengan mengklik feature yang diinginkan. Namun untuk query yang lebih kompleks dapat dilakukan dengan pernyataan kondisional (conditional statement). Pernyataan kondisional tersebut melibatkan operasi logis, yaitu AND, OR, NOT, XOR. Gambar berikut ini adalah contoh dari operasi logis yang dimaksud untuk penggabungan dua kondisi.

2.      Pengukuran Analisis spasial dapat dilakukan dengan fungsi pengukuran. Fungsi pengukuran yang dimaksud adalah sebagai berikut :

a.       Jarak. Pengukuran jarak yang dimaksud adalah menghitung jarak antar dua titik. Pengukuran jarak ini dapat dilakukan dengan mengklik kedua titik tersebut, atau dapat juga dengan menggunakan query.

b.      Luas. Fungsi luas ini dapat digunakan untuk menghitung luas suatu wilayah unsur-unsur spasial. Wilayah tersebut dapat berupa poligon (vektor) ataupun juga wilayah yang bertipe raster.

c.       Kelilling. Fungsi keliling ini digunakan untuk menghitung keliling (parameter) unsur-unsur spasial. Unsur-unsur spasial tersebut dapat bertipe poligon (vektor) dan juga raster.

d.      Centroid. Fungsi digunakan untuk menentukan koordinat titik pusat dari unsur-unsur spasial yang bertipe poligon (raster).

3.      Fungsi Kedekatan Fungsi kedekatan adalah sebuah fungsi untuk menghitung jarak dari suatu titik, garis, ataupun batas poligon. Salah satu fungsi kedekatan yang paling banyak digunakan adalah dengan buffer. Buffer adalah analisis spasial yang akan menghasilkan unsur-unsur spasial yang bertipe poligon. Contoh dari fungsi buffer terdapat pada gambar disamping ini. 4. Overlay Overlay adalah bagian penting dari analisis spasial. Overlay dapat menggabungkan beberapa unsur spasial menjadi unsur spasial yang baru. Dengan kata lain, overlay dapat didefinisikan sebagai operasi spasial yang menggabungkan layer geografik yang berbeda untuk mendapatkan informasi baru. Overlay dapat dilakukan pada data vektor maupun raster.

4.      Pengubahan Unsur-Unsur Spasial

Ø  Union, Merge, atau Combine Pada pengolahan data SIG, seringkali harus melakukan penggabungan antar unsur-unsur spasial. Penggabungan tersebut dapat menggunakan analisis spasial, yaitu union, merge, atau combine. Penggabungan ini dapat menjadikan beberapa unsur spasial menjadi satu unsur spasial saja tanpa mengubah beberapa unsur spasial yang digabungkan tersebut. Ilustrasi dari fungsi ini dapat dilihat pada gambar disamping ini.

Ø  Delete, Erase, atau Cut Fungsi analisis spasial ini digunakan untuk menghapus unsur-unsur spasial yang dirasa tidak perlu ditampilkan. Fungsi ini hanya akan menghapus unsur-unsur spasial yang terpilih saja.

5.      Jenis-jenis Analisis Spasial

Ø  Split atau Clip Fungsi analisis spasial ini bertujuan untuk menghasilkan unsur spasial baru dengan cara memotongnya dari unsur spasial lainnya. Ilustrasi dari fungsi analisis spasial ini dapat dilihat pada gambar disamping ini.

Ø  Intersect Intersect adalah sebuah fungsi pada analisis spasial untuk menghasilkan unsur spasial baru dari dua atau lebih unsur spasial. Fungsi ini menghasilkan unsur spasial baru dari irisan dua atau lebih unsur spasial sebelumnya. Ilustrasinya terdapat pada gambar berikut ini

Sekian dulu pos oe untuk kali ini semoga bermanfaat terimakasih........

Wassalamualaikum....

Read More