提示：运费=里程x货物数量
补充:配送车辆可以从任何一个节点出发，不要求回到出发点。
大家可不可以给点思路，我不要源代码。
59 个解决方案
#1
最小生成树
#2
带权最短路径。
#3
to KBthu(景乐)
最小生成树好象不合适阿，这个问题考虑的是要设计一条线路，而不是一个连通图。
to WaterWalker(水上飘)
带权最短路径是怎么个思路？是不是和最小生成树一个概念？
请大家注意的是，这里的权值还和配送车辆上的剩余货物重量有关。而不单单是路径的长度。
最小生成树好象不合适阿，这个问题考虑的是要设计一条线路，而不是一个连通图。
to WaterWalker(水上飘)
带权最短路径是怎么个思路？是不是和最小生成树一个概念？
请大家注意的是，这里的权值还和配送车辆上的剩余货物重量有关。而不单单是路径的长度。
#4
其实都是一样的，权值计算出来即可嘛
#5
权值怎么算？
#6
ft!
题目要求是：设计一个设计配送路线的程序，使总运费最低
而运费=里程x货物数量，算就是了
题目要求是：设计一个设计配送路线的程序，使总运费最低
而运费=里程x货物数量，算就是了
#7
可是每条边的权值确定吗？
不光是里程，还有剩余的货物量了。
你怎么根据权值选最小的边？
不光是里程，还有剩余的货物量了。
你怎么根据权值选最小的边？
#8
即使是权值能算，我怎么算出出发节点？
#9
带权最短路径,权值就是里程*货物量.
因为反正考虑的只是运费.如果你的出发节点不确定的话,多用一个循环就是
了.
不然用旅行商问题,然后用遗传算法来做我想也是可以的.
因为反正考虑的只是运费.如果你的出发节点不确定的话,多用一个循环就是
了.
不然用旅行商问题,然后用遗传算法来做我想也是可以的.
#10
感觉...有点像网络流.最小费用最大流...
#11
好像要穷举了吗
#12
kensta()说的有道理
如果不能确定首节点的话，就只能穷举了。
我现在的想法是先算出一个相对较优的代价，然后再遍历整棵树，用剪枝法。
不知能行吗？
如果不能确定首节点的话，就只能穷举了。
我现在的想法是先算出一个相对较优的代价，然后再遍历整棵树，用剪枝法。
不知能行吗？
#13
to lonk(寂寞低手·小渝)
这是大二的题目，好像不会有很大难度的，但现在把我难道了。
遗传算法是个什么思路？能不能介绍一下？
这是大二的题目，好像不会有很大难度的，但现在把我难道了。
遗传算法是个什么思路？能不能介绍一下？
#14
就是最短路径问题：
程序构思：
首先，你应该把图形建立成加权图性的邻接数组，在申明一个一维数组来纪录已经查找的的数组(Visited)和一个一维数组来用来纪录顶点间距离综合的变化(Distant)
取原来的距离总和于新加入顶点后的距离总和的最小值作为新的距离的总和，
程序构思：
首先，你应该把图形建立成加权图性的邻接数组，在申明一个一维数组来纪录已经查找的的数组(Visited)和一个一维数组来用来纪录顶点间距离综合的变化(Distant)
取原来的距离总和于新加入顶点后的距离总和的最小值作为新的距离的总和，
#15
to zhoukun666()
能够证明吗？
能够证明吗？
#16
to zhoukun666()
这是不是就是Dijkstra算法啊？
这是不是就是Dijkstra算法啊？
#17
up
#18
帮忙up以下！
#19
运费=里程x货物数量
当然是要里程少,而货物数量多!
所以求里程/货物数量,要求最小,用排序,这样可以求出最近的和最远的,达到自己的目的,这需要一个矩阵来表示数组也可以
当然是要里程少,而货物数量多!
所以求里程/货物数量,要求最小,用排序,这样可以求出最近的和最远的,达到自己的目的,这需要一个矩阵来表示数组也可以
#20
to scorpiotianyawei(scorpiotianyawei)
权值算出来后，然后怎么找到最小路径？这里的要求是遍历所有的节点。
权值算出来后，然后怎么找到最小路径？这里的要求是遍历所有的节点。
#21
只能穷举+剪枝了吗？
#22
up
#23
计算出每个点到配送中心的最短路径就可以了，主要是模型是可加性的。
运费=里程x货物数量
也就是说，如果配送中心要送重量为w(a)的东西到a点，同时要送总量为w(b)的东西到b点，那么派一辆车从配送中心直接将w(a)+w(b)的东西先送到a,卸下w(a)的东西，然后继续将剩余的东西送到b的费用同直接使用两辆车，分别将w(a)直接送到a,将w(b)送到b(但是走的路径经过a)的费用是一样的，所以我们没有必要考虑将多个货物一起运送的情况，于是就变成求到达每个商店的最短路径的问题了。
用Dijkstra算法就行了
运费=里程x货物数量
也就是说，如果配送中心要送重量为w(a)的东西到a点，同时要送总量为w(b)的东西到b点，那么派一辆车从配送中心直接将w(a)+w(b)的东西先送到a,卸下w(a)的东西，然后继续将剩余的东西送到b的费用同直接使用两辆车，分别将w(a)直接送到a,将w(b)送到b(但是走的路径经过a)的费用是一样的，所以我们没有必要考虑将多个货物一起运送的情况，于是就变成求到达每个商店的最短路径的问题了。
用Dijkstra算法就行了
#24
计算出每个点到配送中心的最短路径就可以了，主要是模型是可加性的。
运费=里程x货物数量
也就是说，如果配送中心要送重量为w(a)的东西到a点，同时要送总量为w(b)的东西到b点，那么派一辆车从配送中心直接将w(a)+w(b)的东西先送到a,卸下w(a)的东西，然后继续将剩余的东西送到b的费用同直接使用两辆车，分别将w(a)直接送到a,将w(b)送到b(但是走的路径经过a)的费用是一样的，所以我们没有必要考虑将多个货物一起运送的情况，于是就变成求到达每个商店的最短路径的问题了。
用Dijkstra算法就行了
运费=里程x货物数量
也就是说，如果配送中心要送重量为w(a)的东西到a点，同时要送总量为w(b)的东西到b点，那么派一辆车从配送中心直接将w(a)+w(b)的东西先送到a,卸下w(a)的东西，然后继续将剩余的东西送到b的费用同直接使用两辆车，分别将w(a)直接送到a,将w(b)送到b(但是走的路径经过a)的费用是一样的，所以我们没有必要考虑将多个货物一起运送的情况，于是就变成求到达每个商店的最短路径的问题了。
用Dijkstra算法就行了
#25
to mathe()
我这里的问题是要求出一条最短路径，而不是配送中心到每个店最短距离。
还有，配送中心现在不要求独立开来，配送车辆可以从任何一个店出发。
那位大侠有遗传算法的实际应用源代码？
countyroad@sina.com
谢谢！
我这里的问题是要求出一条最短路径，而不是配送中心到每个店最短距离。
还有，配送中心现在不要求独立开来，配送车辆可以从任何一个店出发。
那位大侠有遗传算法的实际应用源代码？
countyroad@sina.com
谢谢！
#26
... 就是中位数啊!.....
>>我这里的问题是要求出一条最短路径，而不是配送中心到每个店最短距离。
你再想想你的化...
还用...什么遗传算法..... -_-
>>我这里的问题是要求出一条最短路径，而不是配送中心到每个店最短距离。
你再想想你的化...
还用...什么遗传算法..... -_-
#27
这也根本和旅行商没关系...
sigh....
sigh....
#28
我来说说啊 ..
能有多大的数据啊!? 能有多严格的时限啊!?
运行一次Floyd求出每个点之间的距离.
然后穷举一圈出发点不久完了么...
靠... Floyd一般六行程序 穷举一圈选最小值 三行代码 ...
... 起码 100个顶点没问题吧1000个顶点也不用两秒啊..
[大稀疏图用johnson取代Floyd]
----
to KBthu(景乐)
最小生成树好象不合适阿，这个问题考虑的是要设计一条线路，而不是一个连通图。
...
=难道这个线路是不连通的?
to WaterWalker(水上飘)
带权最短路径是怎么个思路？是不是和最小生成树一个概念？
请大家注意的是，这里的权值还和配送车辆上的剩余货物重量有关。而不单单是路径的长度。
=sigh....... 乘起来啊!!!!!!!
能有多大的数据啊!? 能有多严格的时限啊!?
运行一次Floyd求出每个点之间的距离.
然后穷举一圈出发点不久完了么...
靠... Floyd一般六行程序 穷举一圈选最小值 三行代码 ...
... 起码 100个顶点没问题吧1000个顶点也不用两秒啊..
[大稀疏图用johnson取代Floyd]
----
to KBthu(景乐)
最小生成树好象不合适阿，这个问题考虑的是要设计一条线路，而不是一个连通图。
...
=难道这个线路是不连通的?
to WaterWalker(水上飘)
带权最短路径是怎么个思路？是不是和最小生成树一个概念？
请大家注意的是，这里的权值还和配送车辆上的剩余货物重量有关。而不单单是路径的长度。
=sigh....... 乘起来啊!!!!!!!
#29
好，我再来说说。
to chenggn(chenggn)
1.穷举是能做，但未免也....
2.我之所以说最小生成树不合适，因为这里有个要求，那就是每个节点只能走一次，否则就不是一条线路了。
3.权值到底是除一下，还是乘起来？即距离/货物数量 or 距离*货物数量？
to chenggn(chenggn)
1.穷举是能做，但未免也....
2.我之所以说最小生成树不合适，因为这里有个要求，那就是每个节点只能走一次，否则就不是一条线路了。
3.权值到底是除一下，还是乘起来？即距离/货物数量 or 距离*货物数量？
#30
我觉得还是除一下有道理。
#31
up
#32
!! 对不起 原来只有!! 10个顶点...!!!
不要看不起穷举
我只是用词不当 穷举又叫搜索 搜索是规则化的遍历
而一些简单的动态规划就是搜索去掉重复的计算而达到的结果
各种图论算法 那一种其本质不是搜索.
请考虑一下我说得吧
由于Floyd求出了每个顶点之间的距离,
然后搜索出发点
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=shortdis[i][j];
}
选取最小的sum即为答案
权值的设定大概你的程序是求最大的 而且这样有浮点误差
我没有仔细考虑你的除法.
没什么说的了.
sorry 但我真的觉得 你说这是大二的题 看来你是大二的学生
还有很多时间用来学习 看来你比较喜欢学习喽
"大家可不可以给点思路，我不要源代码。"
把握时间...
不要看不起穷举
我只是用词不当 穷举又叫搜索 搜索是规则化的遍历
而一些简单的动态规划就是搜索去掉重复的计算而达到的结果
各种图论算法 那一种其本质不是搜索.
请考虑一下我说得吧
由于Floyd求出了每个顶点之间的距离,
然后搜索出发点
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=shortdis[i][j];
}
选取最小的sum即为答案
权值的设定大概你的程序是求最大的 而且这样有浮点误差
我没有仔细考虑你的除法.
没什么说的了.
sorry 但我真的觉得 你说这是大二的题 看来你是大二的学生
还有很多时间用来学习 看来你比较喜欢学习喽
"大家可不可以给点思路，我不要源代码。"
把握时间...
#33
to chenggn(chenggn)
首先说明，我不是大二的学生了，现在是研究生，只是帮别人做而已。
一开始接触这个题目的时候，我就考虑过穷举了，但是一想好象开销很大，然后找了数据结构的书，也没发现合适的算法(数据结构没学好，临时翻翻)，问了几个朋友，由于当时也没考虑仔细，始终得不到好的方法，所以在这里求各位朋友的帮助。
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=shortdis[i][j];
}
这哪里是求从一个点遍历整个图的最短路径。写错了吧？
首先说明，我不是大二的学生了，现在是研究生，只是帮别人做而已。
一开始接触这个题目的时候，我就考虑过穷举了，但是一想好象开销很大，然后找了数据结构的书，也没发现合适的算法(数据结构没学好，临时翻翻)，问了几个朋友，由于当时也没考虑仔细，始终得不到好的方法，所以在这里求各位朋友的帮助。
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=shortdis[i][j];
}
这哪里是求从一个点遍历整个图的最短路径。写错了吧？
#34
求最短路径的算法!!是上面提到的flody!!!
你等等....
你等等....
#35
d[10][10] 距离矩阵
// floyd ------
for (k=0; k<10; k++)
for (i=0; i<10; i++)
for (j=0; j<10; j++)
{
if (d[i][j]<d[i][k]+d[k][j]) // && 有d[i][k], d[k][j]路径存在
{
d[i][j]=d[i][k]+d[k][j];
/*
如果需要求出该路径
p[i][j]=p[k][i];
p[i][j]表示i到j的最短路径中 j的父辈是p[i][j]
全程序最初 初始化时 p[i][j]=i;
*/
}
}
// 以上是floyd算法 通常用于求中等规模稠密图两点间距离 复杂度仍为 O(N^3) ----
// 但复杂度比单纯运行N次Dijkstra的系数要小一些 //
// d[10][10] 现为任意两个点间的最短距离
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=d[i][j]*货物数量[j];
// 如果是除的话 货物越多 权值越小 距离越远 权值越大? 不符合要求 起码权值需要向同一个方向移动
}
// sum[i] 即为以第i个点作为起点的总运费
:) 研究生....
// floyd ------
for (k=0; k<10; k++)
for (i=0; i<10; i++)
for (j=0; j<10; j++)
{
if (d[i][j]<d[i][k]+d[k][j]) // && 有d[i][k], d[k][j]路径存在
{
d[i][j]=d[i][k]+d[k][j];
/*
如果需要求出该路径
p[i][j]=p[k][i];
p[i][j]表示i到j的最短路径中 j的父辈是p[i][j]
全程序最初 初始化时 p[i][j]=i;
*/
}
}
// 以上是floyd算法 通常用于求中等规模稠密图两点间距离 复杂度仍为 O(N^3) ----
// 但复杂度比单纯运行N次Dijkstra的系数要小一些 //
// d[10][10] 现为任意两个点间的最短距离
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=d[i][j]*货物数量[j];
// 如果是除的话 货物越多 权值越小 距离越远 权值越大? 不符合要求 起码权值需要向同一个方向移动
}
// sum[i] 即为以第i个点作为起点的总运费
:) 研究生....
#36
(21:35:18):
1.这个搞配送的到底有几辆车?
如果是一辆开到底 你的错
如果是N辆随便开 你的对
2.这个"线路" 到底长什么样?
如果是一条线到底 你的错
如果是开花成生成树状 你的对
我想自杀...
1.这个搞配送的到底有几辆车?
如果是一辆开到底 你的错
如果是N辆随便开 你的对
2.这个"线路" 到底长什么样?
如果是一条线到底 你的错
如果是开花成生成树状 你的对
我想自杀...
#37
to chenggn(chenggn)
1.从题目来看，应该是一辆车。我的错？why?
2.从题目来看，他的网络是全通图，线路就相当于一笔画，也就是遍历所有的节点，但是每个节点只允许访问一次。
不好意思，麻烦你了！
1.从题目来看，应该是一辆车。我的错？why?
2.从题目来看，他的网络是全通图，线路就相当于一笔画，也就是遍历所有的节点，但是每个节点只允许访问一次。
不好意思，麻烦你了！
#38
几个新条件:
1.一辆车.
2.每个节点只允许访问一次
得出: 是哈密顿通路问题. 标准的方法是... 分枝定界
1.一辆车.
2.每个节点只允许访问一次
得出: 是哈密顿通路问题. 标准的方法是... 分枝定界
#39
上面是别人对我说得... '你'是说我chenggn...
...
5555555~!!@ 我想自杀...
...
5555555~!!@ 我想自杀...
#40
两个都是我的错....
#41
补充
权值计算是我错了。应该和距离*重量成反比。
to chenggn(chenggn)
你也不要泄气，会有办法的，我都没泄气。
to LeeMaRS(小菜虎_水壶的仇人)
分支定界我也想过，但是这里的首节点都没有定出来，那岂不是要都试一下？这不是穷举了？
权值计算是我错了。应该和距离*重量成反比。
to chenggn(chenggn)
你也不要泄气，会有办法的，我都没泄气。
to LeeMaRS(小菜虎_水壶的仇人)
分支定界我也想过，但是这里的首节点都没有定出来，那岂不是要都试一下？这不是穷举了？
#42
才10个节点,用穷举都没问题.
#43
实在不行，也只能穷举了。
#44
呵呵,我再帮你想想办法.
#45
我来说一句话:
只要你的计算是必要的 处理好重复计算的 就是好的
:)
一个图有几个一笔画? :>
只要你的计算是必要的 处理好重复计算的 就是好的
:)
一个图有几个一笔画? :>
#46
谢谢
遗传算法用过吗？
听上去很高深。
遗传算法用过吗？
听上去很高深。
#47
嘻嘻~ 大家的态度都很好嘛 共同进步 共同进步
#48
大家都在线啊？
很高兴和大家聊。
to chenggn(chenggn)
只要能改进，就要比穷举好。
很高兴和大家聊。
to chenggn(chenggn)
只要能改进，就要比穷举好。
#49
没什么了解 印象中是概率算法之类 :)
#50
我这里得到了一份遗传算法关于TSP问题求解的源代码，现在还没看。
几位要吗？
几位要吗？
#1
最小生成树
#2
带权最短路径。
#3
to KBthu(景乐)
最小生成树好象不合适阿，这个问题考虑的是要设计一条线路，而不是一个连通图。
to WaterWalker(水上飘)
带权最短路径是怎么个思路？是不是和最小生成树一个概念？
请大家注意的是，这里的权值还和配送车辆上的剩余货物重量有关。而不单单是路径的长度。
最小生成树好象不合适阿，这个问题考虑的是要设计一条线路，而不是一个连通图。
to WaterWalker(水上飘)
带权最短路径是怎么个思路？是不是和最小生成树一个概念？
请大家注意的是，这里的权值还和配送车辆上的剩余货物重量有关。而不单单是路径的长度。
#4
其实都是一样的，权值计算出来即可嘛
#5
权值怎么算？
#6
ft!
题目要求是：设计一个设计配送路线的程序，使总运费最低
而运费=里程x货物数量，算就是了
题目要求是：设计一个设计配送路线的程序，使总运费最低
而运费=里程x货物数量，算就是了
#7
可是每条边的权值确定吗？
不光是里程，还有剩余的货物量了。
你怎么根据权值选最小的边？
不光是里程，还有剩余的货物量了。
你怎么根据权值选最小的边？
#8
即使是权值能算，我怎么算出出发节点？
#9
带权最短路径,权值就是里程*货物量.
因为反正考虑的只是运费.如果你的出发节点不确定的话,多用一个循环就是
了.
不然用旅行商问题,然后用遗传算法来做我想也是可以的.
因为反正考虑的只是运费.如果你的出发节点不确定的话,多用一个循环就是
了.
不然用旅行商问题,然后用遗传算法来做我想也是可以的.
#10
感觉...有点像网络流.最小费用最大流...
#11
好像要穷举了吗
#12
kensta()说的有道理
如果不能确定首节点的话，就只能穷举了。
我现在的想法是先算出一个相对较优的代价，然后再遍历整棵树，用剪枝法。
不知能行吗？
如果不能确定首节点的话，就只能穷举了。
我现在的想法是先算出一个相对较优的代价，然后再遍历整棵树，用剪枝法。
不知能行吗？
#13
to lonk(寂寞低手·小渝)
这是大二的题目，好像不会有很大难度的，但现在把我难道了。
遗传算法是个什么思路？能不能介绍一下？
这是大二的题目，好像不会有很大难度的，但现在把我难道了。
遗传算法是个什么思路？能不能介绍一下？
#14
就是最短路径问题：
程序构思：
首先，你应该把图形建立成加权图性的邻接数组，在申明一个一维数组来纪录已经查找的的数组(Visited)和一个一维数组来用来纪录顶点间距离综合的变化(Distant)
取原来的距离总和于新加入顶点后的距离总和的最小值作为新的距离的总和，
程序构思：
首先，你应该把图形建立成加权图性的邻接数组，在申明一个一维数组来纪录已经查找的的数组(Visited)和一个一维数组来用来纪录顶点间距离综合的变化(Distant)
取原来的距离总和于新加入顶点后的距离总和的最小值作为新的距离的总和，
#15
to zhoukun666()
能够证明吗？
能够证明吗？
#16
to zhoukun666()
这是不是就是Dijkstra算法啊？
这是不是就是Dijkstra算法啊？
#17
up
#18
帮忙up以下！
#19
运费=里程x货物数量
当然是要里程少,而货物数量多!
所以求里程/货物数量,要求最小,用排序,这样可以求出最近的和最远的,达到自己的目的,这需要一个矩阵来表示数组也可以
当然是要里程少,而货物数量多!
所以求里程/货物数量,要求最小,用排序,这样可以求出最近的和最远的,达到自己的目的,这需要一个矩阵来表示数组也可以
#20
to scorpiotianyawei(scorpiotianyawei)
权值算出来后，然后怎么找到最小路径？这里的要求是遍历所有的节点。
权值算出来后，然后怎么找到最小路径？这里的要求是遍历所有的节点。
#21
只能穷举+剪枝了吗？
#22
up
#23
计算出每个点到配送中心的最短路径就可以了，主要是模型是可加性的。
运费=里程x货物数量
也就是说，如果配送中心要送重量为w(a)的东西到a点，同时要送总量为w(b)的东西到b点，那么派一辆车从配送中心直接将w(a)+w(b)的东西先送到a,卸下w(a)的东西，然后继续将剩余的东西送到b的费用同直接使用两辆车，分别将w(a)直接送到a,将w(b)送到b(但是走的路径经过a)的费用是一样的，所以我们没有必要考虑将多个货物一起运送的情况，于是就变成求到达每个商店的最短路径的问题了。
用Dijkstra算法就行了
运费=里程x货物数量
也就是说，如果配送中心要送重量为w(a)的东西到a点，同时要送总量为w(b)的东西到b点，那么派一辆车从配送中心直接将w(a)+w(b)的东西先送到a,卸下w(a)的东西，然后继续将剩余的东西送到b的费用同直接使用两辆车，分别将w(a)直接送到a,将w(b)送到b(但是走的路径经过a)的费用是一样的，所以我们没有必要考虑将多个货物一起运送的情况，于是就变成求到达每个商店的最短路径的问题了。
用Dijkstra算法就行了
#24
计算出每个点到配送中心的最短路径就可以了，主要是模型是可加性的。
运费=里程x货物数量
也就是说，如果配送中心要送重量为w(a)的东西到a点，同时要送总量为w(b)的东西到b点，那么派一辆车从配送中心直接将w(a)+w(b)的东西先送到a,卸下w(a)的东西，然后继续将剩余的东西送到b的费用同直接使用两辆车，分别将w(a)直接送到a,将w(b)送到b(但是走的路径经过a)的费用是一样的，所以我们没有必要考虑将多个货物一起运送的情况，于是就变成求到达每个商店的最短路径的问题了。
用Dijkstra算法就行了
运费=里程x货物数量
也就是说，如果配送中心要送重量为w(a)的东西到a点，同时要送总量为w(b)的东西到b点，那么派一辆车从配送中心直接将w(a)+w(b)的东西先送到a,卸下w(a)的东西，然后继续将剩余的东西送到b的费用同直接使用两辆车，分别将w(a)直接送到a,将w(b)送到b(但是走的路径经过a)的费用是一样的，所以我们没有必要考虑将多个货物一起运送的情况，于是就变成求到达每个商店的最短路径的问题了。
用Dijkstra算法就行了
#25
to mathe()
我这里的问题是要求出一条最短路径，而不是配送中心到每个店最短距离。
还有，配送中心现在不要求独立开来，配送车辆可以从任何一个店出发。
那位大侠有遗传算法的实际应用源代码？
countyroad@sina.com
谢谢！
我这里的问题是要求出一条最短路径，而不是配送中心到每个店最短距离。
还有，配送中心现在不要求独立开来，配送车辆可以从任何一个店出发。
那位大侠有遗传算法的实际应用源代码？
countyroad@sina.com
谢谢！
#26
... 就是中位数啊!.....
>>我这里的问题是要求出一条最短路径，而不是配送中心到每个店最短距离。
你再想想你的化...
还用...什么遗传算法..... -_-
>>我这里的问题是要求出一条最短路径，而不是配送中心到每个店最短距离。
你再想想你的化...
还用...什么遗传算法..... -_-
#27
这也根本和旅行商没关系...
sigh....
sigh....
#28
我来说说啊 ..
能有多大的数据啊!? 能有多严格的时限啊!?
运行一次Floyd求出每个点之间的距离.
然后穷举一圈出发点不久完了么...
靠... Floyd一般六行程序 穷举一圈选最小值 三行代码 ...
... 起码 100个顶点没问题吧1000个顶点也不用两秒啊..
[大稀疏图用johnson取代Floyd]
----
to KBthu(景乐)
最小生成树好象不合适阿，这个问题考虑的是要设计一条线路，而不是一个连通图。
...
=难道这个线路是不连通的?
to WaterWalker(水上飘)
带权最短路径是怎么个思路？是不是和最小生成树一个概念？
请大家注意的是，这里的权值还和配送车辆上的剩余货物重量有关。而不单单是路径的长度。
=sigh....... 乘起来啊!!!!!!!
能有多大的数据啊!? 能有多严格的时限啊!?
运行一次Floyd求出每个点之间的距离.
然后穷举一圈出发点不久完了么...
靠... Floyd一般六行程序 穷举一圈选最小值 三行代码 ...
... 起码 100个顶点没问题吧1000个顶点也不用两秒啊..
[大稀疏图用johnson取代Floyd]
----
to KBthu(景乐)
最小生成树好象不合适阿，这个问题考虑的是要设计一条线路，而不是一个连通图。
...
=难道这个线路是不连通的?
to WaterWalker(水上飘)
带权最短路径是怎么个思路？是不是和最小生成树一个概念？
请大家注意的是，这里的权值还和配送车辆上的剩余货物重量有关。而不单单是路径的长度。
=sigh....... 乘起来啊!!!!!!!
#29
好，我再来说说。
to chenggn(chenggn)
1.穷举是能做，但未免也....
2.我之所以说最小生成树不合适，因为这里有个要求，那就是每个节点只能走一次，否则就不是一条线路了。
3.权值到底是除一下，还是乘起来？即距离/货物数量 or 距离*货物数量？
to chenggn(chenggn)
1.穷举是能做，但未免也....
2.我之所以说最小生成树不合适，因为这里有个要求，那就是每个节点只能走一次，否则就不是一条线路了。
3.权值到底是除一下，还是乘起来？即距离/货物数量 or 距离*货物数量？
#30
我觉得还是除一下有道理。
#31
up
#32
!! 对不起 原来只有!! 10个顶点...!!!
不要看不起穷举
我只是用词不当 穷举又叫搜索 搜索是规则化的遍历
而一些简单的动态规划就是搜索去掉重复的计算而达到的结果
各种图论算法 那一种其本质不是搜索.
请考虑一下我说得吧
由于Floyd求出了每个顶点之间的距离,
然后搜索出发点
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=shortdis[i][j];
}
选取最小的sum即为答案
权值的设定大概你的程序是求最大的 而且这样有浮点误差
我没有仔细考虑你的除法.
没什么说的了.
sorry 但我真的觉得 你说这是大二的题 看来你是大二的学生
还有很多时间用来学习 看来你比较喜欢学习喽
"大家可不可以给点思路，我不要源代码。"
把握时间...
不要看不起穷举
我只是用词不当 穷举又叫搜索 搜索是规则化的遍历
而一些简单的动态规划就是搜索去掉重复的计算而达到的结果
各种图论算法 那一种其本质不是搜索.
请考虑一下我说得吧
由于Floyd求出了每个顶点之间的距离,
然后搜索出发点
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=shortdis[i][j];
}
选取最小的sum即为答案
权值的设定大概你的程序是求最大的 而且这样有浮点误差
我没有仔细考虑你的除法.
没什么说的了.
sorry 但我真的觉得 你说这是大二的题 看来你是大二的学生
还有很多时间用来学习 看来你比较喜欢学习喽
"大家可不可以给点思路，我不要源代码。"
把握时间...
#33
to chenggn(chenggn)
首先说明，我不是大二的学生了，现在是研究生，只是帮别人做而已。
一开始接触这个题目的时候，我就考虑过穷举了，但是一想好象开销很大，然后找了数据结构的书，也没发现合适的算法(数据结构没学好，临时翻翻)，问了几个朋友，由于当时也没考虑仔细，始终得不到好的方法，所以在这里求各位朋友的帮助。
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=shortdis[i][j];
}
这哪里是求从一个点遍历整个图的最短路径。写错了吧？
首先说明，我不是大二的学生了，现在是研究生，只是帮别人做而已。
一开始接触这个题目的时候，我就考虑过穷举了，但是一想好象开销很大，然后找了数据结构的书，也没发现合适的算法(数据结构没学好，临时翻翻)，问了几个朋友，由于当时也没考虑仔细，始终得不到好的方法，所以在这里求各位朋友的帮助。
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=shortdis[i][j];
}
这哪里是求从一个点遍历整个图的最短路径。写错了吧？
#34
求最短路径的算法!!是上面提到的flody!!!
你等等....
你等等....
#35
d[10][10] 距离矩阵
// floyd ------
for (k=0; k<10; k++)
for (i=0; i<10; i++)
for (j=0; j<10; j++)
{
if (d[i][j]<d[i][k]+d[k][j]) // && 有d[i][k], d[k][j]路径存在
{
d[i][j]=d[i][k]+d[k][j];
/*
如果需要求出该路径
p[i][j]=p[k][i];
p[i][j]表示i到j的最短路径中 j的父辈是p[i][j]
全程序最初 初始化时 p[i][j]=i;
*/
}
}
// 以上是floyd算法 通常用于求中等规模稠密图两点间距离 复杂度仍为 O(N^3) ----
// 但复杂度比单纯运行N次Dijkstra的系数要小一些 //
// d[10][10] 现为任意两个点间的最短距离
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=d[i][j]*货物数量[j];
// 如果是除的话 货物越多 权值越小 距离越远 权值越大? 不符合要求 起码权值需要向同一个方向移动
}
// sum[i] 即为以第i个点作为起点的总运费
:) 研究生....
// floyd ------
for (k=0; k<10; k++)
for (i=0; i<10; i++)
for (j=0; j<10; j++)
{
if (d[i][j]<d[i][k]+d[k][j]) // && 有d[i][k], d[k][j]路径存在
{
d[i][j]=d[i][k]+d[k][j];
/*
如果需要求出该路径
p[i][j]=p[k][i];
p[i][j]表示i到j的最短路径中 j的父辈是p[i][j]
全程序最初 初始化时 p[i][j]=i;
*/
}
}
// 以上是floyd算法 通常用于求中等规模稠密图两点间距离 复杂度仍为 O(N^3) ----
// 但复杂度比单纯运行N次Dijkstra的系数要小一些 //
// d[10][10] 现为任意两个点间的最短距离
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
sum[i]+=d[i][j]*货物数量[j];
// 如果是除的话 货物越多 权值越小 距离越远 权值越大? 不符合要求 起码权值需要向同一个方向移动
}
// sum[i] 即为以第i个点作为起点的总运费
:) 研究生....
#36
(21:35:18):
1.这个搞配送的到底有几辆车?
如果是一辆开到底 你的错
如果是N辆随便开 你的对
2.这个"线路" 到底长什么样?
如果是一条线到底 你的错
如果是开花成生成树状 你的对
我想自杀...
1.这个搞配送的到底有几辆车?
如果是一辆开到底 你的错
如果是N辆随便开 你的对
2.这个"线路" 到底长什么样?
如果是一条线到底 你的错
如果是开花成生成树状 你的对
我想自杀...
#37
to chenggn(chenggn)
1.从题目来看，应该是一辆车。我的错？why?
2.从题目来看，他的网络是全通图，线路就相当于一笔画，也就是遍历所有的节点，但是每个节点只允许访问一次。
不好意思，麻烦你了！
1.从题目来看，应该是一辆车。我的错？why?
2.从题目来看，他的网络是全通图，线路就相当于一笔画，也就是遍历所有的节点，但是每个节点只允许访问一次。
不好意思，麻烦你了！
#38
几个新条件:
1.一辆车.
2.每个节点只允许访问一次
得出: 是哈密顿通路问题. 标准的方法是... 分枝定界
1.一辆车.
2.每个节点只允许访问一次
得出: 是哈密顿通路问题. 标准的方法是... 分枝定界
#39
上面是别人对我说得... '你'是说我chenggn...
...
5555555~!!@ 我想自杀...
...
5555555~!!@ 我想自杀...
#40
两个都是我的错....
#41
补充
权值计算是我错了。应该和距离*重量成反比。
to chenggn(chenggn)
你也不要泄气，会有办法的，我都没泄气。
to LeeMaRS(小菜虎_水壶的仇人)
分支定界我也想过，但是这里的首节点都没有定出来，那岂不是要都试一下？这不是穷举了？
权值计算是我错了。应该和距离*重量成反比。
to chenggn(chenggn)
你也不要泄气，会有办法的，我都没泄气。
to LeeMaRS(小菜虎_水壶的仇人)
分支定界我也想过，但是这里的首节点都没有定出来，那岂不是要都试一下？这不是穷举了？
#42
才10个节点,用穷举都没问题.
#43
实在不行，也只能穷举了。
#44
呵呵,我再帮你想想办法.
#45
我来说一句话:
只要你的计算是必要的 处理好重复计算的 就是好的
:)
一个图有几个一笔画? :>
只要你的计算是必要的 处理好重复计算的 就是好的
:)
一个图有几个一笔画? :>
#46
谢谢
遗传算法用过吗？
听上去很高深。
遗传算法用过吗？
听上去很高深。
#47
嘻嘻~ 大家的态度都很好嘛 共同进步 共同进步
#48
大家都在线啊？
很高兴和大家聊。
to chenggn(chenggn)
只要能改进，就要比穷举好。
很高兴和大家聊。
to chenggn(chenggn)
只要能改进，就要比穷举好。
#49
没什么了解 印象中是概率算法之类 :)
#50
我这里得到了一份遗传算法关于TSP问题求解的源代码，现在还没看。
几位要吗？
几位要吗？