Excel-DNA で XLL をつくる（その17）

カテゴリーに「組合せ最適化」を謳ってるのに、それらしい記事を書いていないので・・・。
今回は、組合せを列挙する関数を記述してみたいと思います。
(元ネタは、この質問です⇒ Yahoo知恵袋で見つけた質問)
組合せ最適化の初歩～「組合せ列挙の問題」を取り上げてやり過ごします（最適化を含んでいませんが）

まず、問題を整理しておきましょう。

1. 複数の行と列からなる整数の入ったセル範囲が与えられる。
2. 目標値が与えられる。
3. 各列から一つの数値を選択し、それらの数値の合計が目標値と一致する組み合わせを列挙する。

さっそく 前回 作った「ひな型」を使って記述していきましょう。

（こんな感じ↓）

using System;
using System.Collections.Generic;
using System.Threading.Tasks;
using ExcelDna.Integration;</code>

public static class MyAddInClass
{
public static int AnsCount(object[,] range, int trg)
{
// 組合せ探索
CombiClass Combi = new CombiClass(trg, range);
List&lt;int[]&gt; AnsList = Combi.EnumCombi(range);
return AnsList.Count;
}

public static object[,] EnumCombi(object[,] range, int trg)
{
// 配列数式範囲参照処理
ExcelReference caller = (ExcelReference)XlCall.Excel(XlCall.xlfCaller);
int r_count = caller.RowLast - caller.RowFirst + 1;
int c_count = caller.ColumnLast - caller.ColumnFirst + 1;
object[,] result = new object[r_count, c_count];

// 組合せ探索
CombiClass Combi = new CombiClass(trg, range);
List&lt;int[]&gt; AnsList = Combi.EnumCombi(range);

// 配列サイズチェック
if (AnsList.Count &lt; r_count)
{
r_count = AnsList.Count;
}

// 戻り値生成処理
for (int r = 0; r &lt; r_count; r++)
{
for (int c = 0; c &lt; c_count; c++)
{
result[r, c] = AnsList[r][c];
}
}
return result;
}
}

public class CombiClass
{
private List&lt;int[]&gt; AnsList;
private readonly int target; // 目標値
private readonly int[,] table; // 探索対象配列
private readonly int r_count; // 配列の行数
private readonly int c_count; // 配列の列数

// コンストラクタ
public CombiClass(int trg, object[,] range)
{
// クラス変数を設定する
this.AnsList = new List&lt;int[]&gt;();
this.target = trg;
this.r_count = range.GetLength(0);
this.c_count = range.GetLength(1);
this.table = cast(range);
}

// 列挙メソッド
public List&lt;int[]&gt; EnumCombi(object[,] range)
{
Parallel.For(0, r_count, r =&gt;
{
int[] ans = new int[this.c_count]; // 暫定解配列
ans[0] = table[r, 0];
int sub_total = table[r, 0]; 　// 暫定化の合計値
seek(1, ref ans, sub_total); 　 // 再帰関数実行
});
return this.AnsList;
}

// 再帰関数
private void seek(int col, ref int[] ans, int sub_total)
{
if (this.c_count &lt; col + 1) return;
for (int r = 0; r &lt; r_count; r++) { if (sub_total + this.table[r, col] &gt; this.target) return;
int[] tmp = new int[this.c_count];
ans.CopyTo(tmp, 0);
tmp[col] = this.table[r, col];
if (sub_total + this.table[r, col] == this.target) AnsList.Add(tmp);
if (sub_total + this.table[r, col] &lt; this.target)
{
seek(col + 1, ref tmp, sub_total + this.table[r, col]);
}
}
}

//型変換
private int[,] cast(object[,] range)
{
int[,] arr = new int[this.r_count, this.c_count];
for (int r = 0; r &lt; this.r_count; r++)
{
for (int c = 0; c &lt; this.c_count; c++)
{
arr[r, c] = Convert.ToInt32(range[r, c]);
}
}
return arr;
}

}

組合せ探索のように、フラクタルというか金太郎アメというか(笑) ・・・ 相似的にネストされている問題を解く場合には、再帰処理を使うと容易に記述することができます。ここでは処理の開始にあたって、EnumCombiメソッド内で最初の列を Paralle.For で並列化したのち再帰関数に渡しています。並列処理が簡単に実装できるのも、Excel-DNA のメリットですからね(笑)

（実行するとこんな感じ↓）

今回取り上げた問題は規模が小さいので、上記のような基本的な処理のみのコードでも短時間で探索出来ますが、行数 x 列数 の規模が大きくなると爆発的に探索数が増加して処理時間がかかるのを体感できると思います。
このページ で示したような大規模な問題では数億年の処理時間がかかるでしょう。コードをチューニングしてどうすれば処理速度を改善できるか？ いじってみると面白いと思います♪

ところで、F# のような関数型言語は、並列化処理に向いているようですが今回のような組合せ探索の問題はどのように記述出来るのでしょう？Excel-DNA と F# の組合せは、とても興味のあるところです♪

では、また(笑)

今回作成したプロジェクトのダウンロードはこちら ⇒ EnumCombi.zip