2个有关问题；1.深搜，广搜的理解；Floyd算法构造前驱路径
2个问题；1.深搜，广搜的理解；Floyd算法构造前驱路径；
问题1：
最近一直在弄图, 学着学着就发现疑问慢慢变多,大家看一下耳熟能详的深搜和广搜基础:
广搜: 如果从A到B存在路径，则广搜一定能找到从A到B的一条最短路径, 这是毋庸置疑的.....
让我理解这个应用,就好像有向图的传递封包一样,就是找到一条从A到B的最短路径(边最少).
深搜: 如果有A到B的路径,那么深搜能找出所有从A到B的路径,这应该是深搜的特点吧.....
大家我的理解是否正确,不正确请纠正,不全面请补充,有更深的理解或实战经验请分享,谢谢啦..
------------------------------------------------------------
问题2：
三层循环过程中,如果已经判定:
dist i,j = dist i,k + dist k,j ,那么parent[i][j]=parent[k][j],这是算法导论书上证明的,没错吧...
那么算法运行完成后，我想打印i到j的最短路径，这样递归对不对:
print(i,j)
{
if(i==j)
{output i;return;}
else
{print(i,parent[i][j]);output j;}
}
------解决方案--------------------
已知点集合 V={v1,v2,v3...vn}通过边连接起来
深度优先模型：
void Find1(v)
{
while(广度++)
{
Find1(新找到的点);//递归
}
}
可以看出他先把某一分支的第一分支一直搜到底，再搜第2分支的第一。。。。
广度优先模型：
声明全局点集合 R={r0}初始为出发节点。
void Find2(r)
{
while(广度++)
{
R.添加(新找到的点);
}
R.移除(旧的点);
while(新广度++)
{
Find2(r);//递归
}
}
以下边图为例：
1
/ \
2 3
/ \ |\
4 5 6 7
深度优先的执行顺序是：
1245367
广度优先是：
1234567
深度优先一般适合查找最长路径。成语接龙例子就是深度优先.
广度优先一般适合查找最短路径或者找到就退出，比较常用。
成语接龙的思路是:
0,分析全部成语,把头尾汉字用Unicode转成数字,再减去short.Maxvalue使其分布在short范围内,以节省内存.如果用string是比较废内存的.
1,利用泛型容器Dictionary查找Key速度是O(1)的哈希散列特点,建立两个字典,一个是全部成语,一个是头索引的多个成语.
2,输入一个成语后点按钮,把尾节点作为头,深度优先搜索.(排除环,检测有环复杂度O(1))
3,每一分钟检查一下是否有更长的龙出现.
代码以前公布过,现在没空间了,可以很快找出3000以上无环的成语长龙.
------解决方案--------------------
我们讨论一下,做一个成语接龙,需要多少算法和数据结构(AS)的知识?
首先,我要着重说一点,学习AS,要从大欧记法开始O(),这个用东北话来说,就是"必须的".
然后,我们先说,成语这个东东:
先,是数量上10000多个成语,不仅让人惊叹,老祖宗留下这个东西,太TMD的适合咱们学习和娱乐了,正好可以考验几乎全面的AS知识和技能,没AS意识,可以想象会做出多慢的东东,那不是龙,那是虫.
然后,分析下它的结构,要接龙,就要有头有尾,所以,很容易把成语做成一个结构体,
那就是头int16+身(随便)+尾int16.
然后,我们再说,龙这个东东:
龙者,路径也,图之所存也,图常见有两种表示法,邻接矩阵和指针结构(一般用面向对象OO的办法实现指针结构),如何选择?
要是预先处理,1万乘一万的Bool邻接矩阵,预先处理就要花费O(n*n)时间,而且超级的离散,所以不推荐这样的做法.
然后我们考虑用对象,有二叉,Hash,链表等供选择.我们要存储几样东西:
0,节点,就是成语,上面已经说过了那结构体,作为图里的V
1,关系,就是谁能连谁,也就是边E.
2,用来反复搜索的变长路径,P.
对E,P和几种结构体分别研究之:
二叉的插入和查找具有O(log n)特性,还可以排序O( n* log n),但是我们不需要它,我们要更快的.
Hash的查找是最快的,O(1),不过他的致命问题是Key不能重复,那么,我们只存储"头"好了,那就意味着每个Hash元素里蜗居着好几个成语,在这里边再套一个以成语本身为Key的hash好了.
就形成了Hash<头,Hash<成语,其他信息>>这样的结构了.OK,完美,悟空,Let's go 天竺.
P路径的问题,P一般是多数图类问题的答案,我有一种感觉,一个问题,如果你能把答案的结构描述出来,问题基本就有一半的答案了,这个答案要适合记录每次递归最少信息.
那么这个龙的问题就是,每次还可以查找是否出现了环,
最快查找重复V,用下半身去想,答案都是Hash,所以龙本身还是个Hash.
有了路径的描述,就还需要一个集合来存储所有路径,要不你咋知道哪条龙最长呢?
所有路径,就用变长数组,LinkList<P>来存储好了,寻找前K大的问题都可以在O( n)内解决,因为我们只需要查找最长的,所以当然是O( n),不需要排序.可以使用一个栈结构(我们叫它大头栈吧),最开始压入一个,然后每压入一个,比较头大小,比头大加头,否则加到尾巴上或者随便加到什么地方.
以上是结构体的问题,那么下面是算法的问题.
成语接龙当然是深度优先拉,深度优先的解释看我13楼的论断.
这里我还想说一下,成语接龙,其实还是可以多线程并行异步的,不过,要注意好那些结构是线程公用的那些是私用的.线程,给数据结构带来新的思考.
------解决方案--------------------
------解决方案--------------------
广搜是队列
深搜是堆栈（一般是递归的形式）
A*是优先队列
你那个1，2，3，4，5那个图还是深搜方便也就是用递归 其实就是回溯法
path: nodes[]
viod Search(Node n)
{
if n is target node
print path
for every adjacent node j
{
path.push(j);
Search(j);
path.pop();
}
}
大概就是这样的
------解决方案--------------------
问题1：
最近一直在弄图, 学着学着就发现疑问慢慢变多,大家看一下耳熟能详的深搜和广搜基础:
广搜: 如果从A到B存在路径，则广搜一定能找到从A到B的一条最短路径, 这是毋庸置疑的.....
让我理解这个应用,就好像有向图的传递封包一样,就是找到一条从A到B的最短路径(边最少).
深搜: 如果有A到B的路径,那么深搜能找出所有从A到B的路径,这应该是深搜的特点吧.....
大家我的理解是否正确,不正确请纠正,不全面请补充,有更深的理解或实战经验请分享,谢谢啦..
------------------------------------------------------------
问题2：
三层循环过程中,如果已经判定:
dist i,j = dist i,k + dist k,j ,那么parent[i][j]=parent[k][j],这是算法导论书上证明的,没错吧...
那么算法运行完成后，我想打印i到j的最短路径，这样递归对不对:
print(i,j)
{
if(i==j)
{output i;return;}
else
{print(i,parent[i][j]);output j;}
}
------解决方案--------------------
已知点集合 V={v1,v2,v3...vn}通过边连接起来
深度优先模型：
void Find1(v)
{
while(广度++)
{
Find1(新找到的点);//递归
}
}
可以看出他先把某一分支的第一分支一直搜到底，再搜第2分支的第一。。。。
广度优先模型：
声明全局点集合 R={r0}初始为出发节点。
void Find2(r)
{
while(广度++)
{
R.添加(新找到的点);
}
R.移除(旧的点);
while(新广度++)
{
Find2(r);//递归
}
}
以下边图为例：
1
/ \
2 3
/ \ |\
4 5 6 7
深度优先的执行顺序是：
1245367
广度优先是：
1234567
深度优先一般适合查找最长路径。成语接龙例子就是深度优先.
广度优先一般适合查找最短路径或者找到就退出，比较常用。
成语接龙的思路是:
0,分析全部成语,把头尾汉字用Unicode转成数字,再减去short.Maxvalue使其分布在short范围内,以节省内存.如果用string是比较废内存的.
1,利用泛型容器Dictionary查找Key速度是O(1)的哈希散列特点,建立两个字典,一个是全部成语,一个是头索引的多个成语.
2,输入一个成语后点按钮,把尾节点作为头,深度优先搜索.(排除环,检测有环复杂度O(1))
3,每一分钟检查一下是否有更长的龙出现.
代码以前公布过,现在没空间了,可以很快找出3000以上无环的成语长龙.
------解决方案--------------------
我们讨论一下,做一个成语接龙,需要多少算法和数据结构(AS)的知识?
首先,我要着重说一点,学习AS,要从大欧记法开始O(),这个用东北话来说,就是"必须的".
然后,我们先说,成语这个东东:
先,是数量上10000多个成语,不仅让人惊叹,老祖宗留下这个东西,太TMD的适合咱们学习和娱乐了,正好可以考验几乎全面的AS知识和技能,没AS意识,可以想象会做出多慢的东东,那不是龙,那是虫.
然后,分析下它的结构,要接龙,就要有头有尾,所以,很容易把成语做成一个结构体,
那就是头int16+身(随便)+尾int16.
然后,我们再说,龙这个东东:
龙者,路径也,图之所存也,图常见有两种表示法,邻接矩阵和指针结构(一般用面向对象OO的办法实现指针结构),如何选择?
要是预先处理,1万乘一万的Bool邻接矩阵,预先处理就要花费O(n*n)时间,而且超级的离散,所以不推荐这样的做法.
然后我们考虑用对象,有二叉,Hash,链表等供选择.我们要存储几样东西:
0,节点,就是成语,上面已经说过了那结构体,作为图里的V
1,关系,就是谁能连谁,也就是边E.
2,用来反复搜索的变长路径,P.
对E,P和几种结构体分别研究之:
二叉的插入和查找具有O(log n)特性,还可以排序O( n* log n),但是我们不需要它,我们要更快的.
Hash的查找是最快的,O(1),不过他的致命问题是Key不能重复,那么,我们只存储"头"好了,那就意味着每个Hash元素里蜗居着好几个成语,在这里边再套一个以成语本身为Key的hash好了.
就形成了Hash<头,Hash<成语,其他信息>>这样的结构了.OK,完美,悟空,Let's go 天竺.
P路径的问题,P一般是多数图类问题的答案,我有一种感觉,一个问题,如果你能把答案的结构描述出来,问题基本就有一半的答案了,这个答案要适合记录每次递归最少信息.
那么这个龙的问题就是,每次还可以查找是否出现了环,
最快查找重复V,用下半身去想,答案都是Hash,所以龙本身还是个Hash.
有了路径的描述,就还需要一个集合来存储所有路径,要不你咋知道哪条龙最长呢?
所有路径,就用变长数组,LinkList<P>来存储好了,寻找前K大的问题都可以在O( n)内解决,因为我们只需要查找最长的,所以当然是O( n),不需要排序.可以使用一个栈结构(我们叫它大头栈吧),最开始压入一个,然后每压入一个,比较头大小,比头大加头,否则加到尾巴上或者随便加到什么地方.
以上是结构体的问题,那么下面是算法的问题.
成语接龙当然是深度优先拉,深度优先的解释看我13楼的论断.
这里我还想说一下,成语接龙,其实还是可以多线程并行异步的,不过,要注意好那些结构是线程公用的那些是私用的.线程,给数据结构带来新的思考.
------解决方案--------------------
------解决方案--------------------
广搜是队列
深搜是堆栈（一般是递归的形式）
A*是优先队列
你那个1，2，3，4，5那个图还是深搜方便也就是用递归 其实就是回溯法
path: nodes[]
viod Search(Node n)
{
if n is target node
print path
for every adjacent node j
{
path.push(j);
Search(j);
path.pop();
}
}
大概就是这样的
------解决方案--------------------