一个求最短总路径的问题

〇〇 · 发表于 2021-8-8 20:36

笛卡尔积太大了
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 · 发表于 2021-8-9 08:24

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

jihuyao · 发表于 2021-8-10 02:45

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).

〇〇 · 发表于 2021-8-12 12:48

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

newkid · 发表于 2021-8-13 02:41

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

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

jihuyao · 发表于 2021-8-13 02:59

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.