search

icsnju / I2EC

3 stars 0 forks source link

4月30日进度报告：异常结果总结 #40

Open 2bdenny opened 5 years ago

2bdenny commented 5 years ago
  1. 根据算法得到的路径和业务数据中的验证路径，总结并说明异常结果情况
  2. 进行算法性能分析
2bdenny commented 5 years ago

30号下午跟段昕针对还原的路径不一致的情况讨论了一下，然后他确认路径还原时有一条限制，同路段内的路径不可拼接，所以30号下午提到的我们还原的路径更短的105/900条数据，实际上是不可行路径。

所以我们修改了模型，在建模的时候将所有点都保存为2个，分别叫v.from和v.to，在连边时：

  1. 对于同一路段内的边，保证都是 v1.from 到 v2.to，如果某个点v允许调头，额外增加一条 v.from 到 v.to的边
  2. 对于不同路段间的边，保证都是 vx.to 到 vy.from，每一条不同路段间的连接都代表2条边

在此模型上重新运行已实现的算法，除了预处理的floyd变慢了很多（点数增加了一倍），真正的计算时间没有变化，并且业务数据全部正确还原（也就是没有我们计算出来的路径更短这种情况了，所以不需要请曹总@caochun 联系他们修改要求了，@FancyPei 实现的算法也没有问题，不需要修改）

稍后@2bdenny 会进行运行时间相关的测试然后更新到报告里（下次讨论Orz）