一个求最短总路径的问题

〇〇

笛卡尔积太大了
pop=# select to_id,count(*)cnt from p group by to_id;
to_id | cnt
-------+-----
    34 |  75
   125 |  13
     1 | 541
   145 |  13
    23 |  75

newkid

这种暴力法也就只能玩玩小数据，认真你就输了。

jihuyao

Here is my question for group trip with Dijkstra algorithm.  Consider 2 people starts at point 1234 and ends at 1 and 4.  How to choose the first step, given D(234)<D(123)<D(124)<D(134)<...<... (other possible direct connecting points)?  If one takes D(234) and one D(123) separately the total is D(234)+D(123)=D1.  If both take D(134) the total is D(134) (free share).  Now if D(234)+D(123) < D(134), how to choose for the very first step, branching or sharing?  If branching, in following steps, both can no longer share paths (implying possible larger distance in fatal).  If sharing in the first step, it is possible to keep sharing to the point 14 and then branching to point 1 and point 4 separately (implying the total distance may be much shortened due to the following shared steps).  So my question is, in order to take greedy choice in the first step as in the Dijkstra algorithm, wether or not we give up the choice of sharing path?  This is all about the first step (nothing else).

〇〇

https://zhuanlan.zhihu.com/p/102709464 感觉是VRP

newkid

jihuyao 发表于 2021-8-10 02:45
Here is my question for group trip with Dijkstra algorithm.  Consider 2 people starts at point 1234  ...

必须穷尽所有分支，没有办法。

jihuyao

The simplest one I caught from the link is one walks through all points and comes back to starting point, which is different from group trip involving share factor.  If constraints can be applied, as in current topic such that Dx+Dy>Dz (always true for the same level stops), the shared stop will be preferred in the very first step.  The we have to deal with the second step as in the algorithm (have not thought about the 2nd step so far, maybe not so hard as being scared).  Forget how complicated the real problems may be.  Now something in common reminds me of the N Card problem.  One is the problem itself how to place all cards back in sequence together efficiently.  My feel is that we can still take the greedy choice (this has to consider both cost and potential benefit) for each step (even for group sharing factor involved).  The second common is the N Card problem is much like the opposite problem of group trip, after 2 people reach their end points 1 and 4, how they come back to the start point 1234 efficiently, that is, one person waits somewhere for the other person in order to share path to come back together to the start point (compare to the 5 cards problem, can not always perform in the same way such as 4 to 5, 3 to 4/5, 2 to 3/4/5, and finally 1 to 2/3/4/5, individually).  Anyway, cooperative greedy choice for each step in group trip is an interesting attempt.  Compared to all path links, for each step one only considers all the direct next paths to evaluate the whole group cost and benefits).  Particularly for larger N levels group trip, this will avoid all unnecessary cross joins as in sql for only one step.

〇〇

newkid 发表于 2021-8-13 02:41
必须穷尽所有分支，没有办法。

如果先求出一个较短的5个人的总距离，在拼接过程中能把比它大的过滤掉

newkid

我前面说的那个方法，第一步就是求出所有点到点的最短距离，以那个作为基准。如果发现更短路径就替换这个基准。如果有些点之间不可达，剪起来就更快了。但是人员的所有分组方法还是都得尝试。

〇〇

https://m.mysmth.net/article/ITExpress/2297371 这个有点厉害

yulihua49

这个让sql做，勉为其难了吧。
还是数据库存数据，用编程语言做好一些。