Algoritma Carian Heuristik dalam Java

Algoritma Heuristic Search ialah kaedah carian pintar dalam Java pengaturcaraan yang bergantung pada penggunaan maklumat anggaran(pengetahuan) untuk membimbing proses carian. Heuristics ialah kaedah anggaran penyelesaian masalah berdasarkan pengetahuan yang tidak sempurna dan maklumat anggaran tentang keadaan semasa masalah.

Cara Algoritma Carian Heuristik Berfungsi

Algoritma Carian Heuristik menggunakan fungsi heuristik untuk menilai "kedekatan" keadaan dengan matlamat. Semasa setiap lelaran carian, algoritma memilih arah carian berdasarkan nilai heuristik keadaan berpotensi. Matlamatnya adalah untuk mengoptimumkan nilai heuristik, yang membawa kepada penyelesaian anggaran untuk masalah tersebut.

Kelebihan dan Kelemahan Algoritma Carian Heuristik

Kelebihan:

• Carian pintar: Algoritma menggunakan anggaran pengetahuan untuk membimbing carian, mengoptimumkan masa dan sumber.
• Kebolehgunaan luas: Heuristics boleh digunakan untuk pelbagai masalah pengoptimuman dan carian dalam senario dunia sebenar.

Kelemahan:

• Kemungkinan ketidaktepatan: Heuristics bergantung pada anggaran dan maklumat yang berpotensi tidak tepat, mengakibatkan penyelesaian yang tidak sempurna.

Contoh dan Penerangan

Contoh biasa bagi algoritma Carian Heuristik ialah algoritma A*, yang digunakan untuk mencari laluan terpendek pada peta. Mari lihat bagaimana algoritma ini berfungsi:

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  
            // ...  
        }  
    }  
}  

Dalam contoh di atas, kami menggunakan algoritma A* untuk mencari laluan terpendek pada peta. Nod jiran diterokai berdasarkan jumlah kos kepada nod semasa dan anggaran heuristik. Hasilnya ialah mencari laluan terpendek dari titik permulaan ke titik sasaran.