IDDFS

• IPA:

IDDFS

1. (matematika, algoritmusok)

Az Iterative Deepening Depth-First Search (IDDFS) egy hatékony keresési algoritmus, amely a mélységi keresést (DFS) iteratívan növekvő mélységhatárral kombinálja. Ez különösen hasznos nagy keresési terekben, ahol a megoldás mélysége nem ismert előre.

Itt a pseudocode, majd a Python és C++ implementációk.

function IDDFS(start, goal, max_depth):
    for depth from 0 to max_depth:
        result = DLS(start, goal, depth)
        if result is not None:
            return result
    return None

function DLS(node, goal, depth):
    if depth == 0:
        if node == goal:
            return node
        return None
    if depth > 0:
        for each child in neighbors(node):
            result = DLS(child, goal, depth - 1)
            if result is not None:
                return result
    return None

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        """Csúcsok közötti él hozzáadása"""
        if u not in self.graph:
            self.graph = 
        self.graph.append(v)

    def iddfs(self, start, goal, max_depth):
        """Iteratív mélységi keresés"""
        for depth in range(max_depth + 1):
            if self.dls(start, goal, depth):
                return True
        return False

    def dls(self, node, goal, depth):
        """Mélységi korlátozott keresés"""
        if depth == 0:
            return node == goal
        if depth > 0:
            for neighbor in self.graph.get(node, ):
                if self.dls(neighbor, goal, depth - 1):
                    return True
        return False


# Példa használatra
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 5)
g.add_edge(2, 6)

start = 0
goal = 6
max_depth = 3

if g.iddfs(start, goal, max_depth):
    print(f"Cél ({goal}) elérhető!")
else:
    print(f"Cél ({goal}) nem érhető el a {max_depth} mélységig.")

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Graph {
private:
    map<int, vector<int>> adj;

public:
    void addEdge(int u, int v) {
        adj.push_back(v);
    }

    bool IDDFS(int start, int goal, int maxDepth) {
        for (int depth = 0; depth <= maxDepth; ++depth) {
            if (DLS(start, goal, depth)) {
                return true;
            }
        }
        return false;
    }

private:
    bool DLS(int node, int goal, int depth) {
        if (depth == 0) {
            return node == goal;
        }
        if (depth > 0) {
            for (int neighbor : adj) {
                if (DLS(neighbor, goal, depth - 1)) {
                    return true;
                }
            }
        }
        return false;
    }
};

int main() {
    Graph g;
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(2, 6);

    int start = 0, goal = 6, maxDepth = 3;

    if (g.IDDFS(start, goal, maxDepth)) {
        cout << "Cél (" << goal << ") elérhető!" << endl;
    } else {
        cout << "Cél (" << goal << ") nem érhető el a " << maxDepth << " mélységig." << endl;
    }

    return 0;
}

1. IDDFS:
   • Kezdő csúcsról indul.
   • Egyre növekvő mélységhatárral hívja meg a DLS-t (Depth-Limited Search).
2. DLS (Depth-Limited Search):
   • Csak az aktuális mélységhatárig keres.
   • Rekurzív módon vizsgálja a gyerek csúcsokat, csökkentve a mélységhatárt.
3. Bonyolultság:
   • Idő: (O(b^d)), ahol (b) a szomszédok száma (ágazási tényező), (d) a megoldás mélysége.
   • Tárhely: (O(d)), mert a DFS csak a jelenlegi útpályát tárolja.

Ez az algoritmus különösen hasznos nagy gráfok és Rubik-kocka problémák esetén, ahol a mélységet nem ismerjük pontosan.

• IDDFS - Értelmező szótár (MEK)
• IDDFS - Etimológiai szótár (UMIL)
• IDDFS - Szótár.net (hu-hu)
• IDDFS - DeepL (hu-de)
• IDDFS - Яндекс (hu-ru)
• IDDFS - Google (hu-en)
• IDDFS - Helyesírási szótár (MTA)
• IDDFS - Wikidata
• IDDFS - Wikipédia (magyar)