1.1 列挙 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム
- すべての場合を数え上げ(enumeration)ることが膨大なので、それを省略することが本書の中心であるが、そうはいっても、数え上げたいことはある。n個の要素の順列は、
。この方法は
であって、限界は早い。
- 例として、複数の２次元座標空間上の点
の並び替えて、
が最小となるような順列
が欲しいものとして実装
- 順列をすべて調べる代わりに、端から順に整列を進め、最終的にすべての整列を達成する方法順に対象範囲を増やすときには、可能な全通りについて条件を確認する
public class EnumerationPath {public static void main(String[] args) {
double[][] data ={{1,0},{5,0},{3,0},{2,0},{6,0},{4,0}};
int[] p = MinimumCostPath(data);
for(int i=0;i<p.length;i++){
System.out.println("i " + i + " " + p[i]);
}
}
public static int[] MinimumCostPath(double[][] d){
int n=d.length;
int[] pi = new int[n];
for(int i=0;i<n;i++){
pi[i]=i+1;
}
int[] pip = MiscUtil.DeepCopyInt1(pi);
int x= n-1;
//System.out.println("x " + x);
boolean flag = true;
while(flag){
flag = false;
int k=minForEnumPath(n,x,pi);
//System.out.println("k " + k);
if(k<=n){
pi[x-1]=k;
double c1 = cost1(pi,d);
double c2 = cost1(pip,d);
if(x==n && c1<c2){
pip = MiscUtil.DeepCopyInt1(pi);
}
if(x<n){
pi[x]=0;
x++;
}
}
if(k==n+1){
x--;
}
if(x>=1){
//System.out.println("true x " + x);
flag = true;
}
for(int i=0;i<pip.length;i++){
System.out.println("pip i " + i + " " + pip[i]);
}
for(int i=0;i<pi.length;i++){
System.out.println("pi i " + i + " " + pi[i]);
}
System.out.println("n k x " + n + " " + k + " " + x);
}
return pip;
}
public static double cost1(int[] order,double[][] d){
double ret=0;
for(int i=0;i<order.length;i++){
for(int j=i+1;j<d[i].length;j++){
for(int k=0;k<d[i].length;k++){
// System.out.println("i order[i] " +i + " " + order[i]);
ret += (d[order[i]-1][k]-d[order[j]-1][k])*(d[order[i]-1][k]-d[order[j]-1][k]);
}
}
}
return ret;
}
public static int min(int[] d){
int ret=d[0];
for(int i=0;i<d.length;i++){
if(ret>d[i]){
ret = d[i];
}
}
return ret;
}
public static int minFromSubSet(int[] a,int[] b){
int ret=0;
int[] exist = new int[a.length];
for(int i=0;i<exist.length;i++){
exist[i]=1;
}
int exCnt=a.length;
for(int i=0;i<a.length;i++){
for(int j=0;j<b.length;j++){
if(a[i]==b[j]){
exist[i]=0;
exCnt--;
break;
}
}
}
int[] Ex = new int[exCnt];
int counter=0;
for(int i=0;i<exist.length;i++){
if(exist[i]==1){
Ex[counter]=a[i];
counter++;
}
}
//System.out.println("Ex len " + Ex.length);
ret = min(Ex);
return ret;
}
public static int minForEnumPath(int n,int x,int[] pi){
int ret=0;
int[] a = new int[n-pi[x-1]+1];
for(int i=0;i<a.length;i++){
a[i]=pi[x-1]+i+1;
//System.out.println("a[i] " + a[i]);
}
int[] b = new int[x-1];
//int[] b = new int[k];
for(int i=0;i<b.length;i++){
b[i]=pi[i];
//System.out.println("b[i] " + b[i]);
}
ret = minFromSubSet(a,b);
return ret;
}
}
