الگوریتم Iterative deepening depth-first search چیست ؟

Question

• الگوریتم Iterative deepening depth-first search یا IDDFS چیه ؟
• چه مزیتی نسبت به DFS داره ؟
•  به چه شکل پیاده سازی میشه ؟

Answer 1

اگر ما الگوریتم 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();
}