版塊導(dǎo)航: 正在加載中...

登錄注冊

應(yīng)《網(wǎng)絡(luò)安全法》要求，自2017年10月1日起，未進行實名認證將不得使用互聯(lián)網(wǎng)跟帖服務(wù)。為保障您的帳號能夠正常使用，請盡快對帳號進行手機號驗證，感謝您的理解與支持！

24小時熱門版塊排行榜

北京石油化工學(xué)院2026年研究生招生接收調(diào)劑公告

返回列表

lichengjun

金蟲 (初入文壇)

應(yīng)助: 0 (幼兒園)
金幣: 830.5
帖子: 17
在線: 32小時
蟲號: 1423137
注冊: 2011-09-30
專業(yè): 通信理論與系統(tǒng)

[求助] 【求助】一個關(guān)于順序調(diào)度的問題

假設(shè)有一個球在橫軸的原點，給定n個可正可負的數(shù)字，其代表球在橫坐標(biāo)的走向及距離，正為向右走，負為向左走，每個數(shù)字只能走一次。每一次走
動都記錄下球離原點的距離D1,D2,...,Dn（距離是非負的）。想找到一種方法，根據(jù)給定的數(shù)字對球的走向進行控制，使得D1,D2,...Dn之和最小。

例如：有三個數(shù)字，（-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。這是一種貪心法，不知道這個方法是不是能得到問題的最優(yōu)解。

希望有大神能夠幫忙看看我的這種方法在數(shù)字個數(shù)較多的情況下能不能得到最優(yōu)解，如果能的話，如何證明這個結(jié)論。如果不能的話，有沒有其他的方法，或者說這類問題有沒有相關(guān)學(xué)科的書籍推薦（小弟非數(shù)學(xué)專業(yè)，不太清楚這類問題屬于數(shù)學(xué)的哪個分支，有點無從下手，所以在這里發(fā)帖求助）

回復(fù)此樓

» 猜你喜歡

一志愿雙一流機械285分求調(diào)劑已經(jīng)有5人回復(fù)
一志愿：西北大學(xué)，英一數(shù)一408-284分求調(diào)劑已經(jīng)有4人回復(fù)
291求調(diào)劑已經(jīng)有5人回復(fù)
求調(diào)劑已經(jīng)有3人回復(fù)
化學(xué)0703 調(diào)劑 306分一志愿211 已經(jīng)有5人回復(fù)
275求調(diào)劑已經(jīng)有16人回復(fù)
調(diào)劑310 已經(jīng)有11人回復(fù)
300求調(diào)劑，材料科學(xué)英一數(shù)二已經(jīng)有9人回復(fù)
296求調(diào)劑已經(jīng)有3人回復(fù)
一志愿南昌大學(xué)324求調(diào)劑已經(jīng)有3人回復(fù)

» 本主題相關(guān)價值貼推薦，對您同樣有幫助:

基團的優(yōu)先保護順序問題已經(jīng)有6人回復(fù)
MS6.0-for-linux在REHL下安裝的問題已經(jīng)有21人回復(fù)
測量材料的光吸收譜時，光路順序問題已經(jīng)有6人回復(fù)
有關(guān)高效液相自身對照法中樣品和1%對照品的進樣順序問題已經(jīng)有16人回復(fù)
關(guān)于Troque提交任務(wù)需要用qrun才能運行的討論已經(jīng)有16人回復(fù)
求助文章第一作者和第二作者順序的修改問題已經(jīng)有10人回復(fù)
有關(guān)液相出峰順序的問題已經(jīng)有12人回復(fù)
torque + maui 的設(shè)置問題已經(jīng)有14人回復(fù)
關(guān)于java多線程啊~ 已經(jīng)有4人回復(fù)
合成中加料順序的問題已經(jīng)有4人回復(fù)
【求助】氣相色譜出峰順序問題，急急急已經(jīng)有14人回復(fù)
【求助】熱處理與冷加工的順序問題已經(jīng)有16人回復(fù)

1樓 2013-07-08 20:35:35

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

pippi6

鐵桿木蟲 (著名寫手)

工程和科學(xué)數(shù)值計算咨詢

數(shù)學(xué)EPI: 6
應(yīng)助: 413 (碩士)
貴賓: 0.002
金幣: 7116.5
散金: 15
紅花: 63
帖子: 1639
在線: 798.9小時
蟲號: 2469437
注冊: 2013-05-14
專業(yè): 計算數(shù)學(xué)與科學(xué)工程計算

【答案】應(yīng)助回帖

感謝參與，應(yīng)助指數(shù) +1

我試著來公式化你的問題，給定 N個數(shù) $(R_1,R_2,...,R_N)$ 。然后有一個整數(shù)映射 $k=k(i)$ ，選擇映射k(i)使得
$\sum\limits_{m=1}^{N}\left|\sum\limits_{i=1}^{m} R_{k(i)}\right|$
最小。

我想，是不是可以先寫個程序，做做數(shù)值試驗，找找感覺。比如驗證你的”貪心法“法是不是最優(yōu)。也許會產(chǎn)生新的思路。聽起來，你是在尋求一個實用的解決方法，那即便沒有真正的數(shù)學(xué)證明，只要達到實際上的優(yōu)化目的，也是有幫助的。

贊一下

回復(fù)此樓

2樓2013-07-09 05:17:40

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

pippi6

鐵桿木蟲 (著名寫手)

工程和科學(xué)數(shù)值計算咨詢

數(shù)學(xué)EPI: 6
應(yīng)助: 413 (碩士)
貴賓: 0.002
金幣: 7116.5
散金: 15
紅花: 63
帖子: 1639
在線: 798.9小時
蟲號: 2469437
注冊: 2013-05-14
專業(yè): 計算數(shù)學(xué)與科學(xué)工程計算

【答案】應(yīng)助回帖

另外就是，實用中，你的N典型值是多大？你能接受的優(yōu)化時間是多少？我在想，這就像很多實用的sorting 方法一樣，也許你要的就是一個實用的排序方法，或手續(xù)、程序，能夠在可接受的時間內(nèi)解決問題。非得要嚴格的數(shù)學(xué)證明嗎？像百度查找，只要實際上快，誰會在乎有沒有證明它是最快的呢？

贊一下

回復(fù)此樓

3樓2013-07-09 05:29:21

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

lichengjun

金蟲 (初入文壇)

應(yīng)助: 0 (幼兒園)
金幣: 830.5
帖子: 17
在線: 32小時
蟲號: 1423137
注冊: 2011-09-30
專業(yè): 通信理論與系統(tǒng)

引用回帖:

2樓: Originally posted by pippi6 at 2013-07-09 05:17:40
我試著來公式化你的問題，給定 N個數(shù) (R_1,R_2,...,R_N)。然后有一個整數(shù)映射 k=k(i) ，選擇映射k(i)使得
\sum\limits_{m=1}^{N}\left|\sum\limits_{i=1}^{m} R_{k(i)}\right|
最小。

我想，是不是可以 ...

對的，其實我想找的就是一個較為實用的解決方法，但是如果我的方法不是最優(yōu)的，我想能夠比較我的算法與最優(yōu)算法的差別。還有就是這方面的問題屬于什么學(xué)科，有沒有什么相關(guān)的書籍推薦。
還有就是如果寫程序，我不知道如何找到最優(yōu)的方案，只能窮舉法感覺。

贊一下

回復(fù)此樓

4樓2013-07-09 10:35:12

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

lichengjun

金蟲 (初入文壇)

應(yīng)助: 0 (幼兒園)
金幣: 830.5
帖子: 17
在線: 32小時
蟲號: 1423137
注冊: 2011-09-30
專業(yè): 通信理論與系統(tǒng)

引用回帖:

3樓: Originally posted by pippi6 at 2013-07-09 05:29:21
另外就是，實用中，你的N典型值是多大？你能接受的優(yōu)化時間是多少？我在想，這就像很多實用的sorting 方法一樣，也許你要的就是一個實用的排序方法，或手續(xù)、程序，能夠在可接受的時間內(nèi)解決問題。非得要嚴格的數(shù) ...

典型值大概也就100左右，所以基本上不考慮優(yōu)化的時間吧...也不是說非得有嚴格的數(shù)學(xué)證明，我想知道的是自己的方法跟最優(yōu)解法會有多大的差距。類似于這種實用的sorting方法，有沒有什么比較合適的書籍推薦呢？謝謝！

贊一下

回復(fù)此樓

5樓2013-07-09 10:45:13

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

pippi6

鐵桿木蟲 (著名寫手)

工程和科學(xué)數(shù)值計算咨詢

數(shù)學(xué)EPI: 6
應(yīng)助: 413 (碩士)
貴賓: 0.002
金幣: 7116.5
散金: 15
紅花: 63
帖子: 1639
在線: 798.9小時
蟲號: 2469437
注冊: 2013-05-14
專業(yè): 計算數(shù)學(xué)與科學(xué)工程計算

【答案】應(yīng)助回帖

引用回帖:

5樓: Originally posted by lichengjun at 2013-07-09 10:45:13
典型值大概也就100左右，所以基本上不考慮優(yōu)化的時間吧...也不是說非得有嚴格的數(shù)學(xué)證明，我想知道的是自己的方法跟最優(yōu)解法會有多大的差距。類似于這種實用的sorting方法，有沒有什么比較合適的書籍推薦呢？謝謝！...

其實，我也不懂怎么優(yōu)化sorting，也就是簡單的窮舉法吧。但我感覺，如果在100左右，你根本就感覺不出來差別。有個解決問題的方法不就行了嗎？你的方法0.01s，優(yōu)化后0.001s，你覺得有區(qū)別嗎？我倒是想試試，找個隨機序列，100個數(shù)�？纯凑乙淮纹骄嚅L時間。

贊一下

回復(fù)此樓

6樓2013-07-09 11:02:15

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

lichengjun

金蟲 (初入文壇)

應(yīng)助: 0 (幼兒園)
金幣: 830.5
帖子: 17
在線: 32小時
蟲號: 1423137
注冊: 2011-09-30
專業(yè): 通信理論與系統(tǒng)

引用回帖:

6樓: Originally posted by pippi6 at 2013-07-09 11:02:15
其實，我也不懂怎么優(yōu)化sorting，也就是簡單的窮舉法吧。但我感覺，如果在100左右，你根本就感覺不出來差別。有個解決問題的方法不就行了嗎？你的方法0.01s，優(yōu)化后0.001s，你覺得有區(qū)別嗎？我倒是想試試，找個隨 ...

我其實都不考慮優(yōu)化的時間，因為數(shù)值比較小。我就是想找到一個最優(yōu)的解決方法，當(dāng)然最好不是窮舉法了。
如果找不到最優(yōu)的方法，我就想找到一種稍微簡單的方法，然后與最優(yōu)解進行比較，看看會有多大的差距�；旧蟻碚f，優(yōu)化的時間我并不考慮。

贊一下

回復(fù)此樓

7樓2013-07-09 11:10:39

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

lichengjun

金蟲 (初入文壇)

應(yīng)助: 0 (幼兒園)
金幣: 830.5
帖子: 17
在線: 32小時
蟲號: 1423137
注冊: 2011-09-30
專業(yè): 通信理論與系統(tǒng)

我用10個數(shù)進行窮舉來求最小距離，發(fā)現(xiàn)我自己貪心法并不能得到最優(yōu)的解，但是與最優(yōu)解相差并不是特別大�，F(xiàn)在的問題就是上述的問題是不是一個NP問題，如果不是NP問題，是不是能找出一個最優(yōu)算法；如果是NP問題的話，又如何將這個問題歸化為已知的NP問題？

贊一下

回復(fù)此樓

8樓2013-07-09 13:20:39

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

相關(guān)版塊跳轉(zhuǎn) 我要訂閱樓主 lichengjun 的主題更新

返回列表

最具人氣熱帖推薦 [查看全部]		作者	回/看	最后發(fā)表

[考研] 275求調(diào)劑 +11	Micky11223 2026-03-25	16/800	2026-03-29 14:27 by 1018329917
[考研] 總分293求調(diào)劑 +6	加一一九 2026-03-25	9/450	2026-03-29 13:40 by 加一一九
[考研] 309求調(diào)劑 +7	誰不是少年 2026-03-29	7/350	2026-03-29 13:17 by mumin1990
[考研] 321求調(diào)劑 +7	璞玉~~ 2026-03-25	8/400	2026-03-29 06:41 by 544594351
[考研] 復(fù)試調(diào)劑 +3	raojunqi0129 2026-03-28	3/150	2026-03-28 15:27 by 落�？伤�
[考研] 求調(diào)劑 +6	蘆lty 2026-03-25	7/350	2026-03-28 13:13 by 唐沐兒
[考研] 283求調(diào)劑 +7	A child 2026-03-28	7/350	2026-03-28 12:05 by zllcz
[考研] 291求調(diào)劑 +6	HanBeiNingZC 2026-03-24	6/300	2026-03-28 07:55 by baoball
[考研] 272求調(diào)劑 +7	腳滑的守法公民 2026-03-27	7/350	2026-03-27 17:23 by laoshidan
[考研] 307求調(diào)劑 +8	超級伊昂大王 2026-03-24	9/450	2026-03-27 15:34 by 超級伊昂大王
[考研] 復(fù)試調(diào)劑，一志愿南農(nóng)083200食品科學(xué)與工程 +5	XQTJZ 2026-03-26	5/250	2026-03-27 14:49 by 狂炫麥當(dāng)當(dāng)
[考研] 一志愿鄭大085600，310分求調(diào)劑 +5	李瀟可 2026-03-26	5/250	2026-03-27 11:14 by 不吃魚的貓
[考研] 0703化學(xué)338求調(diào)劑！ +6	Zuhui0306 2026-03-26	7/350	2026-03-27 10:35 by shangxh
[考研] 081200-11408-276學(xué)碩求調(diào)劑 +4	崔wj 2026-03-26	4/200	2026-03-27 08:04 by chemisry
[考研] 325求調(diào)劑 +5	李嘉圖·S·路 2026-03-23	5/250	2026-03-27 00:42 by wxiongid
[考研] 351求調(diào)劑 +4	麥克阿磊 2026-03-24	4/200	2026-03-27 00:32 by wxiongid
[考研] 263求調(diào)劑 +6	yqdszhdap－ 2026-03-22	10/500	2026-03-26 13:11 by 公瑾逍遙
[考研] 打過很多競賽，085406控制工程300分，求調(diào)劑 +3	askeladz 2026-03-26	3/150	2026-03-26 09:08 by 給你你注意休息
[考研] 269求調(diào)劑 +4	我想讀研11 2026-03-23	4/200	2026-03-23 21:25 by pswait
[考研] 336化工調(diào)劑 +4	王大坦1 2026-03-23	5/250	2026-03-23 18:32 by allen-yin

24小時熱門版塊排行榜

[求助] 【求助】一個關(guān)于順序調(diào)度的問題

» 猜你喜歡

» 本主題相關(guān)價值貼推薦，對您同樣有幫助:

【答案】應(yīng)助回帖

【答案】應(yīng)助回帖

【答案】應(yīng)助回帖

» 本主題相關(guān)價值貼推薦，對您同樣有幫助: