組合せ最適化

読書

自分で書くなら組み合わせって書くけれど...。isbn:3540431543、を借りたので読んでみる。著作権を侵害しない程度にまとめてみる。遅々として進まない気もしつつ。というかまとめる回数が膨大な量になるのと、一日一回くらいしかここに書く気がしないことにより、詰んでる気もする。

ドリル穴あけ問題

xy平面上にN個の穴を開けたい。移動にかかるコストは、xの差分とyの差分のうち大きい方。(あるいはxの差分とyの差分など、色々な距離計算規則にすることができる。)このとき最小のコストを求めよ、という問題。


取り敢えずN点を順番に穴をあける他ないので、全通り列挙しましょう、というサンプル。導入ですね。N!あるわけですが...。

int path = new int[n];
int min = Integer.MAX_VALUE;
void create(int index) {
  if( index == n ) {
    if( validPath() ) { min = Math.min(min, getCost()); }
    return;
  }
  for(int i=0; i<n; ++i) {
    path[index] = i;
    create(index + 1);
  }
}
boolean validPath() { ... } // 同じ点を二回踏んでいないかチェック
int getCost() { ... } // 得られたパスのコストを計算

というようなパス列挙方式が一例として浮かぶけれど、これはN^Nなので明らかにN!よりも大きい。


で、まず一番自明なパス、0番目からN-1番目までを順番に巡るものから始める。x番目に巡回する点をKとするとKよりも大きい点で今までに到達していない点のうち最小のものでx番目を置き換える。後は使っていない点を若い順に巡回する。xより後続の点についてy番目の点を同様に...みたいにやる。という非常に分かりにくいアルゴリズムをやるとN!でパス列挙ができるよ、と書いてある。


実際には、N^Nのアルゴリズムをちゃんと枝を切りながら実行すればおよそN!になると思うので、そっちでいいと思うけれど、何が違うんだろう？

int path[] = new int[n];
boolean used[] = new boolean[n]; //**//
int min = Integer.MAX_VALUE;
void create(int index) {
  if( index == n ) {
    if( validPath() ) { min = Math.min(min, getCost()); }
    return;
  }
  for(int i=0; i<n; ++i) {
    if( used[i] ) { continue; } //**//
    path[index] = i;
    used[i] = true; //**//
    create(index + 1);
    used[i] = false; //**//
  }
}
boolean validPath() { ... } // 同じ点を二回踏んでいないかチェック
int getCost() { ... } // 得られたパスのコストを計算

こんな感じ。ソース中に強調表示とかやり方知らないので、差分のところに印だけ付けてみた。


いずれにせよ、どうせNが20とかになったら破綻するような類の問題なので、どっちでもいいけれど、N^NとN!は違うぞ、って言いたいだけの例だと思うので、ちゃんと枝を切るので許してもらうことにしようかなぁと、いきなり挫折してみたり...。