急求一个算法思路问题，请大虾们指点啊，谢谢
问题是这样子滴：有一批人沿着几条最短路消散，从起点（O）到各终点（D),O-D分布已知，人流是连续的，行人的速度都是一样的，最短路上每条路段的通行能力C和路段的权（即行驶时间）W均已知，行人从起点（O)时的流量为q，t时间后起点的人都散完，问经过多长时间T后，所有的人都到达终点，且在T时间内，任一时刻时各路段的流量是多少。
注：1，各最短路是可能相交甚至共用同一条或几条路段（这就是问题的难处之一）
2，当行人的流量大于路段通行能力C时，只能以C流量通过，且发生堵塞，假设堵塞点均在各节点，对路段上的人流不受影响（这也是问题的难点之一，就是要考虑因堵塞而逗留的人流什么时候才能到自己的终点，而且堵塞的人还要分各自的终点不一样
希望大家指点指点啊
问题点数：100、回复次数：22Top
1 楼mickyx（星云飘渺）回复于 2006-05-04 09:05:03 得分 0
曾经想过一个算法如下：
Ⅰ算法思想：
通过研究不行网络路段的流量随时间的变化，得到整个网络流量的变化。
Ⅱ假设：
a路段上的步行速度个体差异忽略；b各路段通行能力已知，设为Cij；c不考虑对向人流间的干扰影响；d步行OD已知（由方式划分预测得到）；
Ⅲ算法步骤：
a建立步行网络；b找出每个OD对之间的最短路径；c给每个路段的流量赋予初值（0）；d按指定的划分时段计算，计算各路段在各时间段流量的情况，直至各迄点流进量均为OD给定值。
Ⅳ所用相关变量：
设单位时间段为t0，节点集为Ip（可用单向链表给出），起点集为Rm，终点集为Sn，搜索RS间的所有最短路径，共m×n条（实现算法用邻接矩阵）。
⑴如果i非源点根据最短路径集，设任一节点i的下一节点为d，与之对应的i的前一层节点u∈U（可能不止一个）设在h时段由u流入i的流量为quih，则欲流入id路段流量Qidh＝∑qui×h’（其中u∈U,h’＝h－lui÷vt0）。①if Qidh＋δid≤Cid（δid为上一时段i节点未流入d节点而滞留在i节点的行人流量），则实际流入id路段流量qidh＝Qidh+δid,δid=0;②if Qidh＋δid＞Cid，则实际流入id路段流量qidh＝Cid，δid＝Qidh＋δid－Cid；
⑵如果i是源点，则实际流入id路段流量qidh＝起点流量。
但是，在考虑δid如果在下一个路段再分流，就没法实现了。
Top
2 楼mickyx（星云飘渺）回复于 2006-05-04 09:19:27 得分 0
后来想过一个算法，就是将人流看成是N个队列，每个队列就是一条最短路上的人流，各队列均是由链表组成，每个节点包括流量q和队长t
当遇到各队列间不相互干扰，即各最短路没有共同的路段时，只要比较队列上的q和路段通行能力的大小，如果q<＝c时，队列不变；如果q>=c时，队列流量q＝c，队长t＝q×t/c。最后T=max（所有队长的和＋最短路上路权的和）
但当最短路有共同路段时，情况就好复杂。Top
3 楼mickyx（星云飘渺）回复于 2006-05-04 13:20:03 得分 0
没人顶啊 ？Top
4 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-05-04 13:26:20 得分 10
我来小顶。。。。。
暂时没有学到。。。。。Top
5 楼mickyx（星云飘渺）回复于 2006-05-04 14:20:00 得分 0
呵呵，谢谢楼上的，今天大虾们都休息去啦？Top
6 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-05-04 16:11:42 得分 10
到了晚上的时候都出来了。。。。。Top
7 楼mickyx（星云飘渺）回复于 2006-05-04 17:03:24 得分 0
哦，好哦，那我等到晚上哈^_^Top
8 楼mickyx（星云飘渺）回复于 2006-05-04 22:43:34 得分 0
哇哇。。。没人帮忙啊。。。。。。Top
9 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-05-04 23:26:00 得分 10
我出来了，可惜，我不系呀。。。Top
10 楼UPCC（杂食动物）回复于 2006-05-05 00:58:08 得分 10
留给名先... ...这个比较有意思Top
11 楼mickyx（星云飘渺）回复于 2006-05-05 07:38:05 得分 0
楼上的有空帮忙想想哦Top
12 楼yuanchuang（元创）回复于 2006-05-05 16:43:49 得分 10
这个问题是管理系统模拟上讲的问题吧？
可惜我一节课没上……Top
13 楼dch4890164（巴拉克）回复于 2006-05-05 17:15:58 得分 20
既然是有流量，是否能建立流量模型，概率模型也可以
之后判断阻塞的可能性
之后是否可以用DJKSAR方法或者中国邮路问题解决呢？
不是很确信
感觉很难
估计次优就可以了。
用蚂蚁算法或许也可行。Top
14 楼province_（雍昊）回复于 2006-05-05 17:19:23 得分 0
难题，留个脚印先Top
15 楼mickyx（星云飘渺）回复于 2006-05-05 22:11:32 得分 0
dch4890164(跳梁小丑)
概率模型（一般是泊松分布）是对一般的人流讲的，这个是连续的人流，不需要考虑那么复杂的，中国邮路问题和DJKSAR是啥子啊？还有蚂蚁算法。。。不太懂耶不过感觉不太针对
我后来考虑了一下
是不是可以先不考虑δid在分流后的去向，而是针对每个分流的节点在向各个路段的时候都是一定比例的分过去的，比如1点可以向2，3，4点分，其中向2的流量占50％，向3的流量占20％，向4的流量占30％，一直这样固定不变考虑呢Top
16 楼mickyx（星云飘渺）回复于 2006-05-05 22:14:17 得分 0
但感觉就算这样编程方面还是很繁的，首先要遍历所有的节点和路段，查处哪些是共有的，而且被哪些路段共有，再考虑其中是否会堵塞以及分流的分配率的问题，晕哦，烦得一塌^_^Top
17 楼biaolao（）回复于 2006-05-06 00:33:14 得分 10
晕的厉害Top
18 楼cihw2005（）回复于 2006-05-06 09:06:56 得分 10
期待高人！Top
19 楼mickyx（星云飘渺）回复于 2006-05-06 09:32:08 得分 0
呵呵，期待高人！Top
20 楼aniude（重返荣耀）回复于 2006-05-07 00:53:32 得分 5
连题目都理解不了！Top
21 楼yjdxgah2005（我为你狂）回复于 2006-05-07 13:26:25 得分 5
对我来说是高难！Top
22 楼mickyx（星云飘渺）回复于 2006-05-09 16:43:34 得分 0
aniude(重返荣耀)
是不是我表达不清楚啊，不过偶确实从小语文不好滴，见谅了啊Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
