Algoritma Carian Berasaskan Negeri (State-Based Search) dalam Java

Algoritma Carian Berasaskan Negeri ialah kaedah carian dalam Java pengaturcaraan yang melibatkan penciptaan dan penelusuran melalui kemungkinan keadaan masalah. Dalam algoritma ini, semua kemungkinan keadaan masalah diwakili sebagai nod dalam graf atau ruang keadaan.

Cara Algoritma Carian Berasaskan Negeri Berfungsi

Algoritma bermula dari keadaan awal dan menggunakan transformasi untuk menjana keadaan anak. Setiap keadaan yang baru dijana menjadi nod dalam graf atau ruang keadaan. Algoritma merentasi keadaan ini, memeriksa sama ada keadaan matlamat adalah di antara mereka. Jika dijumpai, algoritma ditamatkan; jika tidak, ia terus melintasi negeri kanak-kanak lain.

Kelebihan dan Kelemahan Algoritma Carian Berasaskan Negeri

Kelebihan:

• Exhaustive: Algoritma mempunyai keupayaan untuk merangkumi semua kemungkinan keadaan masalah.
• Serbaguna: Ia boleh digunakan untuk pelbagai jenis masalah.

Kelemahan:

• Kemungkinan pengulangan: Dalam sesetengah kes, algoritma mungkin mengulangi traversal keadaan tertentu.

Contoh dan Penerangan

Contoh ilustrasi bagi Algoritma Carian Berasaskan Negeri ialah mencari laluan dari titik permulaan ke destinasi pada peta. Mari lihat bagaimana algoritma ini berfungsi:

import java.util.*;  
  
public class StateSearchExample {  
    static boolean isGoalState(State state, State goalState) {  
        return state.equals(goalState);  
    }  
  
    static void stateSearch(State initialState, State goalState) {  
        Queue<State> queue = new LinkedList<>();  
        Set<State> visited = new HashSet<>();  
  
        queue.add(initialState);  
        visited.add(initialState);  
  
        while(!queue.isEmpty()) {  
            State currentState = queue.poll();  
  
            if(isGoalState(currentState, goalState)) {  
                System.out.println("Found goal state: " + currentState);  
                return;  
            }  
  
            List<State> nextStates = currentState.generateNextStates();  
            for(State nextState: nextStates) {  
                if(!visited.contains(nextState)) {  
                    queue.add(nextState);  
                    visited.add(nextState);  
                }  
            }  
        }  
    }  
}  

Dalam contoh di atas, kami menggunakan Algoritma Carian Berasaskan Negeri untuk mencari laluan daripada keadaan awal kepada keadaan matlamat pada peta. Keadaan kanak-kanak dijana dengan melakukan tindakan yang mungkin daripada keadaan semasa. Hasilnya ialah algoritma akan mencari laluan dari keadaan permulaan ke keadaan matlamat.