Euristinės paieškos algoritmas Java

Euristinės paieškos algoritmas yra protingas paieškos metodas programuojant Java, kuris remiasi apskaičiuotos informacijos(žinių) naudojimu, kad būtų nukreiptas paieškos procesas. Heuristics yra apytikslis problemų sprendimo būdas, pagrįstas netobulomis žiniomis ir apskaičiuota informacija apie esamą problemos būklę.

Kaip veikia euristinės paieškos algoritmas

Euristinės paieškos algoritmas naudoja euristines funkcijas, kad įvertintų būsenos „artumą“ tikslui. Kiekvienos paieškos iteracijos metu algoritmas parenka paieškos kryptį pagal euristines potencialių būsenų reikšmes. Tikslas yra optimizuoti euristinę vertę, kad būtų apytikslis problemos sprendimas.

Euristinės paieškos algoritmo privalumai ir trūkumai

Privalumai:

• Pažangi paieška: algoritmas naudoja apskaičiuotas žinias paieškai vadovauti, optimizuodamas laiką ir išteklius.
• Platus pritaikymas: Heuristics gali būti taikomas įvairioms optimizavimo ir paieškos problemoms realaus pasaulio scenarijuose.

Trūkumai:

• Galimas netikslumas: Heuristics pasikliaukite įvertinimu ir galimai netikslia informacija, todėl sprendimai yra netobuli.

Pavyzdys ir paaiškinimas

Dažnas euristinės paieškos algoritmo pavyzdys yra A* algoritmas, naudojamas ieškant trumpiausio kelio žemėlapyje. Pažiūrėkime, kaip veikia šis algoritmas:

import java.util.*;  
  
class Node {  
    int x, y;  
    int cost, heuristic;  
  
    Node(int x, int y, int cost, int heuristic) {  
        this.x = x;  
        this.y = y;  
        this.cost = cost;  
        this.heuristic = heuristic;  
    }  
}  
  
public class HeuristicSearchExample {  
    static int heuristic(int x, int y, int targetX, int targetY) {  
        return Math.abs(targetX- x) + Math.abs(targetY- y);  
    }  
  
    static void heuristicSearch(int[][] grid, int startX, int startY, int targetX, int targetY) {  
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) ->(a.cost + a.heuristic)-(b.cost + b.heuristic));  
        pq.offer(new Node(startX, startY, 0, heuristic(startX, startY, targetX, targetY)));  
  
        while(!pq.isEmpty()) {  
            Node current = pq.poll();  
            int x = current.x;  
            int y = current.y;  
  
            if(x == targetX && y == targetY) {  
                System.out.println("Found target at(" + x + ", " + y + ")");  
                return;  
            }  
  
            // Explore neighboring nodes and add to the priority queue  
            // based on total cost and heuristic  
            // ...  
        }  
    }  
}  

Aukščiau pateiktame pavyzdyje mes naudojame A* algoritmą, kad surastume trumpiausią kelią žemėlapyje. Kaimyniniai mazgai tiriami remiantis bendromis dabartinio mazgo sąnaudomis ir euristiniu įvertinimu. Rezultatas- rasti trumpiausią kelią nuo pradžios taško iki tikslinio taško.