当前位置:天才代写 > tutorial > 大数据教程 > 算法之图搜索算法(一)

算法之图搜索算法(一)

2021-02-21 17:39 星期日 所属: 大数据教程 浏览:1062

1. 详细介绍

文中详细介绍了较为初中级的图优化算法,包含深度优先解析xml,深度广度优先选择解析xml和双重深度广度优先选择解析xml。

2. 深度优先解析xmlDFS

2.1 优化算法观念

从图上某一端点v逐渐,浏览此连接点,随后先后从v中未被浏览的临接点考虑深度优先解析xml图,直至图上上全部和v有途径互通的端点都被浏览;若这时图上还有端点未被浏览,则代选图上一个未被浏览端点做起始点,反复之上全过程,直至图上全部端点都被浏览截止。

深度优先检索解析xml类似树的先序遍历。假设给出图G的初态是全部端点均未被浏览过,在G中随意选择一个端点i做为解析xml的原始点,则深度优先检索解析xml可定义以下:

(1)    最先浏览端点i,并将其浏览标识置为浏览过,即visited[i]=1;

(2)    随后检索与端点i有边相接的下一个端点j,若j未被浏览过,则浏览它,并将j的浏览标识置为浏览过,visited[j]=1,随后从j逐渐反复此全过程,若j已浏览,再看与i有边相接的其他端点;

(3)    若与i有边相接的端点都被浏览过,则退还到前一个浏览端点并反复刚刚全过程,直至图上全部端点都被浏览完止。

2.2 优化算法完成

邻接矩阵的优化算法叙述为下边方式:

void dfs1(graph &g,int i,int n)//深度优先
{//从端点i考虑解析xml  临界值引流矩阵
	cout<<g.v[i];//輸出浏览端点
	visited[i]=1;
	for(j=1;j<=n;j  )
		if((g.arcs[i][j]==1)&&(!visited[j]))
			dfs1(g,j,n);
}

邻接表优化算法叙述为下边方式:

void dfs2(adjlist GL,int i,int n)
{//深度优先 ----从端点i考虑解析xml,算法设计选用邻接表
	cout<<i<<" ";
	visited[i]=1;
	edgenode* p=GL[i];
	while(p!=NULL)
	{
		if(!visited[p->adjvex])
			dfs2(G,p.adjvex,n);
		p=p->next;
	}
}

2.3 应用领域

必须有次序解析xml图,且寻找一个解后輸出就可以。如:trie树排列

多用以只需求得,而且解释树中的反复连接点较多而且反复较难分辨时应用,但通常可以用A*或回溯算法替代。

2.4 举例说明

数独求解。得出一个不详细的数独,让添充在其中空缺的数据。

大量题型:

POJ 1321 旗盘难题:http://www.cublog.cn/u3/105033/showart_2212140.html

类迷宫问题:http://www.jguoer.com/post/2010/02/17/DFS-Code.aspx

数独难题:http://acm.hdu.edu.cn/showproblem.php?pid=1426

3. 深度广度优先选择解析xmlBFS

3.1 优化算法观念

深度广度优先选择检索解析xml类似树的按层级解析xml。设图G的初态是全部端点均未浏览,在G 随意选择一端点i做为原始点,则深度广度优先选择检索的基础观念是:

(1)最先浏览端点i,并将其浏览标示置为已被浏览,即visited[i]=1;

(2)然后先后浏览与端点i有边相接的全部端点W1,W2,…,Wt;

(3)随后再按序浏览与W1,W2,…,Wt有边相接又不曾浏览过的端点;

以此类推,直至图上全部端点都被浏览完截止。

3.2 优化算法完成

用邻接矩阵的优化算法叙述以下:

void bfs1(graph g,int i)
{//从端点i考虑深度广度优先选择解析xml.算法设计为邻接矩阵
	Queue q;
	cout<<g.v[i];
	visited[i]=1;
	q.insert(i);
	while(!q.empty())
	{
		int k=q.delete();
		for(j=0;j<n;j  )
		{
			if((g.a[k][j])&&!visited[j])
			{
				cout<<g.v[j];
				visited[j]=1;
				q.insert(j);
			}
		}
	}
}

用邻接表的优化算法叙述以下 :

void bfs2(adjlist GL,int i,int n)
{//深度广度优先选择解析xml 从i考虑,应用邻接表做为算法设计
	queue q;
	cout<<i<<" ";
	visited[i]=1;
	q.insert(i);
	while(!q.empty())
	{
		int k=q.pop();
		edgenode* p=GL[k];
		while(p!=NULL)
		{
			if(!visited[p->adjvex])
			{
				cout<<p->adjvex;
				visited[p->adjvex]=1;
				q.insert(p->adjvex);
			}
			p=p->next;
		}
	}
}

3.3 应用领域

求难题的最优解

3.4 举例说明

给出一个8*8的方格地形图,再给出最初的状态和停止情况,輸出从原始点抵达停止点的至少计步。

大量题型:

http://www.cppblog.com/firstnode/archive/2009/03/07/75839.html

http://blog.sina.com.cn/s/blog_6635898a0100hwe3.html

http://blog.csdn.net/super_chris/archive/2009/12/26/5082666.aspx

http://www.chenyajun.com/2010/05/08/4540

4. 双重深度广度优先选择解析xml

4.1 优化算法观念

有一些难题依照深度广度优先选择检索规律拓展节点的标准,既合适次序,也合适反序,因此大家考虑到在找寻总体目标节点或途径的检索全过程中,原始节点向总体目标节点和总体目标节点向原始节点另外开展拓展,直到在2个拓展方位上出現同一个子节点,检索完毕,这就是双重检索全过程。

出現的这一同一子节点,大家称之为交叉点,假如的确存有一条从原始节点到总体目标节点的最好途径,那麼按双重检索开展检索必定会在某层出現“交叉”,既有交叉点,原始节点一交叉点一总体目标节点所产生的一条途径就是所愿途径。

4.2 优化算法完成

转自:http://blog.sina.com.cn/s/blog_8627bf080100ticx.html

如今再讨论一下双重广搜免费模板:

void TBFS()
{
  bool found=false;
  memset(visited,0,sizeof(visited)); // 判重二维数组
  while(!Q1.empty()) Q1.pop(); // 顺向序列
  while(!Q2.empty()) Q2.pop(); // 反方向序列

  //======顺向拓展的情况标识为1,反方向拓展标识为2
  visited[s1.state]=1; // 最初的状态标识为1
  visited[s2.state]=2; // 完毕情况标识为2
  Q1.push(s1); // 最初的状态入顺向序列
  Q2.push(s2); // 完毕情况入反方向序列
  while(!Q1.empty() || !Q2.empty())
  {
    if(!Q1.empty())
      BFS_expand(Q1,true); // 在顺向序列中检索
    if(found) // 检索完毕
      return ;

    if(!Q2.empty())
      BFS_expand(Q2,false); // 在反方向序列中检索

    if(found) // 检索完毕
      return ;
  }
}

void BFS_expand(queue<Status> &Q,bool flag)
{
  s=Q.front(); // 从序列中获得头节点s
  Q.pop()
  for( 每一个s 的子连接点 t )
  {
    t.state=Gethash(t.temp) // 获得子连接点的情况
    if(flag) // 在顺向序列中分辨
    {
      if (visited[t.state]!=1)// 没在顺向序列出現过
   {
        if(visited[t.state]==2) // 该情况在反方向序列中出現过
          {
            //各种各样实际操作;
            found=true;
            return;
         }
        visited[t.state]=1; // 标识为在在顺向序列中
        Q.push(t); // 入队
    }
  }else // 在顺向序列中分辨
  {
    if (visited[t.state]!=2) // 没在反方向序列出現过
   {
        if(visited[t.state]==1) // 该情况在顺向向序列中出現过
        {
          各种各样实际操作;
          found=true;
          return;
        }
        visited[t.state]=2; // 标识为在反方向序列中
        Q.push(t); // 入队
    }
  }
}   

4.3 应用领域

最优控制难题中,了解难题的起止情况和最后情况,且2个情况可互相抵达。

4.4 举例说明

旗盘上面有四个棋盘,让你2个情况,问能否8步内将一个情况迁移到另一个情况?

5. DFS与BFS较为

算法设计:DFS选用栈,而BFS选用序列

优化算法观念:深度搜索与深度广度检索的系统结构和造成系统软件很类似,唯一的差别取决于对拓展连接点选择上。因为其保存了全部的前继连接点,因此在造成后续连接点时能够除掉一部分反复的连接点,进而提升 了检索高效率。这二种优化算法每一次都拓展一个连接点的全部子连接点,而不一样的是,深度搜索下一次拓展的是此次拓展出去的子连接点中的一个,而深度广度检索拓展的则是此次拓展的连接点的弟兄连接点

应用范畴:DFS能够快速的寻找一个解,随后运用这一解开展修枝,而BFS可寻找最优解。

 

    关键字:

天才代写-代写联系方式