Algoritmi i kërkimit të bazuar në gjendje (State-Based Search) në Java

Algoritmi i Kërkimit të Bazuar në Shtet është një metodë kërkimi në Java programim që përfshin krijimin dhe kalimin e gjendjeve të mundshme të një problemi. Në këtë algoritëm, të gjitha gjendjet e mundshme të një problemi përfaqësohen si nyje në një grafik ose hapësirë ​​​​gjendjeje.

Si funksionon algoritmi i kërkimit të bazuar në gjendje

Algoritmi fillon nga një gjendje fillestare dhe përdor transformimet për të gjeneruar gjendje fëmijësh. Çdo gjendje e krijuar rishtazi bëhet një nyje në hapësirën e grafikut ose gjendjes. Algoritmi përshkon këto gjendje, duke kontrolluar nëse gjendja e qëllimit është midis tyre. Nëse gjendet, algoritmi përfundon; përndryshe, ai vazhdon të përshkojë nëpër shtete të tjera fëmijë.

Avantazhet dhe disavantazhet e Algoritmit të Kërkimit të Bazuar në Shtet

Përparësitë:

• Shterues: Algoritmi ka aftësinë të mbulojë të gjitha gjendjet e mundshme të problemit.
• I gjithanshëm: Mund të aplikohet për lloje të ndryshme problemesh.

Disavantazhet:

• Mundësia e përsëritjes: Në disa raste, algoritmi mund të përsërisë kalimin e gjendjeve të caktuara.

Shembull dhe Shpjegim

Një shembull ilustrues i Algoritmit të Kërkimit të Bazuar në Shtet është gjetja e një shtegu nga një pikënisje në një destinacion në një hartë. Le të shohim se si funksionon ky algoritëm:

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);  
                }  
            }  
        }  
    }  
}  

Në shembullin e mësipërm, ne përdorim Algoritmin e Kërkimit të Bazuar në Gjendje për të gjetur një shteg nga një gjendje fillestare në një gjendje të qëllimit në një hartë. Gjendjet e fëmijëve krijohen duke kryer veprime të mundshme nga gjendja aktuale. Rezultati është se algoritmi do të gjejë një rrugë nga gjendja fillestare në gjendjen e qëllimit.