IDDFS
Kiejtés
- IPA: [ ˈitfʃ]
Főnév
IDDFS
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.
Általános IDDFS Pseudocode
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
Python Implementáció
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[u] = []
self.graph[u].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.")
C++ Implementáció
#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[u].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[node]) {
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;
}
Magyarázat
- IDDFS:
- Kezdő csúcsról indul.
- Egyre növekvő mélységhatárral hívja meg a
DLS-t (Depth-Limited Search).
- 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.
- 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.