Tilaperusteinen hakualgoritmi (State-Based Search) sisään Java

Tilaperusteinen hakualgoritmi on ohjelmoinnin hakumenetelmä Java, joka sisältää ongelman mahdollisten tilojen luomisen ja läpikäymisen. Tässä algoritmissa ongelman kaikki mahdolliset tilat esitetään solmuina graafissa tai tila-avaruudessa.

Miten tilaperusteinen hakualgoritmi toimii

Algoritmi alkaa alkutilasta ja käyttää muunnoksia lapsitilojen luomiseen. Jokaisesta vasta generoidusta tilasta tulee solmu graafissa tai tilaavaruudessa. Algoritmi kulkee näiden tilojen läpi ja tarkistaa, onko tavoitetila niiden joukossa. Jos löydetään, algoritmi päättyy; muuten se jatkaa kulkemistaan ​​muiden lapsitilojen läpi.

Tilaperusteisen hakualgoritmin edut ja haitat

Edut:

• Kattava: Algoritmi pystyy kattamaan kaikki mahdolliset ongelman tilat.
• Monipuolinen: Sitä voidaan soveltaa erilaisiin ongelmiin.

Haitat:

• Toistomahdollisuus: Joissakin tapauksissa algoritmi saattaa toistaa tiettyjen tilojen läpikäynnin.

Esimerkki ja selitys

Kuvaava esimerkki tilaperusteisesta hakualgoritmista on polun etsiminen lähtöpisteestä määränpäähän kartalta. Katsotaan kuinka tämä algoritmi toimii:

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

Yllä olevassa esimerkissä käytämme tilaperusteista hakualgoritmia löytääksemme polun alkutilasta tavoitetilaan kartalta. Lapsitilat luodaan suorittamalla toimintoja, jotka ovat mahdollisia nykyisestä tilasta. Tuloksena on, että algoritmi löytää polun aloitustilasta tavoitetilaan.