Optimasi Penelusuran Bipartite Graph Tanaman-Protein untuk Memprediksi Formula Jamu dengan Algoritme Branch and Bound

Abstract

Jamu adalah ramuan herbal asal Indonesia yang telah digunakan selama bertahun-tahun. Jamu terbuat dari komposisi berbagai macam tanaman obat, seperti akar, daun, dan batang. Penyakit yang dipercaya dapat diatasi oleh jamu sangat beragam, salah satunya adalah penyakit Diabetes mellitus. Penelitian terkait prediksi formula jamu untuk penyakit Diabetes mellitus tipe 2 sudah pernah dilakukan, namun terkendala dalam pencarian kombinasi formula jamu karena memiliki waktu komputasi yang tinggi. Penelitian ini bertujuan melakukan prediksi kombinasi formula jamu dengan mengoptimasi penelusuran pada bipartite graph tanaman-protein menggunakan algoritme branch and bound. Data yang digunakan pada penelitian ini adalah data protein yang berasosiasi dengan penyakit Diabetes mellitus tipe 2 dan data tanaman yang menarget protein tersebut. Penelusuran bipartite graph dengan algoritme branch and bound mereduksi waktu komputasi sampai 40 kali lebih cepat dibandingkan dengan strategi complete search pada penelitian sebelumnya untuk pencarian kombinasi 4 tanaman. Strategi pencarian breadth first search menjadi opsi terbaik pada penelitian ini.