線上訂房服務-台灣趴趴狗聯合訂房中心
發文 回覆 瀏覽次數:992
推到 Plurk!
推到 Facebook!

使用BEAM SEARCH解決碼頭指派問題

尚未結案
mazarine
一般會員


發表:3
回覆:2
積分:1
註冊:2011-06-05

發送簡訊給我
#1 引用回覆 回覆 發表時間:2011-06-05 22:33:50 IP:114.25.xxx.xxx 訂閱
我對於演算法應用在碼頭指派上有些問題
想麻煩各位大大幫住我

我想使用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 神手幫忙
感激不盡
附加檔案:4deb93ce2f6da_CODE1.txt
mazarine
一般會員


發表:3
回覆:2
積分:1
註冊:2011-06-05

發送簡訊給我
#2 引用回覆 回覆 發表時間:2011-06-07 12:30:13 IP:114.25.xxx.xxx 訂閱
怎麼都沒有人理我@_@
拜託各位大大幫忙
感激不盡
暗黑破壞神
版主


發表:9
回覆:2301
積分:1627
註冊:2004-10-04

發送簡訊給我
#3 引用回覆 回覆 發表時間:2011-06-12 10:08:12 IP:122.122.xxx.xxx 未訂閱
哈,我也看不懂你在說什麼?

你要發問演算法的問題。
我想你要對演算法有定義。
什麼是演算法?
它是來幹什麼的?
演算法是用來”解決問題的方法”。
什麼問題?某一個”特定的問題”。

而你並沒有把你的問題描述清楚呀。
沒把問題描述清楚,根本不知道目標在那邊。
怎麼解題?
===================引 用 mazarine 文 章===================
怎麼都沒有人理我@_@
拜託各位大大幫忙
感激不盡
系統時間:2017-10-19 2:32:02
聯絡我們 | Delphi K.Top討論版
本站聲明
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇!