[PR]当サイトはアフィリエイト広告を利用しています。
このブログで何度か取り上げてきたSPF材の最小切り出し問題ですが、この問題は組み合わせ最適化問題の瓶パッキング問題と呼ばれる問題です。
NP-困難な問題として厳密に解くのが難しい問題です。
この分野の代表的な解法として貪欲法というのがあります。
今回はこの貪欲法のファーストフィットアルゴリズムを用いてSPF材の最小切り出し問題を解いてみようと思います。
参考：B.コルテ/J.フィーゲン 浅野孝夫/浅野泰仁/小野孝男/平田富夫訳(2012)『組合せ最適化 第2版 理論とアルゴリズム』丸善出版
ファーストフィットアルゴリズムは品物が詰められる瓶の中で添え字が最小の瓶に品物を詰め、詰められなければ新しい瓶をオープンにするというのを繰り返すアルゴリズムです。
品物を詰めました。さらに詰められるなら詰める。詰められないなら新しい瓶に詰めるという単純なアルゴリズムです。
瓶が材木一本、詰める容量が各パーツの長さです。
では作成したプログラムです。
item = [[20,'A'],[20,'B'],[40,'C'],[40,'D'],[60,'E'],[60,'F'],[80,'G'],[80,'H'],[94,'I'],[94,'J'],\
[60,'K'],[60,'L'],[60,'M'],[60,'N'],[60,'O'],[60,'P'],[60,'Q'],[60,'R'],[60,'S'],[60,'T'],[60,'U'],\
[60,'V']]
item.sort(reverse=True)
check = [False,False,False,False,False,False,False,False,False,False,\
False,False,False,False,False,False,False,False,False,False,False,False]
material = [0]
capacity = 180
for i in range(len(item)):
materialFlag = False
for j in range(len(material)):
tempVolume = material[j] + item[i][0]
if(tempVolume <= capacity ):
material[j] = tempVolume
check[i] = j
materialFlag = True
break
if(materialFlag ==False):
material.append(item[i][0])
check[i] = len(material) - 1
print('materialNum: ' + str(len(material)))
for i in range(len(item)):
print(item[i][1] +':' + str(check[i]))
print('sumLength: ' + str(180 * (len(material) - 1) + material[-1]))1行目から8行目は各種値を格納するリストなどの初期化です。
itemには対象とするパーツの長さと、それぞれのパーツのラベルを設定しています。
4行目でソートするのは、大きいパーツから詰めていったほうが結果的に少ない瓶数で詰められることが多いからです。
リストcheckには各パーツが何番目の瓶に詰められたかが格納されます。
リストmaterialには各瓶の詰められ具合が格納されます。material[0]が140のとき、一番目の瓶には合計140cmのパーツがあてがわれているということです。
capacityには瓶の容量、すなわち材木一本の長さが格納されます。
9行目から20行目で実際に瓶にパーツを詰めていきます。
11行目から17行目ではいったん添え字が小さい瓶に現在のパーツの長さを詰めてみて、詰められるならその瓶の長さを更新して、パーツに対応する瓶をcheckに格納します。
詰められないなら18行目から20行目で新しい瓶をオープンして新しい瓶をそのパーツにあてがいます。
21行目から24行目は出力です。
使った瓶の数とその対応状況、最終的な瓶の容量の合計を出力します。
実際の出力は以下。
materialNum: 8
J:0
I:1
H:0
G:1
V:2
U:2
T:2
S:3
R:3
Q:3
P:4
O:4
N:4
M:5
L:5
K:5
F:6
E:6
D:6
C:7
B:6
A:7
sumLength: 1320
以前ソルバーで解いた結果と同じ総量、1320が求められました。
これ、どう考えてもソルバーより計算量が少ないです。
貪欲法の強さとこのアルゴリズムを考えた方はすごいなーと思いました。
