前回は、Wikipedia「ビンパッキング問題」に乗っている２つのアルゴリズムのうち、アルゴリズムAを改良してみました。
今回は、アルゴリズムBを改良し、その後、さらに別の視点で改良を加えてみます。
繰り返しになりますが、Wikipedia「ビンパッキング問題」アルゴリズムは、荷物の全体像が分からないという前提のアルゴリズムです。
改良版では、条件を緩和し、「全体像が把握できる」という前提で、より良い解を求めようというものです。
アルゴリズムBの改良版アルゴリズム
アルゴリズムBの改良版では、単に、最初にソートしてしまおうという単純なものです。
- 前準備として荷物を重い順に並び変える。
- 荷物を空いている容量が最小のビンに詰める。
- どのビンにも荷物が入らないとき、新しいビンに詰める。
と、こんな感じです。
実に簡単な改良です。
改良したコード
クラス名をBinPackingSolver21としました。安易なネーミングですみませんm(_ _)m
変更したのは、一か所のみ。
foreach (var n in items) {
を
foreach (var n in items.OrderByDescending(x => x)) {
にしただけです。
それ以外は、まったく同じアルゴリズムです。
class BinPackingSolver21 : IBinPacking {
public int BinSize { get; set; }
public BinPackingSolver21(int size) {
BinSize = size;
}
public ICollection<ICollection<int>> Solve(int[] items) {
// 最初に一つのビンを用意する
var binList = new List<ICollection<int>>();
binList.Add(new List<int>());
// 各項目をビンに入れてゆく
foreach (var n in items.OrderByDescending(x => x)) {
// nが入るビンを見つける （空きが最小のビン）
var target = binList.Select(b => new { Bin = b, Space = BinSize - b.Sum(t => t) })
.Where(x => x.Space >= n)
.OrderBy(x => x.Space)
.Select(x => x.Bin);
var bin = target.FirstOrDefault();
if (bin != null) {
// nが入るビンが見つかったので、そこに入れる
bin.Add(n);
} else {
// 見つからなかったので、新しいビンを用意する
List<int> bin2 = new List<int>() { n };
binList.Add(bin2);
}
}
return binList;
}
}
確かめてみる
それでは、本当に改良されたのかどうかを確かめてみます。
ちょっと試しただけでは、改良されたか確認できなかったので、ランダムに生成したデータで検証することとしました。
class Program {
static void Main(string[] args) {
int win = 0;
int lose = 0;
int draw = 0;
for (int i = 0; i < 10000; i++) {
(var items, var binsize) = GetDate();
var bp1 = new BinPackingSolver2(binsize);
var r1 = bp1.Solve(items);
var bp2 = new BinPackingSolver21(binsize);
var r2 = bp2.Solve(items);
if (r1.Count() == r2.Count())
draw++;
else if (r1.Count() < r2.Count())
lose++;
else
win++;
}
Console.WriteLine($"改良版の勝ち:{win}");
Console.WriteLine($"改良版の負け:{lose}");
Console.WriteLine($"改良版の引分け:{draw}");
Console.ReadLine();
}
private static Random rnd = new Random();
private static (int[], int) GetDate() {
IEnumerable<int> GetRandSeq() {
for (int i = 0; i < 30; i++) {
yield return rnd.Next(20, 60);
}
}
var items = GetRandSeq().ToArray();
int binsize = rnd.Next(100, 140);
return (items, binsize);
}
}
実行例
それでは、実行してみます。
改良版の勝ち:3708
改良版の負け:100
改良版の引分け:6192
確かに、改良されています。でも、結果が悪くなる場合もありますね。
前回のアルゴリズムAの改良版でも確認してみる。
ということは、前回のアルゴリズムAの改良版も、結果が悪くなる場合がありそうです。
そのため、前回示したアルゴリズムAの改良版に対しても、同じような確認コードを書いて確かめてみました。
改良版の勝ち:3745
改良版の負け:1240
改良版の引分け:5015
改良版の負けの割合が随分と多いですね。それでもトータルで見れば、アルゴリズムAにおいても、全体像が事前に把握できるのであれば、改良版を採用したほうが良いという結論になりますね。
４つのアルゴリズムを全部試して最良の解を採用する
ここまで書いてみて思いました。じゃあ、この４つのアルゴリズムを全部試してみて、一番良い結果を採用すればいいんじゃないかなと。
ビンパッキング問題のアルゴリズムについてちゃんと調べたわけじゃないので、もっと素晴らしいアルゴリズムがあると思いますが、
数学の専門家でもなんでもないプログラマーの僕には、このような泥臭いコードが似合っていると思います。
人手でやるんじゃ手間がかかってしかたありませんが、コンピュータにやらせるんだったら、あっという間に答えがみつかりますから、全然問題ありません。
ということで、以下のようなBinPackingMixedSolverクラスを定義しました。
class BinPackingMixedSolver : IBinPacking {
public int BinSize { get; set; }
public BinPackingMixedSolver(int size) {
BinSize = size;
}
public ICollection<ICollection<int>> Solve(int[] items) {
var solvers = new IBinPacking[] {
new BinPackingSolver21(BinSize),
new BinPackingSolver11(BinSize),
new BinPackingSolver1(BinSize),
new BinPackingSolver2(BinSize),
};
return solvers.Select(s => s.Solve(items))
.OrderBy(x => x.Count)
.First();
}
}
４つのアルゴリズムを全部試してみて、そのなかから最もビンの数が少ない結果を返しています。
こんな時にもLINQのSelectメソッド使えますね。便利です。
使い方のサンプル
最後に、BinPackingMixedSolverの使い方のサンプルを示します。
var data = new int[][] {
new int[] { 33, 61, 58, 41, 50, 21, 60, 64 },
new int[] { 33, 61, 58, 41, 50, 21, 60, 64, 34, 54, 65 },
new int[] { 33, 61, 58, 41, 50, 21, 60, 64, 23, 45, 67, 78, 89 }
};
foreach (var items in data) {
int binsize = 120;
var bp = new BinPackingMixedSolver(binsize);
var result = bp.Solve(items);
PrintResult(result);
}
PrintResultメソッドは、第１回で示したメソッドです。
前回試してみた、３つのデータで解を出してみました。
以下、実行結果です。
114: [64,50]
119: [61,58]
101: [60,41]
54: [33,21]
119: [65,54]
114: [64,50]
119: [61,58]
101: [60,41]
88: [34,33,21]
110: [89,21]
119: [78,41]
117: [67,50]
109: [64,45]
119: [61,58]
116: [60,33,23]
3つ目の結果は前回よりも良い結果になっています。
この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。