简单的说一下广搜算法，带个例题NYOJ115 城市平乱
Categories:
Published on: 2011 年 01 月 21 日
广度优先搜索(BFS)的原理和应用
二叉树中的层序遍历就属于一种BFS(Board First Search)
层序遍历会得到ABCDEFG的层序优先序列(BFS序列)。在层序遍历过程中，可以注意到先访问的节点的孩子节点必然先被访问(如访问了Ａ后访问Ｂ和Ｃ，那么Ｂ的孩子结点一定在Ｃ的孩子结点前被访问――仅针对下一层的孩子而言)。据这个特性，可以用队列来实现这个遍历。
void Layer(bitree *p)
queue Q; //定义一个队列
Q.push(*p);
//起始点入队
while(!Q.empty())
N=Q.front();
cout<data<lchild!=NULL)
//将扩展子结点(仅一层)全都入队
Q.push(N->lchild);
if(N->rchild!=NULL)
Q.push(N->rchild);
BFS比它更进一步，可以针对图的结构进行BFS遍历
的BFS(从Ｖ１开始)路径是
广搜的一般结构如下：
定义一个队列;
起始点入队；
while(队列不空){
队头结点出队;
若它是所求的目标状态,跳出循环;
否则，将它扩展出的子结点,全都入队;
若循环中找到目标,输出结果;
否则输出无解;
它的主要特点是：
每次队头元素出队时，扩展其全部的子结点，并用队列记录下来。
搜索过程没有回溯，是一种牺牲空间换取时间的方法。
下边是给出的例题的代码
#include&iostream&
#include&cstring&
#include&queue&
int city[];
struct army
}armys[1005];
bool visited[1005];
int bfs(int Q,int M)
int sum=,temp=0;
queue&int&
memset(visited,0,sizeof(visited));
que.push(Q);
visited[Q]=1;
while(!que.empty())
temp=que.front();
for (int i=1;i&=M;i++)
if(!visited[i] && city[temp][i])
visited[i]=1;
que.push(i);
armys[i].len +=city[temp][i]+armys[temp].
if(armys[i].ishave && sum&armys[i].len) sum=armys[i].
que.pop();
int main()
int T,N,M,P,Q,temp,a,b,c;
while(T--)
memset(armys,0,sizeof(armys));
memset(city,0,sizeof(city));
cin&&N&&M&&P&&Q;
for (int i=0;i&N;i++)
armys[temp].ishave=1;
for (int i=0;i&P;i++)
cin&&a&&b&&c;
if(city[a][b]&c || city[a][b] ==0)
city[a][b]=c;
city[b][a]=c;
cout&&bfs(Q,M)&&
我猜你可能也喜欢：
Share this
三江小渡 All rights reserved
Fastfood theme by
- Powered by
[put here your code]
quickbar tool -->
Recent Posts
by 三江小渡我猜你可能也喜欢：PHP实现双向链表给你的博客添加一个简易的计数器
by 三江小渡最多留言日志2011年全国数学建模B题题解和论文About2011年全国数学建模B题附录程序Clusterin[...]
by 三江小渡最多留言日志2011年全国数学建模B题题解和论文About2011年全国数学建模B题附录程序Clusterin[...]
by 三江小渡安装了rsync程序后，运行以下shell程序即可完成rsync服务的启动，自行修改相关的module和认证用[...]
by 三江小渡mac下没有找到好用的类似secureCRT，就自己写了个自动登录的脚本，分享一下,如果是新浪的，就基本不用修[...]
by 三江小渡协同过滤算法是推荐系统中最古老，也是最简单高效的推荐算法。简单说协同过滤就是根据以往的用户产生的数据分析，对用[...]
by 三江小渡无意中看到哲学家不解释的博客，被她的文章吸引甚深。又看了她的两篇文章：人人主站 和 哲学十二钗问答 。然后特别[...]
by 三江小渡The big difference between MySQL Table Type MyISAM and [...]
by 三江小渡最多留言日志2011年全国数学建模B题题解和论文About2011年全国数学建模B题附录程序Clusterin[...]
by 三江小渡我猜你可能也喜欢：用于大数据的并查集（基于HBase）的java类最长回文子串算法（Manacher）密码学原[...]
Categories
( 102)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 ( 63)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 ( 44)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 ( 22)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 ( 22)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 ( 21)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 ( 20)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 ( 19)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 ( 9)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 ( 7)Recent Posts by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡 by 三江小渡
Recent Comments
将就，不将就 about 楼主，请问一下怎么处理第一问中表格的数据呀，比如1和15节点形成一条路，那么怎么才能求这条路的路程呢？一条路的路程好求，只是不知道有那么多条路，而且在两个表格中的排列顺序也不一样，所以不知道怎么求，要是知道了如何处理数据，后面的都好说，就要交作业了，还行楼主教我，非常谢谢！！！ 郑晓鹏 about 看过代码和分析不太明白为什么要每次需要重置以前的状态 三江小渡 about 对你也有用我也感到很开心～～：） 不会摇头的傻瓜 about 之前看老师推荐的相关论文，都会写稀疏性，潜意识觉得好像真的是硬伤，结果。。。 不会摇头的傻瓜 about 超级赞，最近刚好有用，！谢谢啦~ 唯美句子 about 这分析精神值得学习！！ alan about 感觉很这篇科普型的文章很适合我这种读本科的刚开始学信息安全的人哈哈，以后会多看看你的博文的 三江小渡 about 万能的google 呀~~然后就是豆瓣搜书，看看评价好的 翻译过来的书，甚至会有英文版的书，
就这俩途径~ 火星十一郎--河南理工 about 大神 你好 我是河南理工张朋飞
请求您给我发一份你的标签云的代码
还有我看您对协同过滤简介比较深刻 想请教下您平时如何收集资料的？看的那些资料 如能得到您的指导 感激不尽 火星十一郎--河南理工 about “每次合并或分裂都是局部最优的，但一旦做出决策不能撤销，阻碍了局部最优解变成全局最优。”不是不能撤销，而是考虑到效率问题不进行回溯..........我博客/hxsyl/
Not logged in
Welcome , today is 星期三, 2017 年 03 月 01 日
Leave a comment
feed for comments on this post
Trackback URL
Next Post: NYOJ38布线问题 prim 最小生成树MST
Previous Post: 算法合集之《信息学中守恒法的应用》（不错的文章保存一下）
Top of page
Bottom of page提高组第三题有用广搜的么，标题要长。。。。。。_noip吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：18,643贴子：
提高组第三题有用广搜的么，标题要长。。。。。。收藏
「51修」「免费上门--价明透明-原厂品质」超长质保,维修更放心.更省钱!
广搜状态不好存吧。。
本人开了64MB的数组，最后用了40+M，再多就TLE了
......又不求最短，何必广搜。再说求的是字典序最小，深搜啊。。
= =｜｜在该题目之前。。。广搜。。。。。。。
我就是！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
用三个long long可以存下状态。
果断开了数组
啊，终于看到人了，Orz
弹Orz，不能再损人品了
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或8数码问题的广搜在网上可以找到代码，广搜一般可以找到最优解，但是深搜不一定能找到最优解。一般的深搜多是指定最大递归深度的深搜，一般情况下，问题解的深度很难确定。因此深搜会出现三种情况，一是找到最优解，二是在迭代深度内找不到解，三是找到解但不是最优解。第一种情况自然是最好的，不过较经常出现的是第三种，在指定迭代深度不适当的时候也会出现第二种情况。
在迭代深度内找不到解是最糟糕的一种情况，对这个问题没有什么好的解决办法。有时候我们可以用试凑法，多次测试来找到一个比较好的递归深度。对同一输入在不同迭代深度范围内的比较如下：
对于上面的测试数据，广搜的搜索深度为17，是最优的结果。下面的表格中列出了深搜的搜索深度，可以看到深搜的搜索深度不是固定的。
求得解时深度
在下面给出的8数码问题的深度求解算法中，采用非递归的深度优先搜索，并且给出了一个较合理的递归深度。对于代码中的hash值得求取，可能有好些朋友看不大懂，这里我简单讲解一些为什么这样计算hash值。
我们设 hash = a * 8! + b * 7! + c * 6! + d * 5! + e * 4! + f &* 3! + g * 2! + h * 1! + i * 0! ， 其中 a - i 分别是 0 - 8 的逆序数。到了这里，知道逆序数的朋友可以一下子就明白了。我们可以很容易的证明 a &= 8 , b & 8 , c & 7 ...... b & 8 则一定有 b * 7! & 8! 我们可以得到，如果 hash & 8! ( 即 (hash / 8! ) != 0 ) 则一定有&a
!= 0 ，且 hash / 8! = a，依次类推，我们可以证明 (hash % 8! ) / 7! = b ......这就是一个映射的过程，这个映射可以保证对于一组(a , b , c , d , e , f , g , h , i )一定有唯一的 hash 并且对于 一个 hash 一定有唯一的一组( a , b , c , d , e , f , h , i )相对应。&
【EDigital.h】
#pragma once
#include &queue&
using std::
#define HashTableSize 362881
#define DigitalSize 9
#define MaxDeepth 30
//深度优先搜索的最大搜索深度,对有些数据，其最优解可能超过30深度，这时候深搜，程序将不会给出正确结果
class EDigital
typedef struct
int a[DigitalSize];
typedef struct maps
char detail[DigitalSize];
// 记录自己节点在hash表中的位置
// 记录 空格（0）在序列中的位置
enum Direction
UP=0,DOWN=1,LEFT=2,RIGHT=3
EDigital(const int a[ DigitalSize ]);
EDigital(const Detail& detail);
~EDigital(){}
queue&Detail& FindPath();
void Bfs();
void Dfs ( int depth = MaxDeepth);
inline int HashValue(Map& Parent , int direct );
void init(const Detail& detail);
static const int Factorial[ DigitalSize ];//{40320 , 5040 , 720 , 120 , 24
, 6 , 2 , 1 , 1 }; //8!,7!,6!,5!,4!,3!,2!,1!,0!
static const int derection[ 4 ];//{ -3
} ;// 可移动的四个方向,向上下移动空格(0)位置变化3，左右移动变化1
static int
hashTable[ HashTableSize ];//{0}
};【EDitital.cpp】#include &EDigital.h&
#include&iostream&
#include&queue&
#include&stack&
const int EDigital::Factorial[ 9 ] = { 4, 720, 120, 24, 6, 2, 1, 1}; //8!,7!,6!,5!,4!,3!,2!,1!,0!
const int EDigital::derection[ 4 ] = { -3, 3, -1, 1} ;// 可移动的四个方向,向上下移动空格(0)位置变化3，左右移动变化1
int EDigital::hashTable[HashTableSize] = { 0 };
EDigital::EDigital(const int a[ DigitalSize ])
for(int i=0;i&DigitalS++i)
detail.a[i]=a[i];
init(detail);
EDigital::EDigital(const Detail& detail)
init(detail);
void EDigital::init(const Detail& detail)
for( int i = 0 ; i & DigitalS ++ i )
org.detail[ i ]=detail.a[ i ];
if( org.detail[ i ] == 0 )
org.position =
for( int i = 0 ; i & DigitalS ++ i )
//计算奇排列 &\ 偶排列
if( 0 == org.detail[ i ])
for( int j = 0 ; j &
sum += ( 0 != org.detail[ j ]
&& org.detail[ j ]
& org.detail[ i ] );
int index = 0 ;
for( int i = 0 i & DigitalS ++ i )
// 计算初始状态的hash值
int count = 0 ;
for( int j = 0 j & ++ j )
org.detail[ j ] & org.detail[ i ] ;//逆序数
index += Factorial[ org.detail[ i ] ] *
//hash索引
org.index = index + 1 ;
EndIndex = sum%2 ? 561;
// 目标状态的hash值，八数码存在无解的情况 的hash值为322561
*hash值的计算
*Parent:父状态的hash值
*direct:移动的方向
inline int EDigital::HashValue(Map& Parent , int direct )
int i = Parent.
int newindex = Parent.
char *p = Parent.
switch(direct)
newindex -= 3*40320;
newindex += ( p[ i - 2 ] & p[ i - 3 ]) ? ( Factorial[ p[ i - 3 ] ] ) : ( - Factorial[ p[ i - 2 ] ] );
newindex += ( p[ i - 1 ] & p[ i - 3 ]) ? ( Factorial[ p[ i - 3 ] ] ) : ( - Factorial[ p[ i - 1 ] ] );
newindex += 3*40320;
newindex -= ( p[ i + 2 ] & p[ i + 3 ]) ? ( Factorial[ p[ i + 3 ] ] ) : ( - Factorial[ p[ i + 2 ] ] );
newindex -= ( p[ i + 1 ] & p[ i + 3 ]) ? ( Factorial[ p[ i + 3 ] ] ) : ( - Factorial[ p[ i + 1 ] ] );
return newindex - 40320;
case RIGHT :
return newindex + 40320;
广度优先搜索
void EDigital::Bfs()
using std::
queue&Map& Q
Queue.push(org);
hashTable[ org.index ] = -1;
while( ! Queue.empty() )
= Queue.front();
if( node.index == EndIndex )
Queue.pop();
for(int k =0 ; k & 4; k ++ )
tmp.position = node.position + derection[k];
if(tmp.position & 0 || tmp.position & 8 || ( k & 1 && tmp.position / 3 != node.position /3 ) )
tmp.index = HashValue( node , k );
if(0 != hashTable[tmp.index] )//已经存在该状态
tmp.detail[ node.position ] = tmp.detail[ tmp.position ] ;
// 移动空格
tmp.detail[ tmp.position ]
hashTable[tmp.index] = node.
// 状态记录到hashtable中
Queue.push( tmp );
深度优先搜索
void EDigital::Dfs( int depth /*= MaxDeepth*/)
using std::
stack&Map& S
stack&char& FS
Stack.push( org );
FStack.push( 0 );
hashTable[ org.index ] = -1;
while( ! Stack.empty() )
= Stack.top();
if( node.index == EndIndex )
//node即为当前结果
char count = FStack.top();
//扩展标记
FStack.pop();
if(Stack.size() & depth ||
count &= 4 ) //最大扩展30深度
Stack.pop();
hashTable[ node.index ] = 0;
else//扩展
FStack.push( count + 1 );
tmp.position = node.position + derection[count];
if(tmp.position & 0 || tmp.position & 8 || ( count & 1 && tmp.position / 3 != node.position /3 ) ) //越界 或者 左右移动时不在同一层
tmp.index = HashValue( node , (int)count );
if(0 != hashTable[tmp.index] )
//已经存在该状态
// 移动空格
tmp.detail[ node.position ] = tmp.detail[ tmp.position ] ;
tmp.detail[ tmp.position ]
// 状态记录到hashtable中
hashTable[tmp.index] = node.
Stack.push( tmp );
FStack.push( 0 );
if(Stack.empty())
hashTable[ EndIndex ] = -1;
* 通过hash表中记录的进行查找路径
queue&EDigital::Detail& EDigital::FindPath()
using std::
vector&int& S
Stack.push_back(EndIndex);
int nowindex = EndI
while( -1 != hashTable[ nowindex ] )
Stack.push_back(hashTable[ nowindex ]);
nowindex = hashTable[ nowindex ];
int nixu[9];
queue&Detail&
while( ! Stack.empty())
nowindex = Stack.back() - 1 ;
Stack.pop_back();
for( int i = 0 ; i & DigitalS i ++ )
// 计算出逆序
nixu[i] = nowindex / Factorial[ i ] ;
nowindex %= Factorial[ i ];
memset( temp.a , -1 , DigitalSize *sizeof(int));
for( int i = 0 ; i & 9 ; ++ i )
// 根据逆序计算排列
for( int k = nixu[i] ; j & DigitalS ++ j )
if(temp.a[j] == -1 ) k --;
if( k & 0 )
temp.a[j] =
result.push(temp);
} 【main.cpp】
#include&iostream&
#include&EDigital.h&
#include&queue&
#include&string&
#include&Windows.h&
using std::
using std::
using std::
using std::
using std::
int main()
cout && &------输入(例)------& &&
cout && &\t1 2 3& &&
cout && &\t4 5 6& &&
cout && &\t7 8 0& &&
cout && &--------------------& &&
EDigital::D
for( int i = 0 ; i & 9 ; i ++ )
cin && detail.a[ i ];
cout && &--------------------& &&
cout && &1. 深搜
2.广搜& &&
cout && &--------------------& &&
EDigital eight(detail);
long time =GetTickCount();
if( op == &1& )
cout && &输入迭代深度&&;
time = GetTickCount();
eight.Dfs( depth );
eight.Bfs();
cout && &计算用时：& && GetTickCount()-time && &MS\n&;
queue&EDigital::Detail& details = eight.FindPath();
printf(&共需： %d 步\n&,details.size()-1);
getchar();
int count=0;
while( ! details.empty())
EDigital::Detail result = details.front();
details.pop();
for( int i =0 ; i & 9 ; i ++ )
cout.width(3);
cout && result.a[i];
if( 2 == i % 3 )
cout && (&\n&);
if(0 != details.size() )
cout && &\n
↓ 第& && ++ count && &步\n&;
getchar();
整个工程的源代码也可以到这里下载
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：7689次
排名：千里之外
原创：14篇
(1)(6)(4)(4)扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
给我一些pascal题目:关于深搜,广搜的越多越好
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
. Faibonacci数列前几项为: 0,1,1,2,3,5,8,…,其规律是从第三项起, 每项均等于前两项之和.求前30项, 并以每行5个数的格式输出.. Faibonacci数列前几项为: 0,1,1,2,3,5,8,…,其规律是从第三项起, 每项均等于前两项之和.求前30项, 并以每行5个数的格式输出.
为您推荐：
其他类似问题
韩信点兵问题猴子吃枣问题波浪数问题钞票兑换还要的话问我
扫描下载二维码>> 双向广搜求解八数码问题,双向广搜求解八数码问题
双向广搜求解八数码问题,双向广搜求解八数码问题
所属分类：
下载地址：
twicedirectionfor8.r文件大小：1.47 kB
分享有礼！ 》
请点击右侧的分享按钮，把本代码分享到各社交媒体。
通过您的分享链接访问Codeforge，每来2个新的IP，您将获得0.1 积分的奖励。
通过您的分享链接，每成功注册一个用户，该用户在Codeforge上所获得的每1个积分，您都将获得0.2 积分的分成奖励。
双向广搜求解八数码问题,双向广搜求解八数码问题-Collected eight two-way digital problem solving, two-way collected eight digital problem solving
Sponsored links
源码文件列表
温馨提示： 点击源码文件名可预览文件内容哦 ^_^
4.43 kB19-09-08 09:23
（提交有效评论获得积分）
评论内容不能少于15个字，不要超出160个字。
评价成功，多谢！
下载twicedirectionfor8.r
CodeForge积分（原CF币）全新升级，功能更强大，使用更便捷，不仅可以用来下载海量源代码马上还可兑换精美小礼品了
您的积分不足，优惠套餐快速获取 30 积分
10积分 / ￥100
30积分 / ￥200原价 ￥300 元
100积分 / ￥500原价 ￥1000 元
订单支付完成后，积分将自动加入到您的账号。以下是优惠期的人民币价格，优惠期过后将恢复美元价格。
支付宝支付宝付款
微信钱包微信付款
更多付款方式：、
您本次下载所消耗的积分将转交上传作者。
同一源码，30天内重复下载，只扣除一次积分。
鲁ICP备号-3 runtime:Elapsed:643.618ms - init:0.1;find:1.4;t:0.5;tags:0.4;related:22.0;comment:0.2; 27.69
登录 CodeForge
还没有CodeForge账号？
Switch to the English version?
^_^"呃 ...
Sorry!这位大神很神秘，未开通博客呢，请浏览一下其他的吧
