| 查看: 1887 | 回复: 7 | ||
[求助]
【求助】一个关于顺序调度的问题
|
|
假设有一个球在横轴的原点，给定n个可正可负的数字，其代表球在横坐标的走向及距离，正为向右走，负为向左走，每个数字只能走一次。每一次走 动都记录下球离原点的距离D1,D2,...,Dn（距离是非负的）。想找到一种方法，根据给定的数字对球的走向进行控制，使得D1,D2,...Dn之和最小。 例如：有三个数字，（-3，-1，6），选择顺序为（-1，-3，6），这样距离之和为1+4+2=7最短，而顺序（-1，6，-3）的距离之和为1+5+2 = 8； 我的想法是在选取球的走向顺序时，每次都使球尽量靠近原点，就如同上面例子的（-1，-3，6），第一次选取1，使得离原点最近，然后再选取-3，使得距离为4（如果选取6的话则为5），最后选取6。这是一种贪心法，不知道这个方法是不是能得到问题的最优解。 希望有大神能够帮忙看看我的这种方法在数字个数较多的情况下能不能得到最优解，如果能的话，如何证明这个结论。如果不能的话，有没有其他的方法，或者说这类问题有没有相关学科的书籍推荐（小弟非数学专业，不太清楚这类问题属于数学的哪个分支，有点无从下手，所以在这里发帖求助） |
回复此楼» 猜你喜欢
大家散了吧，后缀研究没有意义，别浪费时间了，过好目前的每一天，不要焦虑
已经有6人回复
-
固定端突然变了，今天
已经有6人回复
-
听说今天filecode变了
已经有25人回复
-
基金中了
已经有4人回复
-
filecode
已经有10人回复
-
filecode
已经有12人回复
-
一个有机合成实验室都需要哪些设备？
已经有12人回复
-
求各位大神看下
已经有33人回复
-
咨询面上基金
已经有7人回复
-
影响面上的因素
已经有11人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 基团的优先保护顺序问题
已经有6人回复
- MS6.0-for-linux在REHL下安装的问题
已经有21人回复
- 测量材料的光吸收谱时，光路顺序问题
已经有6人回复
- 有关高效液相自身对照法中样品和1%对照品的进样顺序问题
已经有16人回复
- 关于Troque提交任务需要用qrun才能运行的讨论
已经有16人回复
- 求助文章第一作者和第二作者顺序的修改问题
已经有10人回复
- 有关液相出峰顺序的问题
已经有12人回复
- torque + maui 的设置问题
已经有14人回复
- 关于java多线程啊~
已经有4人回复
- 合成中加料顺序的问题
已经有4人回复
- 【求助】气相色谱出峰顺序问题，急急急
已经有14人回复
- 【求助】热处理与冷加工的顺序问题
已经有16人回复
pippi6
铁杆木虫 (著名写手)
工程和科学数值计算咨询
- 数学EPI: 6
- 应助: 413 (硕士)
- 贵宾: 0.002
- 金币: 7116.5
- 散金: 15
- 红花: 63
- 帖子: 1639
- 在线: 798.9小时
- 虫号: 2469437
- 注册: 2013-05-14
- 专业: 计算数学与科学工程计算
2楼2013-07-09 05:17:40
pippi6
铁杆木虫 (著名写手)
工程和科学数值计算咨询
- 数学EPI: 6
- 应助: 413 (硕士)
- 贵宾: 0.002
- 金币: 7116.5
- 散金: 15
- 红花: 63
- 帖子: 1639
- 在线: 798.9小时
- 虫号: 2469437
- 注册: 2013-05-14
- 专业: 计算数学与科学工程计算
3楼2013-07-09 05:29:21
4楼2013-07-09 10:35:12
5楼2013-07-09 10:45:13
pippi6
铁杆木虫 (著名写手)
工程和科学数值计算咨询
- 数学EPI: 6
- 应助: 413 (硕士)
- 贵宾: 0.002
- 金币: 7116.5
- 散金: 15
- 红花: 63
- 帖子: 1639
- 在线: 798.9小时
- 虫号: 2469437
- 注册: 2013-05-14
- 专业: 计算数学与科学工程计算
6楼2013-07-09 11:02:15
7楼2013-07-09 11:10:39
8楼2013-07-09 13:20:39
50