我的无代价宽度优先的搜索雄踞百度和google的开头.....
问题当时没有解决.语言是tsql.也没有系统学过这个.所以就给做出来...(while语句不会写)
现在好了.今天复习到了线性代数.看到了15面得题目.这个问题解决了.有开大家可以翻一下教科书.高教出版社的<线性代数及其应用>.同济2版吧.计算图的路径.
题目.例1.10.设航空公司在四个城市间航行运行图如图 记者从d出发.1)有几条经过3次航行到达城市c的线路?
2)有几条经4次回到城市d的路线?
它话的图是个正五角形.里面有连线.太麻烦.我直接把上面的数组表示出来
a b c d e
a 0 0 1 1 0
b 1 0 1 0 1
c 0 0 0 1 0
d 0 1 0 0 0
e 1 0 1 1 0 这个矩阵命名为A
说明.这个主对角线为0.说明没有空弧.就是说不能放弃坐飞机的机会.每次必须坐飞机.
a
a 0
b 1 特别说明 这个1的表示为 (b,a)=1
这个b的那个1表示从b出发.到a有线路.
好算符构造完毕 .
运算.就是矩阵的乘方运算
这里A^2 A^3 A^4我就不公布了.还有一刻钟断网.
A的乘方的含义.A^2表示两次坐飞机可以到得路径.
计算机运算含义赋值 (b,a)表示从b出发到a有的线路条数 .在A^2 (b,a)=1 A^3 (b,a)=2 分别表示第二次,第三次飞机 从b到a有1条线路和2条线路
矩阵的乘法运算还是比较简单的...还有个 如果是A定义为2维数组就可以了..怎么表示A^3? 这个可以用A[3][ ][ ]来解决.还有个是回到题目本身.计算得到.有3条路经过三次到达城市c的线路.那么是那三条?
这个需要对矩阵开始分解.检测(d,c)所在的矩阵坐标.(行,列)之后挨个反向查A^2 A就可以了.
结论:每次计算从A开始.看起始路径到目标路径是否为1. //A的肯定为1 后面A开始乘法运算.A^N=A^(N-1)*A
是1就终止搜索.输出路径.之后再把每次路径的长度计算出来就得到最优解.这个也是基于宽度优先的算法.