C#でビンパッキング問題を解く(4)


[C#でビンパッキング問題を解く(1)](https://qiita.com/gushwell/items/65d348fa3a6261e65630)
[C#でビンパッキング問題を解く(2)](https://qiita.com/gushwell/items/e2d71f914fdaea60a3fa)
[C#でビンパッキング問題を解く(3)](https://qiita.com/gushwell/items/d09bda6cc2c408f4128d)

と続けてきましたが、いよいよ最終版のプログラムです。

## どうやって改良するか

[前回のコード](https://qiita.com/gushwell/items/d09bda6cc2c408f4128d)をさらに、改良し、より良い結果を得られるようにしたいと思います。

最終版のプログラムは、簡単に書けば、BinPackingMixedSolverで解を求めて、一番空きの少ないビンを最終回答として、残りの荷物に対して、BinPackingMixedSolverで解を求める。これを繰り返す、という処理です。

もう少し詳しく書くと、以下のような手順になります。


1. BinPackingMixedSolverで解を求める。これを仮の解とする。
2. 仮の解の中から一番空きの少ないビンを求め、これを確定解とする。
3. 仮の解から、確定したビンを取り除く。
4. すべてのビンが確定したら、処理を終わりにする。
5. 確定していないビンに詰まった荷物を取り出し、新たな荷物のリストを作成する。
6. この荷物のリストに対して、BinPackingMixedSolverで解を求める。
7. 2へ戻る。

## C#のコード最終版

これをコードにしたのが、以下のコードです。

```csharp
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;
    }
}
```

再帰処理でも書けますが、ここでは、上記手順で示したようにループ処理にしました。
このシリーズの最初に示したコードにくらべて、随分と効率が悪いアルゴリズムですが、今のコンピュータのパワーならば、問題ないと思います。

## どれくらい改良されたのか

どれくらい改良されたのか確かめたいと思います。
ここでは、[前回](https://qiita.com/gushwell/items/d09bda6cc2c408f4128d)で示したコード（4つのアルゴリズムの最善解を採用するコード）BinPackingMixedSolverと比較します。

```csharp
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)](https://qiita.com/gushwell/items/65d348fa3a6261e65630)で最初に示したバージョンBinPackingSolver1とも比べてみました。上記コードのBinPackingMixedSolverをBinPackingSolver1に変えるだけです。
こういったことが簡単に行えるのは、インターフェースIBinPackingを定義しておいたおかげですね。

##### 結果(BinPackingSolver1との比較)
```
改良版の勝ち:8177
改良版の負け:0
改良版の引分け:1823
```

wikipediaで示されていた「最も空きが多いビンに荷物を入れてゆく解法」に比べると、ずいぶんと改良されたことが確認できました。

---

この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。