人工智能 - 无信息搜索策略的简单实现
4.73/5 (28投票s)
人工智能课程中无信息搜索策略的简单实现。
引言
本文旨在帮助人工智能课程的初学者了解无信息搜索策略（盲搜索）的目标和实现，该策略仅使用问题定义中提供的信息。
无信息搜索包括以下算法
- 广度优先搜索（BFS）
- 统一代价搜索 (UCS)
- 深度优先搜索（DFS）
- 深度受限搜索 (DLS)
- 迭代加深搜索 (IDS)
- 双向搜索 (BS)
背景
本文涵盖了几种属于无信息搜索范畴的搜索策略。该术语意味着这些策略除了问题定义中提供的信息外，没有其他额外信息。它们只能生成后继节点，并将目标节点与非目标节点区分开来。所有搜索策略都通过扩展节点的顺序来区分。
为了继续这一系列文章，我将使用一些人工智能术语，如下所示
一个问题可以由四个组成部分定义
- 问题开始的初始状态
- 问题结束的目标状态
- 寻找导致目标状态的动作序列
- 解决问题的路径代价
初始状态、目标状态、动作和路径代价共同定义了问题状态空间（从初始状态通过任何动作序列可达的所有状态的集合）。状态空间中的路径是连接动作序列的状态序列。问题的解决方案是一个从初始状态到目标状态的动作序列。
查看达到目标的动作序列的过程称为搜索。搜索算法以问题作为输入，并以动作序列的形式返回解决方案。搜索从初始状态开始，初始状态代表问题搜索空间中的根节点。分支是动作，节点对应于问题状态空间中的状态。
示例
8数码问题状态空间的一小部分
注意：深度=从初始状态到该状态的步数。
已生成但尚未扩展的节点集合称为边缘；边缘的每个元素都是一个叶节点（即在树中没有后继节点）。
让我们开始解释前两种盲搜索算法
- 广度优先搜索 (BFS)：是一种简单的策略，首先扩展根节点，然后扩展根节点的所有后继节点，接着扩展它们的后继节点，以此类推。边缘是一个先进先出队列。
- 统一代价搜索 (UCS)：修改了 BFS，总是使用路径代价函数 g(n)（即从初始状态到节点 n 的路径的代价）来扩展边缘上成本最低的节点。节点按路径代价递增的顺序存储在队列中。
- 深度优先搜索 (DFS)：总是扩展搜索树当前边缘中最深的节点。边缘是一个后进先出队列（堆栈）。
- 深度受限搜索 (DLS)：通过为 DFS 提供预定的深度限制 l，可以缓解 DFS 在无限状态空间中的尴尬失败，即深度为 l 的节点被视为没有后继节点。
- 迭代加深深度优先搜索 (IDS)：是一种常用的通用策略，通常与深度优先树搜索结合使用，以找到最佳深度限制。它通过逐渐增加限制来实现此目的，首先为 0，然后为 1，然后为 2，依此类推，直到找到目标。
- 双向搜索 (BS)：双向搜索的原理是从初始状态向前搜索，并从目标状态向后搜索，当两个搜索在中间相遇时停止。这里有两个边缘，一个维护向前搜索的节点，另一个维护向后搜索的节点。每个边缘的实现是后进先出还是先进先出，取决于搜索中使用的搜索策略（即向前=BFS，向后=DFS）。
Using the Code
我的代码中的第一个类是 Node.cs，它将节点表示为状态空间中的数据结构。每个节点都有一些属性，如深度、代价、状态和父节点。状态属性根据问题状态空间内的物理配置进行定义。我的代码仅仅是在正数状态空间中搜索一个数字，所以状态在这里被简单地定义为一个整数。
让我们通过以下片段来探索 Node 类
// class Node.cs
class Node
{
public int depth;
public int State;
public int Cost;
public Node Parent;
// Parent Node which has depth =0 and parent = null;
public Node (int State)
{
this.State = State;
this.Parent = null;
this.depth = 0;
}
// another form of Node Constructor which accepts only the State;
public Node(int State)
{
this.State = State;
}
// this form of Generalization of Node Constructor which accepts
// any node root or ordinary node;
public Node(int State,Node Parent)
{
this.State = State;
this.Parent = Parent;
if (Parent == null)
this.depth = 0;
else
this.depth = Parent.depth + 1;
}
// this form of Generalization of Node Constructor which accept
// any node root or ordinary node and accept the cost of each node;
public Node(int State, Node Parent, int Cost)
{
this.State = State;
this.Parent = Parent;
this.Cost = Cost;
if (Parent == null)
this.depth = 0;
else
this.depth = Parent.depth + 1;
}
}
我的代码搜索范围是从 0, 1, 2, ...N 的数字，所以初始状态是 0，目标状态是用户指定的数字。数字生成的每一步的代价是随机数或 1。GetSucc.cs 类定义了 GetSussessor() 函数，该函数包含按顺序生成正数所需的可能动作集。GetSussessor() 的输入是问题的当前状态（即初始状态 0），输出是当前状态可达的下一个状态的 ArrayList（例如，从 0 到下一个状态 1、2，假设我们的树是二叉树）。
class GetSucc
{
//if search go forward from 0 to number n
public ArrayList GetSussessor(int State)
{
ArrayList Result = new ArrayList();
Result.Add(2 * State + 1);
Result.Add(2 * State + 2);
return Result;
}
//if search go backward from n to number 0
public ArrayList GetSussessor_Reverse(int State)
{
ArrayList Result = new ArrayList();
if (State % 2 == 0)
{
int P = State / 2 - 1;
Result.Add(P);
}
else
{
int Sib = State + 1;
Result.Add(Sib / 2 - 1);
}
return Result;
}
//if the cost of each node must be determined
public ArrayList GetSussessor(int State,Node Parent)
{
ArrayList Result = new ArrayList();
Random n = new Random();
Test s = new Test();
Result.Add(new Node(2* State + 1,Parent,n.Next(1,100)+Parent.Cost));
Result.Add(new Node(2* State + 2, Parent,n.Next(1,100) + Parent.Cost));
Result.Sort(s);
return Result;
}
}//end class
//implement the interface IComparer to compare objects in ArrayList
public class Test : IComparer
{
public int Compare(object x, object y)
{
int val1 = ((Node)x).Cost;
int val2 = ((Node)y).Cost;
if (val1 <= val2)
return 1;
else
return 0;
}
}//end class Test
从这里开始，让我们开始编写无信息搜索策略的代码
广度优先搜索
public static void Breadth_First_Search(Node Start, Node Goal)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
Queue Fringe = new Queue();
Fringe.Enqueue(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Dequeue();
Console.WriteLine("Node {0} Visited ", Parent.State);
//Console.ReadKey();
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
break;
}//end if
children = x.GetSussessor(Parent.State);
for (int i = 0; i < children.Count; i++)
{
int State = (int)children[i];
Node Tem = new Node(State, Parent);
Fringe.Enqueue(Tem);
}//end for
}//end while
}//end method
统一代价搜索
public static void Uniform_Cost_Search(Node Start,Node Goal)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
PriorityQueue Fringe = new PriorityQueue();
Fringe.Enqueue(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Dequeue();
Console.WriteLine("Node {0} Visited with Cost {1} ",
Parent.State,Parent.Cost);
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
break;
}//end if
children = x.GetSussessor(Parent.State,Parent);
for (int i = 0; i < children.Count; i++)
{
Fringe.Enqueue((Node)children[i]);
}//end for
}//end while
}// end method
深度优先搜索
public static void Depth_First_Search(Node Start, Node Goal)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
Stack Fringe = new Stack();
Fringe.Push(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Pop();
Console.WriteLine("Node {0} Visited ", Parent.State);
Console.ReadKey();
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
break;
}//end if
children = x.GetSussessor(Parent.State);
for (int i = 0; i < children.Count; i++)
{
int State = (int)children[i];
Node Tem = new Node(State, Parent);
Fringe.Push(Tem);
}//end for
}//end while
}//end method
深度受限搜索
public static void Depth_Limited_Search(Node Start, Node Goal, int depth_Limite)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
Stack Fringe = new Stack();
Fringe.Push(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Pop();
Console.WriteLine("Node {0} Visited ", Parent.State);
// Console.ReadKey();
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
break;
}//end if
if (Parent.depth == depth_Limite)
{
continue;
}
else
{
children = x.GetSussessor(Parent.State);
for (int i = 0; i < children.Count; i++)
{
int State = (int)children[i];
Node Tem = new Node(State, Parent);
Fringe.Push(Tem);
}//end for
}//end else
}//end while
}//end method
迭代加深搜索
public static void Iterative_Deepening_Search(Node Start, Node Goal)
{
bool Cutt_off = false;
int depth = 0;
while(Cutt_off == false)
{
Console.WriteLine("Search Goal at Depth {0}",depth);
Depth_Limited_Search(Start, Goal, depth,ref Cutt_off);
Console.WriteLine("-----------------------------");
depth++;
}
}//end method
public static void Depth_Limited_Search(Node Start, Node Goal,
int depth_Limite,ref bool Cut_off)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
Stack Fringe = new Stack();
Fringe.Push(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Pop();
Console.WriteLine("Node {0} Visited ", Parent.State);
// Console.ReadKey();
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
Cut_off = true;
break;
}//end if
if (Parent.depth == depth_Limite)
{
continue;
}
else
{
children = x.GetSussessor(Parent.State);
for (int i = 0; i < children.Count; i++)
{
int State = (int)children[i];
Node Tem = new Node(State, Parent);
Fringe.Push(Tem);
}//end for
}//end else
}//end while
}//end method
双向搜索
public static void Bidirectional_Search(Node Start,Node Goal)
{
GetSucc x = new GetSucc();
ArrayList Children_1 = new ArrayList();
ArrayList Children_2 = new ArrayList();
Queue Fringe_IN = new Queue();
Queue Fringe_GO = new Queue();
Fringe_IN.Enqueue(Start);
Fringe_GO.Enqueue(Goal);
while((Fringe_IN.Count !=0)&&(Fringe_GO.Count!=0))
{
Node Parent1 = (Node)Fringe_IN.Dequeue();
Console.WriteLine("Node {0} Visited ", Parent1.State);
//Console.ReadKey();
if ((Parent1.State == Goal.State)||Contain(Fringe_GO,Parent1))
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent1.State);
break;
}//end if
Children_1 = x.GetSussessor(Parent1.State);
for (int i = 0; i < Children_1.Count; i++)
{
int State = (int)Children_1[i];
Node Tem = new Node(State, Parent1);
Fringe_IN.Enqueue(Tem);
}//end for
Node Parent2 = (Node)Fringe_GO.Dequeue();
Console.WriteLine("Node {0} Visited ", Parent2.State);
//Console.ReadKey();
if ((Parent2.State == Start.State) || Contain(Fringe_IN,Parent2))
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent2.State);
break;
}//end if
Children_2 = x.GetSussessor_Reverse(Parent2.State);
for (int i = 0; i < Children_2.Count; i++)
{
int State = (int)Children_2[i];
Node Tem = new Node(State, Parent2);
Fringe_GO.Enqueue(Tem);
}//end for
}//end while
}//End Method
public static bool Contain(Queue Fringe,Node Parent)
{
object[] S = new object[Fringe.Count];
S = Fringe.ToArray();
for (int i = 0; i < S.Length; i++)
{
Node Target = (Node)S[i];
if (Target.State == Parent.State)
{
return true;
}
}
return false;
}
参考
- Stuart Russell, Peter Norving, 人工智能：一种现代方法