Penerapan Algoritma Bracktracking Dalam Penyelesaian Masalah Sistem Pakar

Abstract

Penelitian ini berfokus pada penerapan algoritma backtracking sebagai metode penyelesaian berbagai permasalahan kompleks di bidang komputasi, permainan, dan diagnosis sistem pakar. Algoritma backtracking digunakan untuk memecahkan masalah seperti permainan teka-teki (Minesweeper, N-Queen Problem, Math Maze, Knight Tour, Nonogram, dan Sudoku), sistem checkpoint pada permainan edukatif, serta optimalisasi diagnosis penyakit. Berbagai pendekatan diperbandingkan, termasuk brute force dan soft computing, menunjukkan bahwa backtracking memiliki keunggulan signifikan dalam efisiensi waktu dan akurasi solusi.

Dalam permainan Minesweeper, backtracking berhasil memangkas ruang pencarian dengan kompleksitas O(2ⁿ.n), dibandingkan brute force dengan O(n.n!/(n-d)!). Pada N-Queen Problem, algoritma ini menghasilkan solusi optimal untuk papan berukuran kecil. Penyelesaian permainan Knight Tour menunjukkan efisiensi pada papan menengah, sementara Sudoku dan Nonogram menghasilkan akurasi 100% dengan perbandingan kecepatan terhadap metode lain. Di bidang sistem pakar diagnosis, penerapan backtracking pada metode backward chaining meningkatkan efisiensi sebesar 88%.

Hasil penelitian menunjukkan bahwa algoritma backtracking efektif dan akurat dalam memecahkan permasalahan kombinatorik dan sistem kompleks. Namun, efisiensi algoritma berkurang pada skala besar, sehingga diperlukan optimasi lebih lanjut untuk menangani permasalahan dengan kompleksitas tinggi.