Giải thuật tìm kiếm sâu dần

1. Kỹ thuật tìm kiếm sâu dần

Kỹ thuật tìm kiếm sâu dần là thực hiện việc tìm kiếm với độ sâu ở mức giưói hạn d nào đó. Nếu không tìm ra nghiệm ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên được lặp lại với d lần lượt là 1, 2,…đến độ sâu max nào đó.
Kỹ thuật tìm kiếm sâu dần thường được thực hiện khi cây tìm kiếm chứa nhánh vô hạn, và nếu sử dụng tìm kiếm theo độ sâu ta có thể mắc kẹt ở một nhánh nào đó (thuật toán không dừng) và không tìm ra nghiệm
2. Giải thuật
Thuật toán tìm kiếm sâu dần sử dụng thuật toán tìm kiếm sâu hạn chế như thủ tục con. Đó là thủ tục tìm kiếm theo chiều sâu nhưng chỉ tới độ sâu d nào đó rồi quay lên.


bool result = false;
openList.Push(n0);
deepOfNode(no, 0);//độ sâu của đỉnh xuất phát là 0
while (!openList.IsEmpty())
{
node = openList.Pop();
if (node.Equals(n*))
{
result = true;
break;
}closeList.Push(node);
int deep = deepOfNode[node];
if (deep < limitedDeep)
{
for (n in Tn(node))
{
if (!openList.InList(n) && !closeList.InList(n))
{
openList.Push(n);
BeforeOfNode(n, node);
deepOfNode.Add(n, deep + 1);//độ sâu của đỉnh n
}
}
}
}

if (result)
{
DisplayResult();
}
else
{
NotFound();
}

 

3. Ví dụ

Cho đồ thị như hình vẽ

Đỉnh xuất phát là (1), đỉnh đích là (11), độ sâu giới hạn là 3

Các bước chi tiết thực hiện giải thuật

Kết quả