الگوریتم جست وجوی depth-limited search

Question

این الگوریتم با DFS چه تفاوتی داره ؟ مزیت نسبت به DFS چیه و چه جایی استفاده میشه ؟

Answer 1

اگر در جست و جوی 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();
}

 

Answer 2

الگوریتم جستجوی Depth-Limited Search (DLS) یک تغییر ساده از الگوریتم جستجوی عمق اول (DFS) است. در DLS، محدودیتی برای عمق جستجو تعیین می‌شود و الگوریتم تا آن عمق جستجو را انجام می‌دهد. به عبارت دیگر، DLS تا عمق مشخص شده جستجو می‌کند و در صورتی که به این عمق برسد و هنوز هدف را پیدا نکرده باشد، جستجو را متوقف می‌کند.

 

تفاوت اصلی بین DLS و DFS در محدودیت عمق جستجو است. در DFS، الگوریتم به طور نامحدود در عمق گراف حرکت می‌کند تا هدف را پیدا کند یا تمام گره‌ها را بررسی کند. این ممکن است منجر به جستجوی بی‌نهایت در صورتی که هدف در عمق بالا قرار داشته باشد.

 

اما در DLS، با تعیین یک محدودیت عمق، الگوریتم می‌تواند جستجو را متوقف کند و از جستجوی بی‌نهایت جلوگیری کند. این محدودیت عمق می‌تواند به عنوان یک پارامتر ورودی به الگوریتم داده شود و میزان عمق مورد نظر را تعیین می‌کند.

 

مزیت اصلی DLS نسبت به DFS این است که جستجوی بی‌نهایت را در عمق‌های بالا جلوگیری می‌کند. این الگوریتم به خوبی در مسائلی که عمق جستجو مهم است، مورد است

 

#include <iostream>
#include <list>
using namespace std;

class Graph {
    int V; // Number of vertices
    list<int> *adj; // Pointer to an array containing adjacency lists

public:
    Graph(int V); // Constructor
    void addEdge(int v, int w); // Function to add an edge to the graph
    bool DLS(int v, int target, int depth); // Depth-Limited Search function
    bool DLSUtil(int v, int target, int depth, bool visited[]); // Utility function for DLS
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

bool Graph::DLSUtil(int v, int target, int depth, bool visited[]) {
    if (depth == 0 && v == target)
        return true;

    if (depth > 0) {
        visited[v] = true;

        for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
            if (!visited[*i] && DLSUtil(*i, target, depth - 1, visited))
                return true;
    }

    return false;
}

bool Graph::DLS(int v, int target, int depth) {
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    return DLSUtil(v, target, depth, visited);
}

int main() {
    Graph g(7);
    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 startVertex = 0;
    int targetVertex = 6;
    int maxDepth = 3;

    if (g.DLS(startVertex, targetVertex, maxDepth))
        cout << "Target found within the depth limit.\n";
    else
        cout << "Target not found within the depth limit.\n";

    return 0;
}