மாநில அடிப்படையிலான தேடல் (State-Based Search) அல்காரிதம் Java

மாநில-அடிப்படையிலான தேடல் அல்காரிதம் என்பது நிரலாக்கத்தில் ஒரு தேடல் முறையாகும், Java இது ஒரு சிக்கலின் சாத்தியமான நிலைகளை உருவாக்குதல் மற்றும் கடந்து செல்வதை உள்ளடக்கியது. இந்த அல்காரிதத்தில், ஒரு சிக்கலின் சாத்தியமான அனைத்து நிலைகளும் ஒரு வரைபடம் அல்லது மாநில இடைவெளியில் முனைகளாகக் குறிப்பிடப்படுகின்றன.

மாநில அடிப்படையிலான தேடல் அல்காரிதம் எவ்வாறு செயல்படுகிறது

அல்காரிதம் ஆரம்ப நிலையில் இருந்து தொடங்குகிறது மற்றும் குழந்தை நிலைகளை உருவாக்க உருமாற்றங்களைப் பயன்படுத்துகிறது. புதிதாக உருவாக்கப்பட்ட ஒவ்வொரு நிலையும் வரைபடம் அல்லது மாநில இடத்தில் ஒரு முனையாக மாறும். அல்காரிதம் இந்த நிலைகள் வழியாகச் சென்று, இலக்கு நிலை அவற்றில் உள்ளதா எனச் சரிபார்க்கிறது. கண்டுபிடிக்கப்பட்டால், அல்காரிதம் முடிவடைகிறது; இல்லையெனில், அது மற்ற குழந்தை மாநிலங்களில் தொடர்ந்து பயணிக்கிறது.

மாநில அடிப்படையிலான தேடல் அல்காரிதத்தின் நன்மைகள் மற்றும் தீமைகள்

நன்மைகள்:

• முழுமையானது: அல்காரிதம் சிக்கலின் அனைத்து சாத்தியமான நிலைகளையும் உள்ளடக்கும் திறனைக் கொண்டுள்ளது.
• பல்துறை: இது பல்வேறு வகையான சிக்கல்களுக்குப் பயன்படுத்தப்படலாம்.

தீமைகள்:

• மீண்டும் நிகழும் சாத்தியம்: சில சந்தர்ப்பங்களில், அல்காரிதம் சில நிலைகளின் பயணத்தை மீண்டும் செய்யக்கூடும்.

எடுத்துக்காட்டு மற்றும் விளக்கம்

மாநில-அடிப்படையிலான தேடல் அல்காரிதத்தின் ஒரு எடுத்துக்காட்டு உதாரணம், ஒரு வரைபடத்தில் ஒரு தொடக்கப் புள்ளியில் இருந்து இலக்குக்கான பாதையைக் கண்டறிவது. இந்த அல்காரிதம் எவ்வாறு செயல்படுகிறது என்பதைப் பார்ப்போம்:

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

மேலே உள்ள எடுத்துக்காட்டில், வரைபடத்தில் ஆரம்ப நிலையிலிருந்து இலக்கு நிலைக்கு ஒரு பாதையைக் கண்டறிய மாநில அடிப்படையிலான தேடல் அல்காரிதத்தைப் பயன்படுத்துகிறோம். தற்போதைய நிலையில் இருந்து சாத்தியமான செயல்களைச் செய்வதன் மூலம் குழந்தை நிலைகள் உருவாக்கப்படுகின்றன. இதன் விளைவாக, அல்காரிதம் தொடக்க நிலையிலிருந்து இலக்கு நிலைக்கு ஒரு பாதையைக் கண்டுபிடிக்கும்.