[数列] [算法]金字塔最短路径-小六的作业之一

realnumber

图片是3层金字塔俯视图.

2019-2-13 16:42

现在泽泽在金字塔最底层的左上角。他可以向前后左右或走到楼上去，但必须花费一点时间。一旦走到楼上后楼下的门就会关闭，泽泽不能回下去了，因此泽泽格外小心。幸运的是，金字塔很巧妙。在金字塔里有一些暗道，可以从某点直接通向某点，而不用再走最平常的路线，也是只能上不能下。泽泽知道这些暗道在哪里，而且知道走到每个地方的所花费的时间。
现在你要做的就是算出泽泽走到金字塔顶端所花最少的时间。
注意：
第n层第i行第j列我们表示成n，i，j。当n>=2时，n，i，j可以由4个位置走来（不包括暗道）。如3，1，1可以从2，1，1或2，1，2或2，2，1或2，2，2走来。

    如图所示，一座大小为3的金字塔的俯视图就是这个样子的。从A（2，1，1）、B（2，1，2）、C（2，2，1）、D（2，2，2）都可以走到E（3，1，1）。其他位置依次类推。

输入格式
第1行为2个整数n，m。n表示金字塔的底部边长以及高，m表示有多少暗道。
接下来有n张正方形的图，每张图用一个回车隔开，表示从最底层到最高层的每个位置所花费的时间。保证上面的图的边长比下面图的多1。（如样例，这座大小为4的金字塔第1层是$4\times4$的，第2层是$3\times3$，第3层是$2\times2$，第4层是$1\times1$.）
接下来的m行，每行7个整数$a_{i1}，b_{i1}，c_{i1}，a_{i2}，b_{i2}，c_{i2}，p_i$。表示 第$a_{i1}$层的第$b_{i1}$行第$c_{i1}$列 到 第$a_{i2}$层的第$b_{i2}$行第$c_{i2}$列 之间有一条时间为$p_i$的暗道。保证$a_{i1}<a_{i2}$。

输出格式
一个整数，即泽泽走到金字塔顶端的最短时间。

样例输入
4 2

4 1 5 2  4  5 10 12  
4 3 4 7  8  8 12 19  
1 9 2 8  9 17 14 22  
0 3 5 1  9 20 19 20
  

2 8 5
9 3 9
1 1 8

7 4
5 2

42

1 1 2 2 3 1 1
1 3 2 2 2 1 7

样例输出
52

题目提示
流程：
1        泽泽一开始在1，1，1的位置，总时间为0+4=4。
2        从1，1，1走到1，1，2，总时间为4+1=5。
3        走暗道到了2，3，1，总时间为5+1+1=7。
4        从2，3，1走到2，3，2，总时间为7+1=8。
5        再上楼到了3，2，2，总时间为8+2=10。
6        再上楼到了4，1，1，总时间为10+42=52。

数据范围
对于50%的数据，$n\le 5$
对于100%的数据，$n\le 100，m\le 50$，每格的暗道总数不超过10个。

业余的业余

状态空间搜索当然可以，但估计满足不了时间限制。觉得是一个动态规划问题，虽然还没太看懂题目。

kuing

吓死宝宝了，小六……我看了一半题目就放弃了……

realnumber

回复 3# kuing


    当然吓人了，是学校四题里最后一题(浙江不是最吓人的，据说有些地区小三就开始学编程了，感觉对学数学帮助也很大)
这么说吧，比如就平面方格$n\times n$，每个格子有个非负数，从某格A到某格B找一条路（只能上下左右走），要求经过的格子内的数字和最小。现在1楼是个金字塔型且有暗道（可能的捷径），因为错开的缘故从$k\times k$的某格到上层$(k-1)\times (k-1)$的某格有4种可能以及暗道.我也不知道答案，等过一段时间说下我的想法，估计是2楼说的搜索有些类似.

业余的业余

搜一下 单源最短路径 图的最小代价生成树 Dijkstra 算法 三者之一。

印象有点模糊了。应该是这个方向。那样就是个贪心算法问题了。

realnumber

回复 5# 业余的业余
也在网络上搜索到过这个名称，基本都不知道意思，没学过算法。
我的想法是这样，就是模仿地面被水流浸过的过程，把浸到与没浸到的边界记录下来。这样描述不晓得有没表达清楚，开个数组A,记录从起点出发再走一格的三个距离值以及位置（有一条暗道的话，也就再多个值），并按小到大排序，哪个最小从哪个继续，新的若干个值放入数组A（快速排序）,继续这个操作，直至结束。水流边界碰到金字塔每一层边界或水流自己的边界时，就不是边界了，即不是A中的一个值了。最多$1^2+2^2+...+100^2$每个格子都走到，且只走一次，猜测时间不会超吧.
      又这样有没意义：直接计算起点到塔顶的一条棱经过的格子的和t，大概在进行到一定规模时与t比较，大于t直接排除.

业余的业余

回复  业余的业余
也在网络上搜索到过这个名称，基本都不知道意思，没学过算法。
我的想法是这样，就是模 ...
realnumber 发表于 2019-2-14 09:06

对了。我没细看你的过程，但被水沁润的过程，这个关键词说到点子上了，这就是单源最短路径额Dijkstra算法思路的核心。

本质上就是在不断的扩大同心圆(朋友圈)，以包含更多的节点(Node), 这里是金字塔的方块。最初的时候，圆里只有圆心，就是初始节点(1,1,1), 然后从所有节点中找出到这点距离最近的，加入这个朋友圈，接着，再在剩下的节点中找通过朋友圈中的任何一点，到圆心，即初始节点最近的节点，加入朋友圈。以此类推，直到目标节点，即金字塔的最顶块进入了朋友权，算法结束，得到最优值。

思路虽然简单，实现需要极巧。要选取和你要进行的操作最适合的数据结构。但是，即使类似冒泡法的最笨的办法，也保证了算法具有多项式时间复杂度。如果用回溯法一类的状态空间搜索，你得到的应该是类似指数复杂度的。

动态规划应该可以，但既然贪心算法(Dijkastra) 可以，就不用管其它的路了。

敬畏数学

此题不太会。

realnumber

搜索办法在50层（没暗道）用时约0.1秒，100层时约6秒，会超时（一般限制是2秒内，也不排除程序没编好）.
高手说下动态规划大概的思路，不需要编程，因为c++也不太懂.

游客

实际的 金字塔到底是3层还是4层的 ？“样例“是什么意思？

realnumber

回复 10# 游客

图是3层的，
样例就是举个具体的数据，即举个例子，本题给的样例是4层的.
实际规模最大是100层.

业余的业余

回复 9# realnumber


做到 100 层 6秒， 应该算法没大问题，前次听你说水的沁润，是对路的。这个问题用贪心算法应该效率最好。我估计问题出在算法的实现上。

这个算法应该是 $O(n^2)$， $100$ 层是 $338,350$ 的节点，开一个
$338350\times 338350$ 的二维数组存节点间的代价矩阵。

再开两个 $338350$ 的数组，一个记录算法执行至今相应节点到初始节点的最短路径，无显明路径的用最大整数或 $-1$ 代表，另一个记录对应当前最短路径时的前驱节点，然后用一个双层循环，完成沁润过程。

业余的业余

回复 12# 业余的业余

也可能这个问题的特殊性有更快的算法。有样本数据吗，发一个我试试。

realnumber

回复 13# 业余的业余


    没有，测试的数据是小朋友自己编制的数据，就看他程序生成，不晓得怎么做。

我的还有个不太成熟设想是用填表法（但小朋友说就6楼一样），但不好估计速度，怎么实现也是个问题，因为编程相关问题其实菜鸟一枚.