Cara Kerja Algoritma Dijkstra

Contributor Cecilia




Step By Step Cara Kerja Algoritma Dijkstra

Algoritma Dijkstra dapat digunakan untuk menyelesaikan permasalah rute terpendek dari sebuah titik asal menuju titik tujuan dalam sebuah grafik berbobot. Rute terpendek diperoleh dari dua buah titik yang total bobotnya paling mimum atau paling kecil jika ditotalkan dari semua titik dalam jaringan grafik.

Ide dari algoritma ini sangat sederhana. Algoritma Dijkstra memilih titik (sumber) dan menetapkan kemungkinan biaya optimum (yaitu tak terhingga) ke setiap titik lainnya. Langkah berikutnya akan mencoba untuk meminimalkan biaya untuk setiap titik. Biaya yang dimaksud disini adalah jarak atau waktu yang diambil untuk mencapai titik tujuan dari titik sumber.

Berikut merupakan beberapa notasi yang digunakan dalam Algoritma Dijkstra (Dharam, 2015), yaitu: 
a. Grafik G
b. Satu set simpul atau titik V (Vertex)
c. Seperangkat sisi E (dimana setiap sisi memiliki berat non-negatif)
d. Titik awal V

Perlu diperhatikan bahwa simbol “elemen”, , menunjukkan bahwa elemen di sisi kiri simbol terkandung dalam sisi lain simbol. Misalnya, V menjelaskan bahwa s adalah elemen dari V. Berarti, dalam hal ini s adalah titik yang terdapat di dalam grafik.

Secara umum, cara kerja Algorithma Dijkstra adalah sebagai berikut:
  1. Berilah nilai bobot (jarak) dari satu titik ke titik lainnya, kemudian tentukan nilai 0 pada titik awal dan nilai tak hingga (∞) pada titik yang lain atau titik yang belum terisi.
  2. Tentukan semua titik yang belum dilewati dan aturlah titik awal sebagai titik keberangkatan.
  3.  Dari titik keberangkatan, pertimbangkan titik lain yang belum terlewati dan hitung jaraknya dari titik keberangkatan. Pada langkah ke-3 ini, misalnya titik A ke titik B memiliki nilai (jarak) 5 dan dari titik B ke titik C bernilai 2. Maka, jarak ke titik C melewati titik B adalah 5 + 2 = 7. Jika jarak ini lebih kecil dari sebelumnya yang telah dicatat, hapus data lama dan simpan ulang nilai (jarak) yang baru.
  4. Ketika setiap jarak terhadap titik lain telah dipertimbangkan, tandai titik yang telah dilewati sebagai ‘titik terlewati’. Titik terlewati tidak akan pernah diperiksa kembali, dan jarak yang disimpan adalah jarak terakhir dari titik keberangkatan dan yang paling minimal nilainya (jaraknya).
  5. Tentukan titik belum terlewati dengan nilai (jarak) terkecil dari titik keberangkatan, sebagai titik keberangkatan selanjutnya, dan lanjutkan dengan mengulang kembali langkah ke-3.


Step 1 : Pengambilan Data

          Ketika menyelesaikan Algorithma Dijkstra, dibutuhkan data untuk melakukan perhitungan nilai (jarak) minimum. Dalam hal ini, data diambil berdasarkan nilai (jarak) atau biaya yang dapat diperoleh melalui posisi koordinat suatu wilayah. Posisi koordinat dapat diambil melalui Google Maps atau layanan serupa yang memiliki pemetaan suatu wilayah.

Untuk pengambilan data ini, perlu dicatat bahwa setiap koordinat yang ambil harus bernilai positif. Jika koordinat tersebut bernilai negative, maka algorithma ini tidak dapat dilakukan. Setelah mendapatkan titik koordinat tersebut, dilakukan pencarian nilai (jarak) atau biaya antar titik yang berhubungan atau yang ada di sekitarnya.

Step 2 : Membuat Skema

           Skema merupakan suatu bentuk rancangan atau kerangka secara garis besar yang memuat gambaran umum dari apa yang akan diperhitungkan. Skema yang dibuat berupa gambar antar titik yang saling terhubung oleh garis sesuai dengan posisi koordinat yang telah didapat sebelumnya.


Gambar diatas merupakan contoh dari sebuah skema yang menggambarkan nilai (jarak) antar titik yang berhubungan. Skema diatas juga memberikan informasi bahwa nilai (jarak) tiap titik bernilai positif dan titik awal keberangkatan dimulai dari titik 1.

contoh skema


Step 3 : Membuat Tabel Perhitungan

          Langkah berikutnya adalah membuat tabel perhitungan, dimana langkah ini sangat penting karena tabel ini akan menentukan proses perhitungan secara keseluruhan. Proses perhitungan dengan tabel dapat dikatakan benar apabila jumlah step yang dilakukan berjumlah seluruh titik ditambah satu. Misal ada 6 titik, maka step yang dilakukan ada 7.

Contohnya dalam tabel ini (Girsang, 2017), yang pertama dilakukan adalah memberikan nilai awal titik keberangkatan (V1) yaitu 0, dan nilai tak hingga (∞) kepada titik yang lain. Kemudian membandingkan titik dengan nilai (jarak) terkecil dengan titik lain yang terhubung dengan melakukan perhitungan nilainya. Proses atau langkah tersebut terus berlanjut hingga ditemukan nilai (jarak) terkecil atau minimum dari titik awal hingga ke titik tujuan.



Step 4 : Menentukan Nilai (Jarak) Tiap Titik

          Setelah selesai membuat tabel, maka didapatkan nilai (jarak) semua titik yang terhubung dan telah dilewati dari titik awal hingga ke titik tujuan.
1. V1 memiliki jalur terpendek menuju V2 tanpa perantara dengan nilai (jarak) 3
2. V1 memiliki jalur terpendek menuju V3 tanpa perantara dengan nilai (jarak) 4
3. V1 memiliki jalur terpendek menuju V4 tanpa perantara dengan nilai (jarak) 2
4. V1 memiliki jalur terpendek menuju V5 melalui V4 dengan nilai (jarak) 3
5. V1 memiliki jalur terpendek menuju V6 melalui V5 dengan nilai (jarak) 5

Step 5 : Kesimpulan

                Pada langkah terakhir ini, dapat disimpulkan bahwa nilai (jarak) terpendek dari titik awal (V1) menuju titik tujuan (V6) adalah 5, dengan lintasan melalui V1 V4 V5 V6. 

Algoritma Djikstra

by Contributor Cecilia



1. Tentang Algorithma Dijkstra


       Algoritma ini ditemukan oleh Edsger Wybe Dijkstra, seorang ilmuwan komputer asal Belanda, yang dipublikasikan pada tahun 1959 dalam sebuah jurnal Numerische Mathematik dengan judul “A Note on Two Problems in Connexion with Graphs”.

Edsger Wybe Dijkstra

       Djisktra berpikir tentang permasalahan lintasan terpendek ketika bekerja di Mathematical Center, Amsterdam pada tahun 1956. Pada masa itu, Djisktra bekerja sebagai programmer yang menunjukkan kemampuan dari komputer baru yaitu ARMAC dengan tujuan untuk memilih solusi dari masalah yang ada melalui komputer yang dapat dipahami oleh orang-orang yang tidak menggunakan komputer. Dia merancang Algoritma Djikstra ini untuk diterapkan dalam ARMAC untuk peta transportasi dari kota ke kota di Belanda. Algoritmanya baru diterbitkan tiga tahun kemudian, pada tahun 1959.


2 Kegunaan Algoritma Dijkstra


Algoritma Dijkstra sangat populer dalam penyelesaian masalah pencarian rute atau lintasan terpendek dari berbagai pilihan rute atau lintasan. Algoritma ini sering digunakan karena lebih efektif dan efisien dari sisi waktu, serta penyelesaian masalahnya dilakukan langkah demi langkah sehingga membuat pembaca mudah memahami.
Dengan adanya Algoritma Dijkstra, permasalahan tentang pencarian rute atau lintasan terpendek dapat diselesaikan dan menghasilkan solusi yang dapat membantu penggunanya dalam mengambil keputusan.


3 Kelebihan Algoritma Dijkstra

  • menentukan rute atau lintasan tercepat dengan waktu yang lebih cepat dibandingkan dengan algoritma lainnya
  • mempermudah kita dalam mengetahui jarak atau lintasan terpendek dari suatu titik tertentu ke semua titik yang lain.
  • menampilkan visualisasi data dalam bentuk peta jika diterapkan dalam system geografis.
  • memudahkan pembaca dalam memahami dan membaca penampilan rute atau peta
  • Lintasan yang terdapat di dalam rute atau peta dapat diberi warna sehingga semakin memudahkan dan membuat penampilan Algoritma Dijkstra lebih menarik, karena setiap warna membedakan dari titik yang lain.
  • dapat digunakan untuk memetakan rute-rute alternative jika rute utama mengalami hambatan.


4. Kekurangan Algoritma Dijkstra

  • Penerapan Algoritma Dijkstra dalam sebuah system akan terputus dari web server jika terdapat suatu titik pada graf yang berdiri sendiri atau tidak terhubung.
  • Nilai titik yang digunakan harus bernilai positif, karena akan merusak perhitungan algoritma jika nilai titiknya negatif.

5. Pseudocode Algoritma Dijkstra



Cara Kerja Algoritma Naive Bayes


Step By Step Cara Kerja Algoritma Naïve Bayes
Contributor: Triesta Arviana Haryadinanti

  • Penjelasan mengenai tahapan-tahapan pengerjaan algoritma Naïve Bayes akan menggunakan contoh berikut untuk mempermudah pemahaman: 
  • Di sebuah universitas, terdapat data set mahasiswa sebagai berikut:

Tabel 1 Contoh Data Mahasiswa

No.
Jenis kelamin
Status mahasiswa
Status pernikahan
IPK
semester
1-6
Status kelulusan
1
Laki - laki
Mahasiswa
Belum
3.17
Tepat
2
Laki - laki
Bekerja
Belum
3.30
Tepat
3
Perempuan
Mahasiswa
Belum
3.01
Tepat
4
Perempuan
Mahasiswa
Menikah
3.25
Tepat
5
Laki - laki
Bekerja
Menikah
3.20
Tepat
6
Laki - laki
Bekerja
Menikah
2.50
Terlambat
7
Perempuan
Bekerja
Menikah
3.00
Terlambat
8
Perempuan
Bekerja
Belum
2.70
Terlambat
9
Laki - laki
Bekerja
Belum
2.40
Terlambat
10
Perempuan
Mahasiswa
Menikah
2.50
Terlambat
11
Perempuan
Mahasiswa
Belum
2.50
Terlambat
12
Perempuan
Mahasiswa
Belum
3.50
Tepat
13
Laki - laki
Bekerja
Menikah
3.30
Tepat
14
Laki - laki
Mahasiswa
Menikah
3.25
Tepat
15
Laki - laki
Mahasiswa
Belum
2.30
Terlambat

  •  Berpegangan pada rumus berikut:

dimana
Y = status kelulusan à kelas kejadian
X1 = jenis kelamin à variabel pertama
X2 = status mahasiswa à variabel kedua
X3 = status pernikahan à variabel ketiga
X4 = IPK à variabel keempat

  • Kemudian universitas ingin menambah sebuah data sebagai berikut:
  • Universitas akan menggunakan Naïve Bayes untuk mendapatkan hasil mengenai status kelulusan mahasiswa tersebut.

Step 1: Menghitung probabilitas total setiap kelas kejadian

  • Tahap pertama yang perlu dilakukan adalah menghitung probabilitas total masing-masing kelas kejadian. Caranya adalah dengan membagi jumlah data kelas kejadian dengan jumlah seluruh data di tabel.
  • Untuk contoh di atas, maka perhitungan menjadi seperti berikut:
    • P(Y = tepat)  = 8/15   à jumlah data kelas “tepat” pada kejadian status kelulusan” dibagi jumlah seluruh data
    • P(Y = terlambat) = 7/15 à jumlah data kelas “terlambat” pada kejadian status kelulusan” dibagi jumlah seluruh data

Step 2: Menghitung probabilitas detil variabel dalam kelas

  • Tahap kedua adalah menghitung probabilitas setiap kasus. Perhitungan dilakukan dengan menghitung jumlah kasus yang terjadi di masing-masing variabel, sesuai yang bersangkutan dengan data tambahan, dengan masing-masing kelas kejadian.
  • Untuk contoh di atas, maka perhitungannya adalah sebagai berikut:
    •  Variabel jenis kelamin (X1):
      • P(jenis kelamin = laki-laki | Y = tepat) = 5/8 à jumlah data jenis kelamin “laki-laki” dengan kejadian status kelulusan “tepat” dibagi jumlah data kelas “tepat”.
      • P(jenis kelamin = laki-laki | Y = terlambat) = 3/7 à jumlah data jenis kelamin “laki-laki” dengan kejadian status kelulusan “terlambat” dibagi jumlah data kelas “terlambat”.
    • Variabel status mahasiswa (X2)
      •  P(status mahasiswa = mahasiswa | Y = tepat) = 5/8 à jumlah data status mahasiswa “mahasiswa” dengan kejadian status kelulusan “tepat” dibagi jumlah data kelas “tepat”.
      •  P(status mahasiswa = mahasiswa | Y = terlambat) = 3/7 à jumlah data status mahasiswa “mahasiswa” dengan kejadian status kelulusan “terlambat” dibagi jumlah data kelas “terlambat”.
    • Variabel status pernikahan (X3):
      •  P(status pernikahan = belum | Y = tepat) = 4/8 à jumlah data status pernikahan “belum” dengan kejadian status kelulusan “tepat” dibagi jumlah data kelas “tepat”.
      • P(status pernikahan = belum | Y = terlambat) = 4/7 à jumlah data status pernikahan “belum” dengan kejadian status kelulusan “terlambat” dibagi jumlah data kelas “terlambat”.

    • Variabel IPK (X4):
      • P(IPK = 2.70| Y = tepat) = 0/8 à jumlah data IPK “2.70” dengan kejadian status kelulusan “tepat” dibagi jumlah data kelas “tepat”.
      • P(IPK = 2.70| Y = terlambat) = 1/7 à jumlah data IPK “2.70” dengan kejadian status kelulusan “terlambat” dibagi jumlah data kelas “terlambat”.

Step 3: Mengalikan semua variabel kelas

  • Tahap ketiga adalah mengalikan semua hasil variabel pada setiap kelas kejadian. Untuk contoh di atas, maka perhitungannya adalah sebagai berikut:
    • Kelas kejadian status kelulusan “tepat”:
      • P (jenis kelamin = laki-laki), (status mahasiswa = mahasiswa), (status pernikahan = belum), (IPK = 2.70 ) | TEPAT)
        = P(jenis kelamin = laki-laki |Y = tepat)
           x P(status mahasiswa = mahasiswa | Y = tepat) 
           x P(status pernikahan = belum | Y = tepat)
           x P(IPK = 2.70 | Y = tepat)
        = 5/8 x 5/8 x 4/8 x 0/8 x 8/15
        = 0
    • Kelas kejadian status kelulusan “terlambat”:
      • P (jenis kelamin = laki-laki), (status mahasiswa = mahasiswa), (status pernikahan = belum), (IPK = 2.70 ) | TERLAMBAT)
        = P(jenis kelamin = laki-laki |Y = terlambat)
           x P(status mahasiswa = mahasiswa | Y = terlambat)
           x P(status pernikahan = belum | Y = terlambat)
           x P(IPK = 2.70 | Y = terlambat)
        = 3/7 x 3/7 x 4/7 x 1/7 x 7/15
        = 0,00699

Step 4: Membandingkan hasil antar kelas

  • Pada tahap terakhir ini, yang perlu dilakukan hanya membandingkan hasil akhir kelas-kelas yang ada. Hasil atau keputusan yang diambil adalah hasil yang paling besar.
  • Untuk contoh di atas, hasilnya adalah:
    • P(tepat) = 0
    • P(terlambat) = 0,00699
    • Hasil P(terlambat) lebih besar dari P(tepat) maka keputusannya adalah “TERLAMBAT”.

Pengertian Algoritma Naive Bayes


Algoritma Naive Bayes
Contributor: Triesta Arviana Haryadinanti

1. Tentang Algoritma Naive Bayes

Naïve Bayes merupakan metode klasifikasi yang berdasarkan pada Teorama Bayes. Dinamakan Teorema Bayes karena disesuaikan dengan nama penemunya, yaitu Reverend Thomas Bayes, walaupun sebenarnya ada beberapa penelitian yang mengatakan bahwa Teorema Bayes telah ditemukan oleh orang lain sebelum Reverend Thomas Bayes.
Reverend Thomas Bayes merupakan seorang ilmuwan dari Inggris. Reverend Thomas Bayes mempelajari hal-hal mengenai klasifikasi, namun setelah beliau meninggal, temannyalah yang menggantikannya untuk mempresentasikan penelitiannya.

Reverend Thomas Bayes

Algoritma Naïve Bayes kurang lebih ditemukan pada pertengahan abad ke-18. Pada saat itu, algoritma ini dikenal dengan banyak nama. Meskipun begitu, algoitma ini populer dikenal sebagai metode pengelompokkan teks dan pengkategorian menggunakan frekuensi kata-kata.
Sesuai namanya, algoritma Naïve Bayes disebut demikian karena cirinya yang “naïve”, yaitu mengasumsikan bahwa setiap variabelnya independen, bebas antara satu sama lain, tidak memiliki hubungan atau korelasi yang bisa memengaruhi hasilnya.
Walaupun Naïve Bayes dianggap memiliki asumsi yang terlalu sederhana, namun Naïve Bayes telah bekerja dengan baik untuk menangani masalah-masalah nyata yang rumit. Seperti pada tahun 2004, sebuah hasil analisis menyatakan bahwa ada alasan mengenai keakuratan Naïve Bayes yang mana keakuratan tersebut bertentangan dengan anggapan orang-orang. Pada tahun 2006, pengklasifikasian dengan Naïve Bayes menampilkan performa dan hasil yang lebih baik dibandingkan dengan metode-metode lain seperti random forest dan boosted trees. 

2. Kegunaan Naïve Bayes

·           Mengklasifikasikan dokumen teks seperti teks berita ataupun teks akademis
·           Sebagai metode machine learning yang menggunakan probabilitas
·           Untuk membuat diagnosis medis secara otomatis
·           Mendeteksi atau menyaring spam


3. Kelebihan Naïve Bayes

·           Bisa dipakai untuk data kuantitatif maupun kualitatif
·           Tidak memerlukan jumlah data yang banyak
·           Tidak perlu melakukan data training yang banyak
·           Jika ada nilai yang hilang, maka bisa diabaikan dalam perhitungan.
·           Perhitungannya cepat dan efisien
·           Mudah dipahami
·           Mudah dibuat
·           Pengklasifikasian dokumen bisa dipersonalisasi, disesuaikan dengan kebutuhan setiap orang
·           Jika digunakan dalaam bahasa pemrograman, code-nya sederhana
·           Bisa digunakan untuk klasifikasi masalah biner ataupun multiclass

4. Kekurangan Naïve Bayes

·           Apabila probabilitas kondisionalnya bernilai nol, maka probabilitas prediksi juga akan bernilai nol
·           Asumsi bahwa masing-masing variabel independen membuat berkurangnya akurasi, karena biasanya ada korelasi antara variabel yang satu dengan variabel yang lain
·           Keakuratannya tidak bisa diukur menggunakan satu probabilitas saja. Butuh bukti-bukti lain untuk membuktikannya.
·           Untuk membuat keputusan, diperlukan pengetahuan awal atau pengetahuan mengenai masa sebelumnya. Keberhasilannya sangat bergantung pada pengetahuan awal tersebut
·           Banyak celah yang bisa mengurangi efektivitasnya
·          Dirancang untuk mendeteksi kata-kata saja, tidak bisa berupa gambar