TUGAS-2 MATA KULIAH SISTEM PAKAR

Pakar adalah sebuah sistem yang menghasilkan keputusan atas dasar basis pengetahuan yang dimiliki oleh seorang ahli, penerapan sistem pakar meliputi bidang-bidang diantaranya dalam mengambil keputusan strategis organisasi, keputusan untuk mendiagnosis penyakit, memberikan bantuan untuk pengobatan penyakit yang didiagnosis, dan lain sebagainya (Kartikeyn, Desai, 2015).

Kepakaran adalah suatu pengetahuan yang diperoleh dari pelatihan, membaca, dan pengalaman. Kepakaran memungkinkan para ahli dapat mengambil keputusan lebih cepat dan lebih baik daripada seseorang yang bukan pakar (Sutojo, 2017).

Data merupakan sekumpulan teks, angka, dan simbol yang bersumber dari fakta, namun belum memiliki arti. Data diperoleh berdasarkan fakta-fakta baik secara pengukuran ataupun pernyataan yang tidak bisa diukur, untuk dapat memberikan sebuah arti maka data harus diolah agar menghasilkan suatu informasi. Contoh : 1, 2, 3, Sani, Bobby, Nary, dll (Advernesia, 2017).

Informasi merupakan hasil output dari sebuah pengolahan data baik secara bahasa ataupun matematis, dalam perkembangan saat ini data diolah menggunakan bantuan komputer yakni secara komputasi. Setelah data tersebut diolah menjadi sebuah informasi, maka data itu mempunyai arti atau pengetahuan. Contoh : 1, 2, 3 adalah list angka yang merupakan absen mahasiswa (Advernesia, 2017).

Pengetahuan merupakan kesimpulan dari sebuah informasi yang telah memperoleh pengetahuan, secara fundamental pengetahuan dapat berupa memperoleh serangkaian fakta dan menggunakan informasi untuk memecahkan suatu masalah. Contoh : Nomor absen 3 bernama Nary (Advernesia, 2017).

Kelebihan Sistem Pakar, diantaranya :

i.    Mendukung orang awam untuk menyelesaikan perkara tanpa dukungan pakar.

ii.  Menyandang kemampuan untuk mengakses kepakaran dan keahlian para ahli, baik yang biasa ataupun yang langka.

iii.   Meningkatkan kualitas dan produktifitas.

iv.   Selaku asisten para ahli sehingga memudahkan pekerjaan para ahli.

v.    Dapat menyesuaikan waktu dalam pengutipan hasil.

Kekurangan Sistem Pakar, diantaranya :

i.    Tidak ada jaminan bahwa sistem pakar memuat 100% kepakaran yang diperlukan.

ii.  Biaya untuk arsitektur, mengimplementasikan dan merawat bisa sangat mahal terkait seberapa lengkap kemampuan tersebut.

iii. Pembangunan sistem pakar terkait ada tidaknya pakar dibidangnya sehingga pembangunannya mendapatkan hambatan (Syahromi, 2016).

Sumber pengetahuan potensial untuk pengembangan sistem pakar berasal dari pakar manusia, buku teks, dokumen multimedia, database (publik dan privat), laporan riset khusus, dan informasi yang terdapat dalam website (Munarto, 2018).

Akuisisi Pengetahuan yakni akumulasi, transfer, dan transformasi keahlian pemecah masalah dari pakar yang terdokumentasi ke dalam program komputer untuk membangun dan mengembangkan basis pengetahuan. Sumber pengetahuan potensial untuk pengembangan sistem pakar berasal dari pakar manusia, buku teks, dokumen multimedia, database (publik dan privat), laporan riset khusus, dan informasi yang terdapat dalam web. Mendapatkan pengetahuan dari seorang pakar adalah tugas kompleks yang sering menimbulkan kemacetan dalam kontruksi Expert System (ES), maka diperlukanlah knowledge engineer / pakar elisitas pengetahuan untuk berinteraksi dengan satu atau lebih pakar manusia dalam membangun basis pengetahuan dengan menyusun area persoalan dengan menginterpretasikan dan mengintegrasikan jawaban manusia, menyusun analogi, mengajukan contoh pembanding, dan menjelaskan kesulitan konseptual (Munarto, 2018).

Representasi pengetahuan adalah sebuah cara dalam menyaapabilan berbagai pengetahuan yang diperoleh ke dalam suatu diagram sehingga diketahui relasi antara pengetahuan yang satu dengan pengetahuan yang lain dan bisa digunakan dalam pengujian logika kebenarannya. Representasi pengetahuan digunakan untuk menangkap sifat penting masalah dan mempermudah prosedur pemecahan masalah dalam mengakses informasi, selain itu format representasi pengetahuan pun harus mudah dipahami sehingga programmer mampu mengekspresikan pengetahuan (Susatyono, 2021).

Mesin inferensi merupakan sebuah program yang berguna untuk memandu mekanisme penalaran terhadap suatu kondisi berdasarkan pada basis fakta yang disimpan dalam basis pengetahuan untuk mencapai penyelesaian atau kesimpulan. Dalam mekanisme tersebut, mesin inferensi menggunakan strategi pengendalian yakni sebagai panduan arah dalam melakukan mekanisme penalaran yang terdiri dari 3 teknik pengendalian, diantaranya forward chaining, backward chaining, dan gabungan dari kedua teknik tersebut (Susatyono, 2021).

Metode yang dapat digunakan pada mesin inferensi, diantaranya :

a.  Forward Chaining atau Perambatan Maju merupakan aturan-aturan diuji satu per satu dalam urutan tertentu, urutan tersebut berupa aturan ke dalam perangkat aturan atau dapat juga urutan lain yang ditentukan oleh pemakai. Dalam pengujian tersebut sistem pakar akan mengevaluasi apakah kondisinya benar atau salah. Apabila kondisinya benar, maka aturan tersebut ditembakkan dan aturan berikutnya diuji. Apabila kondisinya salah, maka aturan tersebut tidak ditembakkan dan aturan berikutnya diuji. Mekanisme pengujian aturan satu demi satu berlanjut sampai putaran lengkap melalui seluruh perangkat aturan, ketika tidak ada lagi aturan yang dapat ditembakkan maka mekanisme penalaran berhenti.

b. Backward Chaining atau Perambatan Mundur merupakan inference engine memilih suatu aturan dan menganggapnya sabagai masalah yang harus diselesaikan, dengan menggunakan perangkat aturan inference engine mulai mengevaluasi dari variabel sasaran. Kemudian diikuti dengan pemilihan salah satu subproblem untuk dievaluasi, dan subproblem yang terpilih akan dievaluasi sebagai masalah baru. Inference engine terus mencari subproblem untuk menjadi masalah baru yang akan dievaluasi sampai dengan tidak ada lagi subproblem yang ditemui, tanpa harus mempertimbangkan seluruh aturan dan tidak membuat beberapa aturan melalui perangkat aturan (Susatyono, 2021).

Penjelasan jurnal "SISTEM PAKAR UNTUK MENDIAGNOSA PENYAKIT PADA TANAMAN JAGUNG DENGAN METODE BAYES", diantaranya :

a. Masalah pada penelitian tersebut yakni meneliti dalam hal membantu setiap petani dalam menentukan pilihan pengobatan, karena banyaknya penyakit pada tanaman jagung saat ini yang membuat petani susah mendapatkan hasil karena mereka tidak dapat melakukan pendiagnosaan yang tepat sehingga tingkat produktivitas menurun.

b. Proses pembuatan sistem pakar ini metode kepastiannya teorema bayes dimana metode ini didasarkan dari kondisi awal dimana kondisi awal tersebut merupakan kondisi gejala-gejala yang ada kemudian dikenakan aturan yang sudah ditentukan lalu diambil nilai kebenaran yang paling besar untuk menentukan kesimpulan dan solusi dari gejala yang disebutkan sebelumnya. Dengan menggunakan teorema bayes ini adalah untuk mendiagnosa penyakit pada tanaman jagung dan gejala-gejala yang menyebabkan penyakit tersebut.

c. Pada penelitian tersebut, metode forward chaining digunakan untuk melakukan diagnosa hama yang menyerang tanaman padi dengan melihat ciri-ciri yang muncul pada tanaman tersebut, sistem pakar untuk mendiagnosa hama dan penyakit tanaman bawang merah menggunakan certainty factor. Penelusuran fakta tersebut menggunakan forward chaining yakni penelusuran yang dimulai dari fakta-fakta untuk menguji kebenaran hipotesis, sebuah penalaran dimana adanya penambahan fakta baru yang mengakibatkan adanya ketidakpastian. Maka dapat digunakan penalaran statistik, teori Bayes digunakan sebagai alat pengambil keputusan untuk memperbaharui tingkat kepercayaan diri dari sebuah informasi atau pengetahuan, dimulai dari perancangan sistem hingga implementasi sistem untuk melakukan pembangunan Aplikasi Sistem Pakar.

d. Kesimpulan dari penelitian tersebut dengan membangun Aplikasi Sistem Pakar untuk mendiagnosa penyakit pada tanaman jagung yang dapat menyelesaikan masalah yakni dapat menampilkan hasil diagnosa dengan cepat dan tepat berdasarkan gejala-gejala yang dimasukkan oleh pengguna, hasil diagnosa yang ditampilkan dihitung secara otomatis oleh sistem aplikasi yakni banyaknya gejala yang dipilih oleh pengguna dibagi dengan banyaknya gejala yang dimiliki suatu penyakit.

Referensi

Advernesia. (2017). Data | Pengertian Data Informasi dan Pengetahuan. Advernesia.Com.

Kartikeyn, Desai,  dan D. (2015). Sistem Pakar. 2(October), 765–770.

Munarto, R. (2018). Sistem Pakar Diagnosis. 14(1), 75–86.

Susatyono, J. D. (2021). Sistem Pakar : Kajian Konsep & Penerapannya.

Sutojo,  dkk. (2017). Kepakaran. 9–29.

Syahromi. (2016). Bab 2 landasan teori. Aplikasi Dan Analisis Literatur Fasilkom UI, 4–25.

TUGAS MATA KULIAH SISTEM PAKAR

Soal

Carilah dua buah jurnal tentang contoh implementasi sistem pakar, 1 dalam bahasa Indonesia dan 1 dari bahasa inggris, lalu buat ringkasannya dari setiap jurnal yang dipilih.

 

Jawaban

(Jurnal bahasa Indonesia)

Judul penelitian : Perancangan Sistem Pakar Diagnosa Penyakit Jantung dengan Metode Forward Chaining

Nama jurnal : Jurnal Informatika Universitas Pamulang

Nama penulis : Fajar Agung Nugroho

Tahun terbit : Vol. 3, No. 2, Juni 2018 (ISSN 2541-1004)

Rangkuman jurnal : Jantung adalah salah satu bagian organ tubuh manusia yang memiliki fungsi utama terhadap keberlangsungan hidup manusia dan tentunya akan sangat beresiko apabila jantung ini memiliki masalah, banyak terjadi kasus bahwa penyebab kematian seseorang disebabkan oleh penyakit jantung. Maka dari itu, dibutuhkanlah seorang pakar / ahli mengenai jantung serta macam-macam penyakitnya. Peneliti tersebut membuat sebuah ide untuk mendiagnosa kesehatan jantung dan mengantisipasi apabila seseorang memiliki resiko penyakit jantung dengan dibuatkannya sebuah rancangan serta implementasi yakni dengan metode forward chaining, yang diterapkan pada sebuah aplikasi berbasis website dengan memakai bahasa pemrograman PHP dan database MySQL. Dengan adanya sistem pakar ini yang nantinya akan ada beberapa pertanyaan yang akan diajukan kepada pengguna / user, setelah seluruh pertanyaan terjawab, maka akan muncul hasil diagnosa dan juga saran yang bisa membantu mencegah sebelum terjadi penyakit jantung tersebut tiba.

 

(Jurnal bahasa Inggris)

Judul penelitian : Internet of Things based Expert System for Smart Agriculture

Nama jurnal : IOT IRAN Internet Of Things

Nama penulis : Raheela Shahzadi, Javed Ferzund, Muhammad Tausif, Muhammad Asif Suryani

Tahun terbit : Vol. 7, No. 9, 2016

Rangkuman jurnal : Peneliti tersebut berpusat pada bidang pertanian, dengan segala cara dilaksanakan demi meningkatkan daya produksi serta mengurangi kerugian yakni menggunakan teknologi dan peralatan canggih berdasarkan ES (Expert System) dan IOT (Internet Of Things) yang nantinya akan menggunakan data masukan / input yang dikumpulkan dalam waktu nyata. Banyak sekali sistem pakar telah dikembangkan di berbagai belahan dunia untuk menyediakan wadah kepada seorang petani, sistem yang diusulkan diantaranya memberikan diagnosa penyakit, serangan gulma dan hama, serta memberikan rekomendasi pestisida untuk gulma, penyakit, dan hama tersebut. Serta memberikan prediksi penyakit berdasarkan data sensor, menyediakan penjadwalan irigasi berdasarkan suhu dan kandungan tanah, hal tersebut juga bisa memberikan sebuah dosis irigasi.

Referensi

Ratih Fitri Aini, M. H. M. M. (2016). Perancangan Sistem Pakar Diagnosa Penyakit Ayam Dengan Metode Forward Chaining. J I M P - Jurnal Informatika Merdeka Pasuruan, 1(2), 75–79. https://doi.org/10.37438/jimp.v1i2.21

Shahzadi, R., Ferzund, J., Tausif, M., & Asif, M. (2016). Internet of Things based Expert System for Smart Agriculture. International Journal of Advanced Computer Science and Applications, 7(9). https://doi.org/10.14569/ijacsa.2016.070947

TUGAS MATA KULIAH DATA MINING

 Soal

1. Carilah 6 definisi data mining yang bersumber dari jurnal atau lainnya. Dengan ketentuan : 3 bahasa Indonesia dan 3 bahasa asing. Lakukan parafrase dalam mendefinisikan dan tuliskan sumber dari setiap definisinya. Serta rangkum simpulan akhirnya.

2. Berikanlah 3 contoh implementasi data mining yang ada pada saat ini.

3. Download 1 jurnal dalam bahasa Inggris tentang implementasi data mining dan buat rangkuman nya.

 

Jawaban

1. Definisi ke-1 data mining dalam website cermati.com : Data mining atau disebut juga dengan Penambangan Data yakni sebuah cara untuk mengakumulasikandata atau keterangan signifikan yang diharapkan untuk pihak terkait, via sekumpulan data yang lebih luas dan kompleks / Big data. Cara mengakumulasikan tersebut kerap kali menggunakan prosedur matematika, statistika, sampai pendayagunaan artificial intelligence / AI (Saretta, 2021). Definisi ke-2 data mining dalam website gurupendidikan.co.id : Data mining adalah sebuah perangkat yang diperuntukkan bagi klien dalam mengakses data yang banyak secara cepat. Data mining ini juga menjabarkan sekumpulan metode-metode yang bertujuan mendapatkan prototype yang tidak ditemukan terhadap sekumpulan data (Kurniawan, 2021). Definisi ke-3 data mining dalam website ekrut.com : Data mining merupakan sebuah cara untuk mendapatkan prototype, association, ataupun anomaly pada kumpulan data yang luas dalam memperkirakan hasil nantinya. Selain itu, Data mining pun disebut juga dengan istilah lain seperti halnya Pattern analysis, Knowledge discovery, Knowledge extraction, dan Information harvesting (Handayani, 2021). Definisi ke-4 dalam website techtarget.com : Data mining is a way of improving large amounts of data to identify prototypes and relationships that can help solve business problems via data analysis. Data mining is generally used by companies to predict the future and make accurate business policies (Stedman, 2021). Definisi ke-5 dalam website investopedia.com : Data mining is a method used for industry in transforming primary data into useful information. Data mining is concerned with the efficient accumulation of data and computer operations performed (Twin, 2021).Definisi ke-6 dalam website ibm.com : Data mining is a scientific discovery in databases, besides that data mining is also generally used for companies (retail, banking, insurance), research (astronomy, medicine), and government security (Clifton, 2022). Simpulan akhir : Jadi, kesimpulan yang didapatkan dari ke-6 definisi data mining tersebut bahwa Data mining adalah sebuah cara untuk mengakumulasikan data secara cepat yang diharapkan oleh pihak terkait, via sekumpulan Big Data. Cara mengakumulasikan tersebut kerap kali menggunakan prosedur matematika, statistika, hingga penggunaan artificial intelligence untuk mendapatkan prototype, association, serta anomaly yang tidak ditemukan terhadap sekumpulan data dalam memperkirakan hasil nantinya. Tentunya data mining ini berkaitan dengan akumulasi data yang efisien dan operasi komputer yang dilakukan, serta dapat membantu memecahkan masalah bisnis melalui analisis data yang pada umumnya digunakan oleh perusahaan untuk memprediksi masa depan dan membuat kebijakan bisnis yang akurat yakni dengan mengubah data primer menjadi informasi yang berguna. Contoh penerapan yang digunakan oleh industri seperti Ritel, Perbankan, Asuransi, sedangkan oleh peneliti seperti Astronomi, Kedokteran, dan keamanan pemerintah.

2.  Contoh implementasi data mining yang ada pada saat ini, diantaranya :

i.   Analisis dan Manajemen Pasar

Dengan melakukan analisis kebutuhan pelanggan, yakni sebuah identifikasi produk yang paling tepat untuk pelanggan, memprediksi faktor apa saja yang dapat menarik perhatian para pelanggan, dan juga menyediakan berbagai informasi secara ringkas. Contoh sederhana dalam kehidupan sehari-hari jika kita ke supermarket seperti Alfamart atau Indomaret, coba perhatikan dalam peletakan produk-produk yang mereka jual cenderung mempunyai hubungan asosiasi yang diharapkan calon pembeli berminat untuk membeli barang yang ada disampingnya. Misalnya, peletakan produk sikat gigi berdekatan dengan pasta gigi / odol dan obat kumur.

ii.  Corporate Analysis and Risk Management

Data mining pun dapat mengontrol kualitas dan menganalisis secara kompetitif, dalam menentukan perancanaan keuangan. Contohnya dengan melakukan prediksi terhadap arus kas, analisis klaim kontinjensi, analisis cross-sectional, serta time series. Kemudian menentukan perencanaan sumber daya, contohnya meringkas dan membandingkan dari berbagai sumber daya yang ditujukan untuk pengeluaran.

iii. Analisis dan Identifikasi Perawatan

Didalam bidang kesehatan, data mining mempunyai potensi besar untuk memperbaiki sistem kesehatan yakni dengan menganalisis dan data digunakan untuk mengidentifikasikan sebuah praktik yang cocok sehingga dapat meningkatkan perawatan serta mengurangi biaya. Peneliti pada umumnya menggunakan pendekatan Database multi dimensi, Pembelajaran mesin, Soft computing, Visualisasi data dan statistic tentunya. Selain itu juga, dapat difungsikan untuk memperkirakan volume pasien didalam setiap kategori proses ditingkatkan yang bisa memberikan kepastian bahwa pasien mendapatkan perawatan yang tepat dan juga pada waktu yang tepat.

3. Judul penelitian : Implementation of Data Mining Techniques for Meteorological Data  Analysis (A case study for Gaza Strip)

Nama jurnal : International Journal of Information and Communication Technology Research

Nama penulis : Sarah N. Kohail, Alaa M. El-Halees

Tahun terbit : Volume 1 No. 3, July 2011. (ISSN-2223-4985)

Link : https://iugspace.iugaza.edu.ps/handle/20.500.12358/25203

Rangkuman jurnal : Didalam jurnal tersebut telah menerapkan penemuan pengetahuan dalam hal pemrosesan yakni untuk mengekstrak pengetahuan dari cuaca di kota Gaza itu dalam bentuk himpunan data, sekumpulan data yang dimana mencakup 9 tahun periode dari tahun 1977 hingga 1985 dalam pengamatan cuaca harian. Dengan melewati seluruh proses penemuan pengetahuan serta menerapkan berbagai data teknik penambangan seperti halnya analisis outlier, prediksi, klasifikasi, penambangan asosiasi, dan juga pengelompokkan. Data mining telah memberikan sebuah manfaat yang sangat besar dan akurat yakni diantaranya pengetahuan dalam bentuk aturan, model, dan grafik visual. Pengetahuan tersebut dapat dipakai untuk mendapatkan prediksi yang berguna dan mendukung pengambilan keputusan untuk berbagai sektor, pekerjaan di masa yang akan datang termasuk membangun adiptif dan metode data mining yang dapat mempelajari secara dinamis untuk mencocokkan sifat-sifat cuaca yang berubah-ubah dengan waktu yang begitu signifikan dan kejadian hal-hal yang tak terduga. Maka dari itu, metode-metode data mining tersebutlah yang dapat mengantisipasi sebelum bilamana terjadi sesuatu.

Referensi

Clifton, C. (2022). data mining computer science. Britannica.Com. https://www.britannica.com/technology/data-mining/Pattern-mining

Handayani, M. T. (2021). Data mining: Pengertian, proses, manfaat, dan 3 contoh penerapannya. Ekrut.Com. https://www.ekrut.com/media/data-mining-adalah

Kohail, S., & El-Halees, A. (2011). Implementation of Data Mining Techniques for Meteorological Data Analysis (A case study for Gaza Strip). International Journal of Information, 1(3), 96–100. http://scholar.google.com/scholar?hl=en&btnG=Search&q=intitle:Implementation+of+Data+Mining+Techniques+for+Meteorological+Data+Analysis+(+A+case+study+for+Gaza+Strip+)#0

Kurniawan, A. (2021). Materi Tentang Data Mining Lengkap. Gurupendidikan.Co.Id. https://www.gurupendidikan.co.id/data-mining/

Saretta, I. R. (2021). Data Mining: Pengertian, Fungsi, Penerapan, dan Metode Pengambilannya. Cermati.Com. https://www.cermati.com/artikel/data-mining-pengertian-fungsi-penerapan-dan-metode-pengambilannya

Stedman, C. (2021). data mining. Techtarget.Com. https://www.techtarget.com/searchbusinessanalytics/definition/data-mining

TWIN, A. (2021). Data Mining. Investopedia.Com. https://www.investopedia.com/terms/d/datamining.asp

Algoritma Dijkstra dan Greedy

Algoritma Dijkstra sesuai dengan penemunya  Edsger Dijkstra, adalah sebuah algoritma yang dipakai dalam memecahkan masalah jarak terpendek untuk sebuah graf berarah. Algoritma ini dipublikasikan pada tahun 1959 dalam jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs”. Permasalahan rute terpendek dari sebuah titik ke titik akhir lain adalah sebuah masalah optimasi yang banyak digunakan untuk menguji sebuah algoritma yang diusulkan.  Permasalahan rute terpendek dianggap cukup baik untuk memperbaiki masalah optimasi, karena permasalahannya hanya menjumlahkan seluruh edge atau sisi yang dilalui namun memiliki banyak pilihan solusi.

Menurut Andrew Goldberg, seorang peneliti Microsoft Research Silicon Valley, mengatakan terdapat banyak alasan mengapa peneliti terus mempelajari masalah pencarian jalan terpendek, karena jalan terpendek adalah masalah optimasi yang relevan untuk berbagai macam aplikasi, seperti jaringan routing, game, desain sirkuit, dan pemetaan. Diskripsi matematis untuk grafik dapat diwakili G = {V. E}, yang berarti sebuah (Grafik = G) didefinisikan oleh satu set simpul (Vertex = V) dan (Edge = E).

Contoh, hitunglah jarak terdekat dari V1 ke V7 pada gambar berikut ini :

Hasil setiap stepnya dapat dilihat pada tabel berikut ini :

Dengan demikian jarak terpendek dari V1 ke V7 adalah 16 dengan jalur V1->V2->V3->V5->V6->V7

Flowchart algoritma Djikstra :

 

Jadi, algoritma Dijkstra ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya. Misalnya titik mengambarkan gedung dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

Algoritma Greedy adalah  jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah local maximum. Kebanyakan kasus, algoritma Greedy tidak akan menghasilkan solusi paling optimal, begitupun pada umumnya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat. Sebagai contoh dari penyelesaian masalah dengan algoritma Greedy, mari kita lihat sebuah masalah yang sering kita jumpai dalam kehidupan sehari-hari yaitu mencari jarak terpendek dari peta. Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta :

Dari peta yang ditampilkan di atas, dapat kita lihat bahwa terdapat beberapa jalur dari titik A ke titik B. Sistem peta pada gambar secara otomatis telah memilih jalur terpendek yakni berwarna biru. Kita akan mencoba mencari jalur terpendek juga, dengan menggunakan algoritma Greedy.

Langkah pertama yang harus kita lakukan adalah memilih struktur data yang tepat untuk digunakan dalam merepresentasikan peta. Jika kita lihat kembali, sebuah peta seperti pada gambar di atas pada dasarnya hanya menunjukkan titik-titik yang saling berhubungan, dengan jarak tertentu pada masing-masing titik tersebut. Misalnya, peta di atas dapat direpresentasikan dengan titik-titik penghubung seperti berikut ini :

Dari gambar di atas, kita dapat melihat bagaimana sebuah peta jalur perjalanan dapat direpresentasikan dengan menggunakan graph, yang lebih spesifiknya adalah graph berarah. Maka dari itu, untuk menyelesaikan permasalahan jarak terpendek ini kita akan menggunakan struktur data graph untuk merepresentasikan peta. Berikut graph yang akan digunakan :

Untuk mencari jarak terpendek dari A ke B, sebuah algoritma Greedy akan menjalankan langkah-langkah seperti berikut :

1.    Kunjungi satu titik pada graph, dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang.

2.    Cari local maximum ke titik selanjutnya.

3.   Tandai graph sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang telah ditentukan.

4.     Kembali ke langkah pertama sampai titik tujuan didapatkan.

Jika mengaplikasikan langkah-langkah di atas pada graph A ke B sebelumnya maka kita akan mendapatkan pergerakan seperti berikut :

1.      Mulai dari titik A. Ambil seluruh titik yang dapat dikunjungi.

2.      Local maximum adalah ke titik C, karena jarak ke titik C adalah yang paling dekat.

3.      Tandai titik A sebagai titik yang telah dikunjungi, dan pindah ke titik C.

4.      Ambil seluruh titik yang dapat dikunjungi dari titik C.

5.      Local maximum adaah ke D, dengan jarak 6.

6.      Tandai C sebagai titik yang telah dikunjungi, dan pindah ke D.

Dengan menggunakan algoritma Greedy pada graph di atas, hasil akhir yang akan didapatkan sebagai jarak terpendek adalah A-C-D-E-F-B. Hasi jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya adalah A-G-E-F-B. Algoritma Greedy memang tidak selamanya memberikan solusi yang optimal, dikarenakan pencarian local maximum pada setiap langkahnya, tanpa memperhatikan solusi secara keseluruhan. Gambar berikut memperlihatkan bagaimana algoritma Greedy dapat memberikan solusi yang kurang optimal :

Tetapi ingat bahwa untuk kasus umum, kerap kali algoritma Greedy memberikan hasil yang cukup baik dengan kompleksitas waktu yang cepat. Hal ini mengakibatkan algoritma Greedy sering digunakan untuk menyelesaikan permasalahan kompleks yang memerlukan kecepatan jawaban, bukan solusi optimal, misalnya pada game.

Dari implementasi yang kita lakukan, dapat dilihat bagaimana algoritma Greedy memiliki beberapa fungsionalitas dasar, yaitu :

1.      Fungsi untuk melakukan penelusuran masalah.

2.      Fungsi untuk memilih local maximum dari pilihan-pilihan pada tiap langkahnya.

3.      Fungsi untuk mengisikan nilai local maximum ke solusi keseluruhan.

4.      Fungsi yang menentukan apakah solusi telah didapatkan.

Algoritma Greedy disusun oleh elemen-elemen yang digunakan dalam penerapan algoritma Greedy antara lain :

1.     Himpunan kandidat, yaitu himpunan yang berisi elemen pembentuk solusi.

2.     Himpunan solusi, yaitu himpunan yang terpilih sebagai solusi persoalan.

3.    Fungsi seleksi, yaitu fungsi untuk memilih kandidat yang paling mungkin untuk mencapai solusi optimal.

4.  Fungsi kelayakan, yaitu fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak. Maksudnya yakni apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada.

5.    Fungsi solusi, yaitu fungsi untuk mengembalikan nilai boolean (true) jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap dan (false) jika himpunan solusi belum lengkap.

6.       Fungsi objektif, yaitu fungsi yang mengoptimalkan solusi.

Contohnya, pada masalah penukaran uang :

·     Himpunan kandidat : himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.

·     Himpunan solusi : total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.

·         Fungsi seleksi : pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.

·       Fungsi layak : memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi        jumlah uang yang harus dibayar.

·         Fungsi objektif : jumlah koin yang digunakan minimum.

Dalam mencari sebuah solusi algoritma Greedy hanya memakai 2 buah macam persoalan optimasi, yaitu :

·         Maksimasi (maxizimation).

·         Minimasi (minimization).

Jadi, algoritma Greedy merupakan algoritma yang besifat heuristik, mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang cukup baik. Meskipun tidak selalu mendapatkan solusi terbaik (optimum), algoritma Greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga algoritma ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal seperti sistem real-time atau game.

Dari kedua algoritma ini, dapat saya simpulkan bahwa perbedaan dari kedua algoritma tersebut terdapat pada masalah optimasi dalam sebuah program. Memang algoritma Greedy memiliki keunggulan dibandingkan dengan algoritma Dijkstra yakni dalam hal menyelesaikan permasalahan kompleks yang memerlukan kecepatan jawaban, bukan solusi optimal. Maka dari itu, algoritma Dijkstra lah yang tepat untuk memperbaiki masalah optimasi. Selain itu, kedua algoritma memiliki kesamaan dalam hal menentukan jarak terpendek

Sumber referensi :

https://mti.binus.ac.id/2017/11/28/algoritma-dijkstra/

https://bertzzie.com/knowledge/analisis-algoritma/Greedy.html

https://wirasetiawan.blog/2015/04/02/tentang-algoritma-dijkstra/

https://tugasanalgo4blog.wordpress.com/2016/12/04/algoritma-greedy/

http://kurniadi-addi.blogspot.com/2015/07/materi-analisis-algortima-algoritma.html