C#でビンパッキング問題を解く(1)
C#でビンパッキング問題を解く(2)
C#でビンパッキング問題を解く(3)
と続けてきましたが、いよいよ最終版のプログラムです。
どうやって改良するか
前回のコードをさらに、改良し、より良い結果を得られるようにしたいと思います。
最終版のプログラムは、簡単に書けば、BinPackingMixedSolverで解を求めて、一番空きの少ないビンを最終回答として、残りの荷物に対して、BinPackingMixedSolverで解を求める。これを繰り返す、という処理です。
もう少し詳しく書くと、以下のような手順になります。
- BinPackingMixedSolverで解を求める。これを仮の解とする。
- 仮の解の中から一番空きの少ないビンを求め、これを確定解とする。
- 仮の解から、確定したビンを取り除く。
- すべてのビンが確定したら、処理を終わりにする。
- 確定していないビンに詰まった荷物を取り出し、新たな荷物のリストを作成する。
- この荷物のリストに対して、BinPackingMixedSolverで解を求める。
- 2へ戻る。
C#のコード最終版
これをコードにしたのが、以下のコードです。
class BinPackingSolver : IBinPacking {
public int BinSize { get; set; }
private BinPackingMixedSolver _solver;
public BinPackingSolver(int size) {
this.BinSize = size;
_solver = new BinPackingMixedSolver(size);
}
// ビンに詰められている全ての要素を順に取り出す
public IEnumerable<int> GetSequence(ICollection<ICollection<int>> list) {
foreach (var bin in list)
foreach (var n in bin)
yield return n;
}
public ICollection<ICollection<int>> Solve(int[] items) {
List<ICollection<int>> result = new List<ICollection<int>>();
// 一旦答えを求める
var binsList = _solver.Solve(items);
while (true) {
// 空きの小さい順に並べ替え、
// 空きが最も小さいビンを最終解答領域(result)へ入れる（確定）
var bin = binsList.OrderByDescending(b => b.Sum())
.First();
result.Add(bin);
// listから確定したビンを取り除く
binsList.Remove(bin);
// 残ったビンは無いので、処理終了
if (binsList.Count == 0)
break;
// 残ったビンに入っている項目で、再度解を求める
binsList = _solver.Solve(GetSequence(binsList).ToArray());
}
return result;
}
}
再帰処理でも書けますが、ここでは、上記手順で示したようにループ処理にしました。
このシリーズの最初に示したコードにくらべて、随分と効率が悪いアルゴリズムですが、今のコンピュータのパワーならば、問題ないと思います。
どれくらい改良されたのか
どれくらい改良されたのか確かめたいと思います。
ここでは、前回で示したコード（4つのアルゴリズムの最善解を採用するコード）BinPackingMixedSolverと比較します。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BinPackingApp {
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 BinPackingMixedSolver(binsize);
var r1 = bp1.Solve(items);
var bp2 = new BinPackingSolver(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}");
}
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);
}
}
}
ランダムに生成したデータで検証しています。以下、この結果です。
結果(BinPackingMixedSolverとの比較)
改良版の勝ち:1500
改良版の負け:0
改良版の引分け:8500
おおっ、確かに良い結果が得られました。
BinPackingSolverの中では、BinPackingMixedSolverを使っていますから、当たり前なのですが、改良版のBinPackingSolverが負けることはありません。
C#でビンパッキング問題を解く(1)で最初に示したバージョンBinPackingSolver1とも比べてみました。上記コードのBinPackingMixedSolverをBinPackingSolver1に変えるだけです。
こういったことが簡単に行えるのは、インターフェースIBinPackingを定義しておいたおかげですね。
結果(BinPackingSolver1との比較)
改良版の勝ち:8177
改良版の負け:0
改良版の引分け:1823
wikipediaで示されていた「最も空きが多いビンに荷物を入れてゆく解法」に比べると、ずいぶんと改良されたことが確認できました。
この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。