应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 运筹学与控制论 » 【求助】一个关于顺序调度的问题
81/1返回列表
查看: 1609  |  回复: 7
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

lichengjun

金虫 (初入文坛)

[求助] 【求助】一个关于顺序调度的问题

假设有一个球在横轴的原点，给定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。这是一种贪心法，不知道这个方法是不是能得到问题的最优解。

希望有大神能够帮忙看看我的这种方法在数字个数较多的情况下能不能得到最优解，如果能的话，如何证明这个结论。如果不能的话，有没有其他的方法，或者说这类问题有没有相关学科的书籍推荐（小弟非数学专业，不太清楚这类问题属于数学的哪个分支，有点无从下手，所以在这里发帖求助）
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2013-07-08 20:35:35
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

pippi6

铁杆木虫 (著名写手)

工程和科学数值计算咨询

【答案】应助回帖

感谢参与，应助指数 +1
我试着来公式化你的问题，给定 N个数  。然后有一个整数映射   ，选择映射k(i)使得

最小。

我想，是不是可以先写个程序，做做数值试验，找找感觉。比如验证你的”贪心法“法是不是最优。也许会产生新的思路。听起来，你是在寻求一个实用的解决方法，那即便没有真正的数学证明，只要达到实际上的优化目的，也是有帮助的。
赞一下 回复此楼
2楼2013-07-09 05:17:40
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

pippi6

铁杆木虫 (著名写手)

工程和科学数值计算咨询

【答案】应助回帖

另外就是，实用中，你的N典型值是多大？ 你能接受的优化时间是多少？我在想，这就像很多实用的sorting 方法一样， 也许你要的就是一个实用的排序方法，或手续、程序，能够在可接受的时间内解决问题。非得要严格的数学证明吗？像百度查找，只要实际上快，谁会在乎有没有证明它是最快的呢？
赞一下 回复此楼
3楼2013-07-09 05:29:21
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

lichengjun

金虫 (初入文坛)
引用回帖:
2楼: Originally posted by pippi6 at 2013-07-09 05:17:40
我试着来公式化你的问题，给定 N个数  (R_1,R_2,...,R_N)。然后有一个整数映射   k=k(i) ，选择映射k(i)使得
\sum\limits_{m=1}^{N}\left|\sum\limits_{i=1}^{m}  R_{k(i)}\right|
最小。

我想，是不是可以 ...

对的，其实我想找的就是一个较为实用的解决方法，但是如果我的方法不是最优的，我想能够比较我的算法与最优算法的差别。还有就是这方面的问题属于什么学科，有没有什么相关的书籍推荐。
还有就是如果写程序，我不知道如何找到最优的方案，只能穷举法感觉。
赞一下 回复此楼
4楼2013-07-09 10:35:12
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

lichengjun

金虫 (初入文坛)
引用回帖:
3楼: Originally posted by pippi6 at 2013-07-09 05:29:21
另外就是，实用中，你的N典型值是多大？ 你能接受的优化时间是多少？我在想，这就像很多实用的sorting 方法一样， 也许你要的就是一个实用的排序方法，或手续、程序，能够在可接受的时间内解决问题。非得要严格的数 ...

典型值大概也就100左右，所以基本上不考虑优化的时间吧...也不是说非得有严格的数学证明，我想知道的是自己的方法跟最优解法会有多大的差距。类似于这种实用的sorting方法，有没有什么比较合适的书籍推荐呢？谢谢！
赞一下 回复此楼
5楼2013-07-09 10:45:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

pippi6

铁杆木虫 (著名写手)

工程和科学数值计算咨询

【答案】应助回帖

引用回帖:
5楼: Originally posted by lichengjun at 2013-07-09 10:45:13
典型值大概也就100左右，所以基本上不考虑优化的时间吧...也不是说非得有严格的数学证明，我想知道的是自己的方法跟最优解法会有多大的差距。类似于这种实用的sorting方法，有没有什么比较合适的书籍推荐呢？谢谢！...

其实，我也不懂怎么优化sorting，也就是简单的穷举法吧。但我感觉，如果在100左右，你根本就感觉不出来差别。有个解决问题的方法不就行了吗？你的方法0.01s，优化后0.001s， 你觉得有区别吗？我倒是想试试，找个随机序列，100个数。看看找一次平均多长时间。
赞一下 回复此楼
6楼2013-07-09 11:02:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

lichengjun

金虫 (初入文坛)
引用回帖:
6楼: Originally posted by pippi6 at 2013-07-09 11:02:15
其实，我也不懂怎么优化sorting，也就是简单的穷举法吧。但我感觉，如果在100左右，你根本就感觉不出来差别。有个解决问题的方法不就行了吗？你的方法0.01s，优化后0.001s， 你觉得有区别吗？我倒是想试试，找个随 ...

我其实都不考虑优化的时间，因为数值比较小。我就是想找到一个最优的解决方法，当然最好不是穷举法了。
如果找不到最优的方法，我就想找到一种稍微简单的方法，然后与最优解进行比较，看看会有多大的差距。基本上来说，优化的时间我并不考虑。
赞一下 回复此楼
7楼2013-07-09 11:10:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

lichengjun

金虫 (初入文坛)
我用10个数进行穷举来求最小距离，发现我自己贪心法并不能得到最优的解，但是与最优解相差并不是特别大。现在的问题就是上述的问题是不是一个NP问题，如果不是NP问题，是不是能找出一个最优算法；如果是NP问题的话，又如何将这个问题归化为已知的NP问题？
赞一下 回复此楼
8楼2013-07-09 13:20:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 lichengjun 的主题更新
81/1返回列表
普通表情 龙 兔 虎 猫
信息提示
关闭
请填处理意见
关闭