有哪些「上帝算法」？ 第1页

update（20150323）：感谢

的指正，Dij算法不是指数级的复杂度，是二次幂多项式级的。这个地方是我记混淆了。对不起各位看官了～以及

真是人如其名！

不请自来。

答题资格：gis相关开发人员。

我想目前的答案对题主的批评其实是缺少思考的结果，其实题主的上帝算法确实很上帝的，这个算法的时间复杂度确实是常数级的，问题在于目前的计算机没有办法实现这个算法。

请听我细细道来。

五年前跳入GIS这个坑，如今准备出坑了，这五年多的时间里二维空间的一切都让我感到奇妙，总是不时地去思考为什么一涉及到二维的算法，复杂度就恐怖得一比。dijkstra这种指数级复杂度（错误，此处应为O（n^2）感谢 @Deep Reader 指正！）的算法，还得靠A*去减少复杂度，勉强得到近似解。当初看到A*的时候，简直惊为天人，并在自己的代码里模仿A*解决了一个大问题，如今想起来也是颇有感慨。说远了，咱么扯回来哈，我也一直在想为什么空间关系计算机处理起来这么复杂呢？刚开始我得出的答案是：计算机的原生数据结构是一维的，所有高维数据都是通过一维的模拟来实现的。这当然是一个解释，但我觉得还不够，却又想不通到底哪里还不够。直到最近又一次翻开《java设计模式》，当我看到调停者模式的时候，突然恍然大悟！原因就是——计算机的原生数据结构不支持关系的表达！

具体的内容就不复述了，可以参加《Java设计模式》的调停者模式一节相关内容。

在这个题目中，之所以人来扯一扯就可以达到O（1），而计算机直奔指数级扬长而去，就是因为原生数据结构不支持关系。

详细说说。

一个二维的无向权值图，一般我们会主要关注它的拓扑关系，在数据结构中，这种拓扑关系可以简单地用一个对象引用+权值来表示。在题主的算法中，还引入了欧拉几何的二维空间关系，此算法利用空间关系改变时，拓扑关系不变的特性来达到找出最优路径的目的。

然而，在计算机处理时，空间关系怎么表达的？（x，y）数值对，注意，在这种表达中，空间关系来源于计算，而非原生的数据机构。换句话说，当两个对象的空间关系发生改变时，我们必须要通过一次“计算”来获得二者当前的空间关系，而现实中，并不需要，因为关系是直接存在于物理世界的原生属性中。

因此，“扯不动”这个关系，对于计算机而言，是非原生的，也就说，计算机原生的数据结构无法表达“扯不动”这个关系，因此，你必须在扯的过程中，不断计算，并加入代码来人工判断是否还能扯得动。然后，你还得计算到底哪一条路径是“绷直”了的，因为“绷直”其实本质上也是一种关系的体现。

我们做个特殊处理，把待求的两个点a，b放在水平轴x上，横向扯动，设a在b的左边。于是，a的x值减小，而同时b的x值开始增大。问题在于，实际中，当a，b开始移动时，由于物理世界原生的关系，你无需去控制其他球和线，它们会“自动”地开始变化，最终达到绷直时的状态。但计算机不行，这个变化的“关系”必须通过你的计算去达到，而计算的次数显然与一共有多少个球相关，最终也会变成指数级（错误，O（n^2））的时间复杂度。

总结起来，其实题主这个算法，对于计算机而言，确实是“上帝算法”了，原因很简单：你做了对于计算机而言，是它的上帝才能做的事情——你的世界里“关系”是原生的。

如果，我是说如果，有一天，计算机内的数据结构原生地支持了关系···我擦，我再跳GIS坑来得及吗？

以上答案是个人思考的结果，不可避免会有不严谨甚至错误的地方。望各位大牛斧正，因为我对空间关系的好奇是无尽的。

最后，考虑到工作关系，虽然可能是废话，但还是说一句：

本答案未经作者允许，禁止转载。