Tugas Besar Strategi Algoritma 2

Pemanfaatan Algoritma IDS dan BFS dalam Permainan WikiRace

Kelompok GoPedia:

No.	Nama	NIM
1.	Rafiki Prawhira Harianto	13522065
2.	Bagas Sambega Rosyada	13522071
3.	Abdullah Mubarak	13522101

Daftar Isi

1. Deskripsi Program
2. Implementasi Algoritma
3. Cara Penggunaan Program

Deskripsi Program

Program ini adalah program untuk menyelesaikan permainan Wikirace menggunakan algoritma IDS dan BFS. Permainan Wikirace adalah permainan untuk mencari jalur terpendek dari satu artikel Wikipedia ke artikel lainnya. Program ini akan mencari jalur terpendek dari artikel awal ke artikel tujuan dengan melakukan scraping pada artikel-artikel yang dikunjungi, dan mengunjungi artikel-artikel tersebut untuk mencari artikel tujuan. Program akan menghasilkan jalur terpendek dari artikel awal ke artikel tujuan pada laman Wikipedia. Laman artikel Wikipedia yang digunakan terbatas pada bahasa Inggris dan tidak menggunakan laman khusus seperti: "/File:", "/Special:", "/Template:", "/Template_page:", "/Help:", "/Category:", "Special:", "/Wikipedia:", "/Portal:", "/Talk:".

Repository ini adalah bagian backend dari program yang berisi script dalam bahasa Go untuk menjalankan fungsi pemrosesan permainan Wikirace dan mengirimkan datanya melalui API ke frontend yang dibuat menggunakan framework ReactJS. Kedua repository perlu dijalankan bersamaan untuk menjalankan program Wikirace. Link kedua repository:

1. Backend
2. Frontend

Implementasi Algoritma

Program ini menggunakan dua algoritma untuk menyelesaikan permainan Wikirace, yaitu:

1. Algoritma IDS (Iterative Deepening Search): Algoritma ini adalah algoritma search yang melakukan depth-first search dengan level depth yang bertambah secara iteratif. Implementasi algoritma ini terdapat pada file src/IDS.go, yang berisi fungsi utama IDS yang akan melakukan pemanggilan fungsi DLS/Depth Limited Search sampai dengan level tertentu. Pencarian akan dilakukan ke simpul tetangga terlebih dahulu. Jika pada level tersebut tidak ditemukan solusi, maka level kedalaman akan ditingkatkan dan fungsi DLS akan dipanggil kembali dengan level kedalaman yang baru.
2. Algoritma BFS (Breadth-First Search): Algoritma ini adalah algoritma search yang melakukan pencarian pada satu level terlebih dahulu secara keseluruhan sebelum mencari di level kedalaman berikutnya. Implementasi algoritma ini terdapat pada file src/BFS.go, yang berisi fungsi utama BFS yang akan melakukan pencarian dengan melakukan scraping dan menyimpan seluruh tautan pada suatu level ke dalam queue, dan mengunjungi setiap artikel pada queue tersebut untuk mencari artikel tujuan. Jika tidak ditemukan artikel tujuan pada level tersebut, fungsi akan melakukan scraping pada level kedalaman selanjutnya dan mengunjunginya secara keseluruhan secara melebar.

Cara Penggunaan Program

Program memerlukan frontend untuk menjalankan program Wikirace. Langkah instalasi terdapat pada repository frontend tersebut.

Requirement

1. Go terinstal di perangkat
2. Framework Gin dan Gocolly
3. Docker dan Docker Desktop

Instalasi

1. Clone repository ini

git clone https://github.com/bagassambega/Tubes2_BE_GoPedia.git

2. Masuk ke direktori repository yang telah di-clone dan ke folder src

cd Tubes2_BE_GoPedia/src

3. Jalankan command berikut untuk memastikan seluruh dependency terinstal

go mod tidy

4. Jalankan Docker Desktop atau Docker, lalu build docker image dari Dockerfile yang telah disediakan

docker build -t gopedia-backend .

5. Jalankan docker container dari docker image yang telah dibuat

docker run -p 8080:8080 gopedia-backend

6. Untuk menghentikan program, jalankan command berikut. Lihat container_id dengan menjalankan command docker ps atau pada Docker Desktop

docker stop [container_id]

Setelah program backend berjalan dan langkah-langkah menjalankan frontend selesai, program dapat diakses pada browser dengan membuka alamat http://localhost:5173/ dan pengguna dapat memasukkan artikel awal dan artikel tujuan untuk mencari jalur terpendek dari artikel awal ke artikel tujuan.

NOTE: Setelah langkah-langkah di atas dilakukan, bagian backend Wikirace akan berjalan pada port 8080. Data sudah dapat diakses melalui browser dengan membuka alamat http://localhost:8080/gopedia/?method=[metode]&source=[awal]&target=[akhir], dengan mengganti [metode] menjadi IDS/BFS, [awal] menjadi artikel awal, dan [akhir] menjadi artikel tujuan. Contoh: http://localhost:8080/gopedia/?method=IDS&source=Indonesia&target=Joko_Widodo. Jika bagian frontend tidak berjalan dengan baik, data dapat diakses langsung dengan langkah di atas.

NOTE: Jika build docker gagal atau menjalankan dengan docker tidak berhasil, program dapat dijalankan dengan menjalankan command berikut pada folder src:

go run .

NOTE: Kendala saat ini baik pada BFS dan IDS adalah terdapat maksimum requests per second yang dibatasi oleh Wikipedia. Untuk terus memantau apakah program berjalan atau sudah diblokir oleh Wikipedia, lihat log pada terminal backend. Untuk melakukan pengaturan terhadap banyak thread yang digunaka, untuk algoritma BFS terdapat pada variabel limiter dengan nilai awal 200 di file BFS.go pada fungsi BFS, dan pada algoritma IDS terdapat pada variabel limiter dengan nilai awal 100 pada file IDS.go pada fungsi DLS. Nilai ini dapat diubah sesuai kebutuhan.