前陣子寫了一個case,如下網站:
http://robot101.blogspot.com/
是一個郵政排班系統,每個人都有負責的區域(1~6個),這一生當中只會排這些區域。
而一天中,除了休假,還有特別排班(即是那個人那天就分配特定區域)之外,其餘的人每個人負責一個區域。
簡單來說,如果有56個區域,就有56個人負責,每個人負責區域不同。
演算法真的很難想,我想過各種方法,最後使用暴力法,就是每種狀況都去測試。可是問題來了!幸運的話,幾分鐘就排出來,如果很慘的話可能要跑上好幾個小時都不一定有結果。原因是總共有67個人,而我要測試6的67次方之多...這是很恐怖的數字,導致效率真是奇差無比。
請問有哪位大大有想到更好的方法碼嗎QQ?我願意給他我所有的IT幣,雖然只有48元QQ
如果可以的話就請將你說的這部份程式的演算法上傳,大家可以互相研究
LabVIEW.rar
裡面有Excel檔,禮拜一要用電腦排排看,禮拜二是手工排好的。
暴力法是我寫的程式:(
????? Folder.rar
OK,試試看這個!我把一些基礎的數值都default了
我程式功力太弱,幫不上忙,不過進來幫你加油打氣一下^^
有個小建議,6的67次方太大了!
那如果是67的6次方會不會比較好一點呢?
還有,排過的地方不是就能去掉,不用再比對了嗎?
因為程式我不大行,不知道是不是可行。
希望對你有幫助,加油
我的用意也是拋磚引玉,看是否有邏輯分析強的人可以幫忙
K大,小弟為8.2版,所以只能從敘述中來和了解問題
暴力法是否為將6個區域進行67個人的尋找,所以總共要6的67次方的尋找
小弟的想法與 iamcary 類似,是否可以將已尋找過的範圍作惕除
這樣子尋找的範圍與次數會越來越小
另外,小弟有找到搜尋的演算法網頁
K大可以參考與討論哦
http://www.chwa.com.tw/TResource/HS/book2/ch7/7-5.htm
elvistu40404.0094560185
感謝各位的想法XD,我想變成6的67次方還是很大
我是有寫過弄掉就刪除,可是會有一些情況排不出來
XD有誰想要接此案的吧!我可以幫你跟顧客牽線一下...
因為雇主也很急XD
caeru
13
版本不同沒辦法改…
給點之前做類似案件的建議:
0. 初始化變數
1. 列出每個人所可能負責的全部區域清單
2. 計算每個區域負責的人數,若有區域無人負責,則重新計算
3. 以最少人負責的區域,隨機抽一個人負責該區域
4. 若同時有多數最少人負責的區域,隨機抽一個區域執行第3項
5. 將已分配的人移出清單
6. 重複執行1-5項,直到所有人數安排完
其中針對演算時間比較有影響的是:
1. 盡可能採用隨機,固定方式推論容易造成多餘演算
2. 無需最佳化,意味著只需要找最少人負責的區域,不要再多找負責最少區域的人,容易流於固定演算,反而難求到答案
(因為規則都一樣,每次演算都要跑相同流程)
3. 雖然遞迴是神的技巧,但是有時候容易陷入迷思,反而浪費時間
跟你原本的作法雷同,但是刪除一些東西或許會能更快得到答案,參考看看^^?
這是個很棒的題目~只是小弟還是看不太懂
56個區域有56個人負責~可是一個人又要負責1~6的區域<==============這裡不是很懂
是要操死他呢~~還是說過太爽
可以解釋一下嗎
根據knightsoul的Excel檔,展開成區域vs.可出勤人員的交叉表,並計算每個區域可用人數,以及每個人可負責區域數,手動進行排班作業後,提供個人一點淺見:
其演算法則中,有固定優先順序部份(只要每個區域負責人數大於0,必定有解):
1.必須從負責人數最少的區域開始分派(人數少->人數多)。
2.一個區域排除已分配者後,需從負責最少區域數的人開始分派。
無優先順序,可隨機分派部份(隨機選定區域或人員時,可衍生多種解):
1.相同負責人數的區域中,可隨機選擇區域進行分派。
2.某區域可分派人員其負責區域數最少者,有超過1人時。
@caeru
其實我之前用過隨機的方式去搜尋,可是其實效果也不太好,我有考慮到人數最少的先排,區域最少的先排。
但是效果都不太好
最大的問題莫過於區域最少人的排完之後,其他的區域其實人數都差不多。
[QUOTE=NewHandAlex]
這是個很棒的題目~只是小弟還是看不太懂
56個區域有56個人負責~可是一個人又要負責1~6的區域<==============這裡不是很懂
是要操死他呢~~還是說過太爽
可以解釋一下嗎
[/QUOTE]
小弟的認知如下(不知道是否正確)..
題目意思為:
每個人有負責的區域,所以56個區域會有56個人負責
如果當天因為有某些人員休假時,就會有其他幾個人來頂休假人的區域,也就是特別排班的意思
若有錯誤,再麻煩K大修正一下
elvistu40407.8813657407
[QUOTE=elvistu][QUOTE=NewHandAlex]
這是個很棒的題目~只是小弟還是看不太懂
56個區域有56個人負責~可是一個人又要負責1~6的區域<==============這裡不是很懂
是要操死他呢~~還是說過太爽
可以解釋一下嗎
[/QUOTE]
小弟的認知為(不知道是否正確)
每個人有負責的區域,所以56個區域會有56個人負責
如果當天因為有某些人員休假時,就會有其他幾個人來頂休假人的區域,也就是特別排班的意思
若有錯誤,再麻煩K大修正一下
[/QUOTE]
大致上都正確,只有特別排班的地方XD
特別排班的意思是指說主管就是要某人安排哪些區域,而這些區域可能不會在他負責區域裡。
簡單來說,特別區域只是主管指定某人某區域而已。
有哪些先進有特別的想法了嗎?
[QUOTE=knightsoul]
最大的問題莫過於區域最少人的排完之後,其他的區域其實人數都差不多。
[/QUOTE]
請教一下,K大說明這樣子的結果,算是不好的排法嗎??