作者yauhh (哟)
看板Prob_Solve
标题Re: [请益] 街道型的Two Shortest Path
时间Sun May 9 02:28:44 2010
※ 引述《MrGG (头有点痛)》之铭言：
: ╔═══╦═══╦═══╦═Ｄ═╗
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ╠═══╬═══╬═══╬═══╣
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ╠═══╬═══╬═══╬═══╣
: ║ ║ ║ ║ ║
: ║ ○ ║ ║ ║
: ║ ║ ║ ║ ║
: ╠Ｓ→→→═○═╬═══╬═══╣
: ║ ║ ║ ║ ║
: ║ Ｘ ║ ║ ║
: ║ ║ ║ ║ ║
: ╚═══╩═══╩═══╩═══╝
: 假设现在由S走到D，
: 当在第一个路口的时候，我可以选择○两条路径行走(最短路径)
: 因此，此时会有两种情境，暂定Case1和Case2
: 如果走Ｘ的话，则会绕远路
这没有可烦恼的. 路网表达为图就是
.----.----.----.-.--.
| | | | D |
.----.----.----.----.
| | | | |
.----.----.----.----.
| | | | |
.-.--.----.----.----.
| S | | | |
.----.----.----.----.
固定路段权重都一样, S与D局部路段用内插法分配权重,
然後用一般的选路法,选就对了.
绕路这种事,在选路法中会自动避开.
而如果你想的是人的选择,就是另外一个比较复杂的问题了.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.209.141
1F：推 MrGG:考虑的就是人的选择...，所以必须在路口提供<=2条最短路径 05/09 02:32
2F：→ MrGG:给人选择... 05/09 02:32
3F：→ yauhh:我猜你可能也想要将路线限制,例如何处禁止左转,加入考虑范围 05/09 02:43
4F：→ yauhh:大概就路线,匣道限制限定的路网先定好,然後把交通情况定为 05/09 02:45
5F：→ yauhh:像权重那样的动态影响因素,这时才来看人的决策模型... 05/09 02:46
6F：推 MrGG:目前还没想到路线限制，想看看能不能算出<=2条最短路线 05/09 02:47
7F：推 MrGG:当初的想法是，因为路线在规划时，假设使用GPS.. 05/09 02:49
8F：→ yauhh:但现在看起来并没有明确定义路网的情况下,你说要<=2条路径, 05/09 02:49
9F：→ MrGG:GPS会推出一条最短路径，那麽如果遇到塞车或是前方车祸的情形 05/09 02:49
10F：→ yauhh:这个方法不对喔 05/09 02:49
11F：→ MrGG:会在推出另外一条最短路径.. 05/09 02:50
12F：→ yauhh:那你就要定义这种影响因素化为参数,如何传播并影响路线权重, 05/09 02:51
13F：→ yauhh:才做得下去. 05/09 02:51
14F：推 MrGG:但是像塞车这类情况必须由人判断，如果没塞车，也是有可能换 05/09 02:56
15F：→ MrGG:路线，所以目前只有想说如何在每个路口提供一条最短路径 05/09 02:57
16F：→ yauhh:当你要说远近的时候,只能看路线配置及路线权重,所以像前面 05/09 02:59
17F：→ yauhh:你说"不能绕远路",显然是普通选路法已经能解决的事情,这就 05/09 03:00
18F：→ yauhh:显得你的问题不明确. 05/09 03:00
19F：→ yauhh:嗯..人为判断塞车的意思,就是...在眼前看到塞车时,就按一下 05/09 03:04
20F：→ yauhh:GPS,叫它重算目前位置到目的地的路径... 05/09 03:05
21F：推 MrGG:但是，GPS重新规划需要有一段时间，所以我必须在每个路口先 05/09 03:10
22F：→ MrGG:估计出可能的最短路径 05/09 03:10
23F：推 PsMonkey:纯乱骂：你这样前提假设根本没说清楚... [摊手] 05/09 06:28
24F：→ yauhh:如果你要事先估好,这叫预测.而预测的可怕之处是难以衡量 05/09 10:37
25F：→ yauhh:模拟系统是否符合真实系统的行为,很难找理由解释清楚. 05/09 10:38
26F：→ yauhh:在此不是喜欢否定你而已,而是告知一些你的研究可能会遭遇的 05/09 10:40
27F：推 MrGG:所以，我的系统是希望S走到D的时候，能够行走最短路径.. 05/09 10:40
28F：→ yauhh:障碍,也许你在前期是比较不会先想到. 05/09 10:40
29F：推 MrGG:当初的构想是，因为人们在都市使用GPS导航，但是GPS的重新 05/09 10:42
30F：→ MrGG:定位需要一段时间，然後封包在传递时，尽可能的不要中断 05/09 10:43
31F：→ MrGG:所以才想要找出另一条可能的最短路径，防止驾驶临时变换路线 05/09 10:44
32F：→ MrGG:所以当GPS导航出一条路线时，在每个路口，需要找出另一条可能 05/09 10:45
33F：→ MrGG:的最短路线，以防止驾驶者临时改变路线 05/09 10:45
34F：→ MrGG:然而找过一些资料，在道路的拓墣上几乎道路长短皆不同 05/09 10:48
35F：→ MrGG:因此很容易规划出最短路线，然而我想到的是使用田字型来减少 05/09 10:48
36F：→ MrGG:未来模拟时的复杂度，但是 衍伸出的就是每条路的长度皆相同 05/09 10:49
37F：→ MrGG:不知道该怎麽去算出最短路线 05/09 10:49
38F：推 stimim:田字形的只要一直朝目标走就是最短了不是吗? 05/09 11:01
39F：→ stimim:如果 D-S = (a,b) 在走的时候就要让 |a|,|b| 减少 05/09 11:03
40F：→ stimim:因此a>0的时候不能向 -x 方向走，b>0的时候不能向-y方向走 05/09 11:04
41F：→ yauhh:路段长度是天生的权重,照着选路法做一定有答案,当然不只一条 05/09 11:05
42F：→ yauhh:最短的. 05/09 11:05