اگر ما الگوریتم depth limited search رو با عمق های متفاوت از کم به زیاد اجرا کنیم بهش IDDFS میگن .
یعنی ما در این الگوریتم از عمق 1 تا حداکثر عمق که m باشه الگوریتم depth limited search رو صدا میزنیم .
مزیتی که این الگوریتم نسبت به DLS داره اینه که هم complete هست یعنی در صورت وجود جواب حتما جواب پیدا میشه و هم در صورت برابر بودن فاصله راس ها optimal هستش (یعنی بهترین جواب ممکن برگشت داده میشه )
مرتبه زمانی این الگوریتم b^d هست که d عمق نزدیکترین جواب هستش و b هم یال های در هر سطح (branching factor ) میزان حافظه مصرفی هم از مرتبه bd هستش
کد این الگوریتم با کد DLS که داخل لینک قبلی گذاشتم زیاد تفاوتی نداره :
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <deque>
#include <set>
using Node = char;
using NodeList = std::deque<Node>;
using Edge = std::pair<Node, Node>;
class Graph
{
public:
//return list of connected nodes
NodeList operator[](const Node& node) const
{
auto loc = data_.find(node);
if (loc != data_.end()){
return loc->second;
}
return NodeList();
}
void addEdge(const Edge& edge)
{
auto item = data_.find(edge.first);
if (item != data_.end()){
item->second.push_back(edge.second);
}
else{
data_[edge.first] = NodeList{ edge.second };
}
}
void addEdge(Node first, Node second)
{
addEdge(Edge(first, second));
}
bool empty()const { return data_.empty(); }
Node first()const { return data_.begin()->first; }
private:
std::map<Node, NodeList> data_;
};
NodeList DLS(const Graph& graph, const Node& goal, int max_depth);
NodeList IDDFS(const Graph& graph, const Node& goal,int graphDepth)
{
for (int i = 0; i < graphDepth; ++i){
NodeList nodeList = DLS(graph, goal, i);
if (nodeList.size()>0)
return nodeList;
}
return NodeList();
}
int main()
{
//test
Node A = 'A', B = 'B', C = 'C', D = 'D'
, E = 'E', F = 'F', G = 'G',H = 'H', I = 'I';
Graph graph;
graph.addEdge(A, B);
graph.addEdge(A, C);
graph.addEdge(B, D);
graph.addEdge(B, E);
graph.addEdge(C, E);
graph.addEdge(E, F);
graph.addEdge(F, G);
graph.addEdge(F, H);
graph.addEdge(H, I);
NodeList result = IDDFS(graph, I, 7);//result : ACEFHI
for (auto node : result){
std::cout << node;
}
}
NodeList DLS(const Graph& graph, const Node& goal, int max_depth)
{
if (graph.empty())
return NodeList();
std::deque<NodeList> frontier(1);
std::set<Node> explored;
frontier[0].push_back(graph.first());
explored.insert(graph.first());
while (!frontier.empty())
{
NodeList frontNodes = frontier[0];
Node currentNode = frontNodes.back();
if (currentNode == goal)
return frontier[0];
frontier.pop_front();
//find connected nodes
NodeList connectedNodes = graph[currentNode];
//agar if zir ro bardarim algorithm be dfs tabdile mishe
if (connectedNodes.size() >= max_depth){
continue;
}
//expand frontier
for (const auto& connectedNode : connectedNodes){
//check if explored before
if (explored.find(connectedNode) == explored.end()){
NodeList temp = (frontNodes);
temp.push_back(connectedNode);
frontier.push_front(temp);
explored.insert(connectedNode);
}
}
}
return NodeList();
}