/Tucil3_13522070

Primary LanguageJavaMIT LicenseMIT


Tugas Kecil 3 IF2211 Strategi Algoritma Tahun Ajaran 2023/2024

Penyelesaian Permainan Word Ladder Menggunakan Algoritma UCS, Greedy Best-First Search, dan A*

Program made using Java Language


Report Bug · Request Feature

MIT License

Dibuat oleh :

NIM Nama
Marzuli Suhada M 13522070

Deskripsi Program

Word ladder adalah permainan kata yang terkenal dimainkan oleh banyak orang. Ditemukan oleh Lewis Carroll pada tahun 1877, permainan ini melibatkan dua kata, yaitu start word dan end word. Pemain harus menemukan rantai kata yang menghubungkan kedua kata tersebut, di mana setiap kata dalam rantai hanya boleh berbeda satu huruf dari kata sebelumnya. Solusi optimal adalah solusi dengan jumlah kata yang dimasukkan ke rantai paling sedikit.

Program berikut digunakan untuk mencari solusi dari permainan seperti website Word Ladder namun perbedaannya program berikut akan menyajikan 3 algoritma pilihan dalam route planning yaitu UCS, Greedy Best-First Search dan A*. Program ini dibuat dalam bahasa java.

Dokumentasi lengkap tentang program dapat dilihat pada link berikut

About Algorithm

Uniform Cost Search (UCS)

UCS adalah algoritma pencarian yang menemukan jalur dengan biaya terendah dari titik awal ke tujuan. Dalam konteks Word Ladder, UCS mencari jalur terpendek dengan menghitung biaya setiap transformasi kata. Algoritma ini menggunakan antrian prioritas dan mengunjungi simpul dengan biaya terendah terlebih dahulu, memastikan setiap langkah perubahan kata memiliki biaya yang sama.

Greedy Best-First Search (GBFS)

GBFS adalah algoritma pencarian yang memprioritaskan simpul berdasarkan estimasi heuristik menuju tujuan. Dalam aplikasi Word Ladder, heuristik biasanya adalah jumlah huruf yang berbeda antara kata saat ini dan kata tujuan. Algoritma ini memilih simpul yang tampaknya paling dekat dengan tujuan, tanpa mempertimbangkan biaya perjalanan yang sebenarnya.

A*

A* adalah algoritma pencarian yang menggabungkan pendekatan UCS dan GBFS. Algoritma ini menghitung biaya total (f(n)) dengan menambahkan biaya dari titik awal ke simpul saat ini (g(n)) dan estimasi heuristik menuju tujuan (h(n)). Dalam kasus Word Ladder, A* memberikan jalur terpendek dengan mempertimbangkan jarak dan estimasi menuju tujuan, membuatnya lebih efisien daripada UCS atau GBFS dalam menemukan solusi optimal.

Spesifikasi Program

Tucil3_13522070
 │ 
 ├── bin    
 ├── doc    
 │    └─ Tucil3_13522070.pdf 
 ├── img 
 ├── src    
 │    └─ wordladder
 │       ├─ dictionary
 │       ├─ image
 │       ├─ jafafx-sdk-22.0.1
 │       ├─ AStar.java
 │       ├─ Dictionary.java
 │       ├─ GBFS.java
 │       ├─ GUI.java
 │       ├─ GUI2.java
 │       ├─ Main.java
 │       ├─ Node.java
 │       ├─ Result.java
 │       ├─ UCS.java
 │       ├─ Utility.java
 │       └─ WordDictionary.java
 ├── test    
 └── README.md

Requirements

To run this program, you need to have:

  1. The latest Java version Java
  2. JavaFX compatible with your operating system JavaFX

Setup and Compilation

GUI : JavaFX

To install the program with a GUI, ensure JavaFX is installed on your system. If not, you need to install JavaFX. For reference, you can use this YouTube tutorial. Follow these steps:

  1. Clone this repository:
git clone https://github.com/zultopia/Tucil3_13522070.git
  1. Navigate to the directory of the program:
cd src/wordladder

  1. Compile the program

    For Windows

    javac --module-path "<path_to_javafx_sdk for example C:\Java\javafx-sdk-22.0.1>/lib" --add-modules javafx.controls,javafx.fxml,javafx.graphics AStar.java GBFS.java UCS.java WordDictionary.java Node.java Utility.java Result.java GUI.java

    For Linux/MacOS

    java --module-path "<path_to_javafx_sdk for example /Users/azulsuhada/Downloads/javafx-sdk-22.0.1>/lib" --add-modules javafx.controls,javafx.fxml,javafx.graphics GUI

  2. Run the program

    For Windows

    javac --module-path "<path_to_javafx_sdk for example C:\Java\javafx-sdk-22.0.1>/lib" --add-modules javafx.controls,javafx.fxml,javafx.graphics AStar.java GBFS.java UCS.java WordDictionary.java Node.java Utility.java Result.java GUI.java

    For Linux/MacOS

    java --module-path "<path_to_javafx_sdk for example /Users/azulsuhada/Downloads/javafx-sdk-22.0.1>/lib" --add-modules javafx.controls,javafx.fxml,javafx.graphics GUI

GUI : Java Swing

If JavaFX still not running. Use this alternatif GUI

  1. Clone this repository:
git clone https://github.com/zultopia/Tucil3_13522070.git
  1. Navigate to the directory of the program:
cd src/wordladder
  1. Compile the program
javac AStar.java GBFS.java UCS.java WordDictionary.java Node.java Utility.java Result.java GUI2.java
  1. Run the program
java GUI2

CLI

To run the program with a CLI, follow these steps.

  1. Clone this repository
 git clone https://github.com/zultopia/Tucil3_13522070.git
  1. Run program
java -cp bin Main
  1. If there is problem, navigate to the src/wordladder directory
cd ./Tucil3_13522070/src/wordladder
  1. Compile and run the program
javac AStar.java GBFS.java UCS.java WordDictionary.java Node.java Utility.java Result.java Main.java
java Main

Screenshots

Graphical User Interface (GUI) Tampak Atas

GUI Screenshot

Graphical User Interface (GUI) Tampak Bawah

GUI Screenshot

Licensing

The code in this project is licensed under MIT license.


THANK YOU!