اگر در جست و جوی DFS عمقی که جلو میریم رو محدود کنیم بهش DLS میگن
همون طوری که اطلاع دارید DFS از مرتبه b^m هست که b تعداد بیشترین شاخه ها در سطوح مختلف هست (branching factor ) و m هم بیشترین عمق گراف . حالا اگر این b,d خیلی بزرگ باشن چون مرتبه توانی هست هیچ وقت در زمان مناسب به جواب نمیرسیم برای همین حداکثر عمق رو محدود می کنیم .
تفاوت ها با DFS :
1_ بر خلاف DFS این الگوریتم complete نیستیعنی در صورت وجود جواب پیدا شدنش تضمین شده نیست .
2_ فضای مصرفی این الگوریتم از مرتبه bL هست (L حداکثر عمق انتخابی max_depth ) و زمان b^L که از DFS با زمان m^b و مصرف حافظه bm سریع تر هست (البته در بدترین حالت اگر L رو همون m بگیریم DLS با DFS یکی میشه )
و این که 2 الگوریتم DFS ,DLS هیچ کدوم جواب optimal به ما نمیدن (یعنی بهترین جواب ممکن )
کد این الگوریتم به زبان ++C :
#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);
int main()
{
//test
Node A = 'A', B = 'B', C = 'C', D = 'D'
, E = 'E', F = 'F', G = 'G';
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);
//NodeList result = DLS(graph, G, 2);//chond depth kame goal peida nemishe
NodeList result = DLS(graph, G, 5);//result : ACEFG
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();
}