使用BEAM SEARCH解決碼頭指派問題 |
|
尚未結案
|
|
mazarine
一般會員   發表：3 回覆：2 積分：1 註冊：2011-06-05 發送簡訊給我 |
我對於演算法應用在碼頭指派上有些問題
想麻煩各位大大幫住我 我想使用BEAM SEARCH解決碼頭指派的問題 先用FCFS先到先指派的方式得到初始解 然後利用BEAM SEARCH尋找最佳解 在下面我舉一個例子 -------------------------------------------------------------------- 如附件 這個CODE用來求初始解 舉例來說 下面這個陣列 A B C D E F G 碼頭一 7 8 2 5 11 3 6 碼頭二 4 9 1 8 8 6 9 碼頭三 3 10 7 6 9 9 5 抵達時間 5 12 3 8 7 6 9 ABCDEFG分別代表不同船隻 下面的是數字分別代表每艘船隻在不同碼頭的作業時間 最後一橫排則是表示每一艘船隻抵達港口的時間 想要用先到先服務FCFS的方式來求解 可以得到下面這個樣子 1: FFF 1: GGGGGG 2: C 2: EEEEEEEE 3: AAA 3: DDDDDD 3: BBBBBBBBBBBB 船隻C第一個抵達港口 將其排入服務時間最短的二號碼頭 接著是船隻A到達 將其排入服務時間最短的三號碼頭 以此類推 從上圖得知船隻的等待時間為二個時間單位 在三號碼頭 服務D船隻與B船隻的時間 然後求得總等候時間為多少 到這邊不曉得各位大大看得懂看不懂 小弟擔心解釋得不清楚 ---------------------------------------------------------------------------------- 然後現在我想要用BEAM SEARCH進行最佳化的求解 先用初始解固定一開始最早進入港口的船隻 每一層BEAM表示尚未解決的船隻數目 第一層裡面有 第一艘船隻在A碼頭 第一艘船隻在B碼頭 第一艘船隻在C碼頭 ................................... ................................... 以此類推直到最後一艘船隻在最後一個碼頭 然後第二層接著把扣掉第一層繼續做 然後依照每一艘船隻在每一個碼頭等候時間 作業時間的總合 以最短的為優先去尋找 直到最後一艘船也被安排到固定的碼頭 想要求總等候時間最小 以上 不曉得各位高手看得懂看不懂 想請問應該要怎麼寫?? 最後下面附上初始解的程式碼 這個部份我實在是非常不了解 麻煩請C 神手幫忙 感激不盡 |
|
mazarine
一般會員 發表：3 回覆：2 積分：1 註冊：2011-06-05 發送簡訊給我 |
|
|
暗黑破壞神
版主   發表：9 回覆：2301 積分：1627 註冊：2004-10-04 發送簡訊給我 |
發表時間：2011-06-05 22:33:50
IP:114.25.xxx.xxx 訂閱
附加檔案：系統時間：2024-11-21 22:01:31
聯絡我們 | Delphi K.Top討論版
| 本站聲明 |
|
1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！ |