Τι είναι οι Ευρετικές Αναζητήσεις;

Οι ευρετικές αναζητήσεις είναι αλγόριθμοι που χρησιμοποιούνται για να βρουν λύσεις σε προβλήματα, εκμεταλλευόμενοι κάποιες “έξυπνες” ή “ευρετικές” προσεγγίσεις. Αντί να ελέγχουν όλες τις πιθανές λύσεις, οι ευρετικοί αλγόριθμοι προσπαθούν να εστιάσουν στις πιο υποσχόμενες περιοχές του χώρου αναζήτησης.

Κύριες Ιδιότητες

  1. Εκτίμηση Κόστους: Χρησιμοποιούν μια ευρετική συνάρτηση για να εκτιμήσουν το κόστος του να φτάσουν σε μια λύση.
  2. Αποδοτικότητα: Συνήθως είναι πιο γρήγοροι από άλλες μεθόδους αναζήτησης, αλλά δεν εγγυώνται πάντα ότι θα βρουν την καλύτερη λύση.
  3. Εφαρμογές: Χρησιμοποιούνται σε προβλήματα όπως ο σχεδιασμός διαδρομών, η τεχνητή νοημοσύνη, και οι στρατηγικές παιχνιδιών.

Κλασικά Παραδείγματα Ευρετικής Αναζήτησης

  1. Αλγόριθμος A*: Ένας από τους πιο γνωστούς ευρετικούς αλγορίθμους, που χρησιμοποιείται για την εύρεση της συντομότερης διαδρομής σε ένα γράφο.
  2. Αλγόριθμος Γενετικής: Χρησιμοποιεί ευρετικές μεθόδους για να βρει καλές λύσεις σε προβλήματα βελτιστοποίησης.

Ψευδογλώσσα

Ας δούμε την ψευδογλώσσα για έναν απλό ευρετικό αλγόριθμο, όπως ο A*.

Ψευδογλώσσα Αλγορίθμου A*

Διαδικασία A*(αρχή, στόχος)
    Άνοιξη <- λίστα που περιέχει μόνο τον κόμβο αρχής
    Κλειστή <- κενή λίστα

    Όσο Άνοιξη δεν είναι κενή κάνε
        τρέχων <- ο κόμβος με την ελάχιστη εκτίμηση κόστους στην Άνοιξη
        Αν τρέχων είναι στόχος τότε
            Επιστροφή ανακατασκευή_διαδρομής(τρέχων)
        Τέλος_αν

        Αφαίρεσε τρέχων από Άνοιξη
        Πρόσθεσε τρέχων στην Κλειστή

        Για κάθε γειτονικό κόμβο ν κάνε
            Αν ν δεν είναι στην Κλειστή τότε
                υπολογισμός_κόστους(ν, τρέχων)
                Αν ν δεν είναι στην Άνοιξη τότε
                    Πρόσθεσε ν στην Άνοιξη
                Τέλος_αν
            Τέλος_αν
        Τέλος_Για
    Τέλος_Όσο

    Επιστροφή "Δεν βρέθηκε διαδρομή"
Τέλος_Διαδικασίας

Διαδικασία A*(αρχή, στόχος)
Άνοιξη <- λίστα που περιέχει μόνο τον κόμβο αρχής
Κλειστή <- κενή λίστα

Όσο Άνοιξη δεν είναι κενή κάνε
τρέχων <- ο κόμβος με την ελάχιστη εκτίμηση κόστους στην Άνοιξη
Αν τρέχων είναι στόχος τότε
Επιστροφή ανακατασκευή_διαδρομής(τρέχων)
Τέλος_αν

Αφαίρεσε τρέχων από Άνοιξη
Πρόσθεσε τρέχων στην Κλειστή

Για κάθε γειτονικό κόμβο ν κάνε
Αν ν δεν είναι στην Κλειστή τότε
υπολογισμός_κόστους(ν, τρέχων)
Αν ν δεν είναι στην Άνοιξη τότε
Πρόσθεσε ν στην Άνοιξη
Τέλος_αν
Τέλος_αν
Τέλος_Για
Τέλος_Όσο

Επιστροφή “Δεν βρέθηκε διαδρομή”
Τέλος_Διαδικασίας



Επεξήγηση του Κώδικα για την υλοποίηση σε c#:

  1. Δομή Κόμβου: Δημιουργούμε μια κλάση Node που περιέχει πληροφορίες για το όνομα, τους γειτονικούς κόμβους, το κόστος, την ευρετική και τον γονέα.
  2. Λειτουργία AStarSearch: Εκτελεί τον αλγόριθμο A* για να βρει τη διαδρομή από τον αρχικό κόμβο στον στόχο.
  3. Ανακατασκευή Διαδρομής: Μετά την εύρεση του στόχου, ανακατασκευάζουμε τη διαδρομή με τη χρήση του γονέα.

Συμπέρασμα

Οι ευρετικές αναζητήσεις είναι μια ισχυρή μέθοδος για την εύρεση λύσεων σε πολύπλοκα προβλήματα, προσφέροντας αποτελεσματικότητα και ταχύτητα. Ο αλγόριθμος A* είναι ένα εξαιρετικό παράδειγμα της εφαρμογής αυτών των τεχνικών.

Υλοποίηση σε C#

Ακολουθεί η υλοποίηση του αλγορίθμου A* σε C#:

using System;
using System.Collections.Generic;

class Node
{
    public string Name;
    public List<Node> Neighbors;
    public int Cost;
    public int Heuristic;
    public Node Parent;

    public Node(string name)
    {
        Name = name;
        Neighbors = new List<Node>();
        Cost = 0;
        Heuristic = 0;
        Parent = null;
    }

    public int TotalCost => Cost + Heuristic;
}

class Program
{
    static void Main()
    {
        Node start = new Node("A");
        Node goal = new Node("D");

        // Δημιουργία γειτονιών
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        
        start.Neighbors.Add(B);
        start.Neighbors.Add(C);
        B.Neighbors.Add(D);

        // Ορισμός κόστους και ευρετικών τιμών
        start.Heuristic = 2; // απόσταση A-D
        B.Heuristic = 1; // απόσταση B-D
        C.Heuristic = 3; // απόσταση C-D
        D.Heuristic = 0; // απόσταση D-D

        List<Node> path = AStarSearch(start, goal);
        if (path != null)
        {
            Console.WriteLine("Διαδρομή:");
            foreach (var node in path)
            {
                Console.Write(node.Name + " ");
            }
        }
        else
        {
            Console.WriteLine("Δεν βρέθηκε διαδρομή.");
        }
    }

    static List<Node> AStarSearch(Node start, Node goal)
    {
        List<Node> openSet = new List<Node> { start };
        HashSet<Node> closedSet = new HashSet<Node>();

        while (openSet.Count > 0)
        {
            Node current = openSet[0];

            // Εύρεση κόμβου με την ελάχιστη συνολική εκτίμηση κόστους
            foreach (var node in openSet)
            {
                if (node.TotalCost < current.TotalCost)
                {
                    current = node;
                }
            }

            if (current == goal)
            {
                return ReconstructPath(current);
            }

            openSet.Remove(current);
            closedSet.Add(current);

            foreach (var neighbor in current.Neighbors)
            {
                if (closedSet.Contains(neighbor)) continue;

                int newCost = current.Cost + 1; // απλό κόστος γειτονιάς

                if (!openSet.Contains(neighbor))
                {
                    openSet.Add(neighbor);
                }
                else if (newCost >= neighbor.Cost)
                {
                    continue;
                }

                neighbor.Cost = newCost;
                neighbor.Parent = current;
            }
        }

        return null;
    }

    static List<Node> ReconstructPath(Node node)
    {
        List<Node> path = new List<Node>();
        while (node != null)
        {
            path.Add(node);
            node = node.Parent;
        }
        path.Reverse();
        return path;
    }
}