选择java 进入自由开放的国度

随笔 - 49, 文章 - 3, 评论 - 154, 引用 - 1
数据加载中……

stat the schema of solution

 

  1 /*------------------------------------------------------------------------
  2                         stat. the schema of solution
  3 --------------------------------------------------------------------------
  4 Programe for stat the schema of  QAP(quadratic assignment problem) solution.
  5 Language: C++
  6 Compiler: g++ or Visual C++ 6
  7     
  8     Author : han
  9     Date   : 2006-07-17
 10     Version: 1.0
 11 
 12     Email  : hongbohan@gmail.com
 13              210413024@suda.edu.cn
 14 
 15 THIS CODE CAN BE FREELY USED FOR NON-COMMERCIAL PURPOSE. YOU CAN
 16 USE IT OR MODIFY IT FOR YOU PAPER, BUT ANY USE OF THIS IMPLEMEN-
 17 TATION OR A MODIFICATION THE CODE MUST ACKNOWLEDGE THE WORK OF 
 18 HONGBO HAN. I'D SO BE PLEASED IF YOU SEND E-MAIL TO ME.
 19 ------------------------------------------------------------------------*/
 20 #include <iostream>
 21 #include <fstream>
 22 //#include <getopt.h>
 23 
 24 using namespace std;
 25 
 26 const long n_max = 400;
 27 typedef long permutation[n_max];
 28 typedef long p_matrix[n_max][n_max];
 29 
 30 void readfile(char* filename, int &n, int bn, p_matrix &);
 31 void print_matrix(long n, long row, p_matrix mp);
 32 void stat(long n, long row, p_matrix mp);
 33 
 34 int isViewProb = 0;                  //是否显示probability matrixx
 35 int isViewElem = 0;                  //是否显示elements  matrix
 36 float probabilityLevel = 0.0;         //模式的概率阀值
 37 int main(int argc, char *argv[])
 38 {
 39     char *filename;
 40     //char *filename = "scr20.p.fdc";
 41 
 42     int bestSolutionNum=0;             //统计的最优解数目
 43     int n;                             //问题规模
 44     permutation bestp;                 //最优解排列
 45     p_matrix    psol;                 //解排列矩阵
 46     
 47 
 48     int i;
 49 
 50     for (i = 0; i < n_max; i++) bestp[i] = 0;
 51 
 52 #if 1
 53   if (argc == 1)
 54   {
 55     cout << "stat. the schema of solution permutation" << endl
 56         <<  "----------------------------------------" <<endl
 57         <<  "usage:"<<endl
 58         <<  "-f  the filename of QAP result " << endl
 59         <<  "-bn the better solutions in the above filename " <<endl
 60         <<  "-wn the worst  solutions in the above filename " <<endl
 61         <<  "-bp the best permutation of the QAP instance, not sopported" << endl
 62         <<  "-q  whether viewing the probability matrix, default false 0" << endl
 63         <<  "-e  whether viewing the elements matrix, default fase 0" << endl
 64         <<  "-p  the probability level, default 0.5" << endl;
 65     return 0;
 66   }
 67   else
 68   {
 69     /*
 70        you must specify the filename and bn;
 71        if you want to stat. the worst solution schema, please specify the wn;
 72        if you want to compare the schema efficency to the best permutation,you
 73        should specify it through parameter: bp.
 74     */
 75     for (i = 1; i < argc; i++)
 76     {
 77        if (!strcmp(argv[i], "-f"))
 78            filename = argv[i+1];
 79        if (!strcmp(argv[i], "-bn"))
 80            bestSolutionNum = atoi(argv[i+1]);
 81        if (!strcmp(argv[i] ,"-q"))
 82            isViewProb = 1;
 83        if (!strcmp(argv[i], "-e"))
 84            isViewElem = 1;
 85        if (!strcmp(argv[i], "-p"))
 86            probabilityLevel = atof(argv[i+1]);
 87 
 88     }
 89   }
 90 #endif
 91   
 92     if (bestSolutionNum == 0) bestSolutionNum = 30;
 93     if (probabilityLevel == 0.0) probabilityLevel=0.5;
 94     //bestSolutionNum = int(argv[2]);
 95     
 96     if (bestSolutionNum > 400)
 97     {
 98        cout << "bestSolutionNum should <= 400" << endl;
 99        return 0;
100     }
101     //cout << filename << bestSolutionNum << endl;
102     //读入文件内容
103     readfile(filename, n, bestSolutionNum, psol);
104     //过滤数据条目
105 
106     //统计结果
107     stat(n, bestSolutionNum, psol);
108     //输出
109     //与最优解排列的比较
110     
111 
112   return 0;
113 }
114 
115 int isExistedInPm(int n, int bn, permutation &temp, p_matrix &pm)
116 {
117   int i,j, flag;
118   //如果距离不等,肯定不存在
119   
120   for (i = 0; i < bn ; i++)
121   {
122      flag = 1;
123      if (temp[0== pm[i][0]
124           && temp[n+1== pm[i][n+1]) 
125      {
126         //比较各位是否相等
127          for (j = 1; j <=n; j++)
128          {
129            if (temp[j] != pm[i][j]) flag = 0;
130          }
131 
132          if (flag) return flag; //有位不同,排列不一样
133      }
134   }
135   return 0;
136 }
137 
138 /*-----------------------------------------------------------------------
139                      从文件中读取数据
140 ------------------------------------------------------------------------*/
141 
142 void readfile(char *filename, int &n, int bn, p_matrix &pm)
143 {
144    //读取解排列
145     //数据格式为:距离:解排列:偏离
146    int i = 0, j= 0, k=0;
147 
148    permutation temp;                      //保存临时读入的数据,用于过滤
149    //char filename[] = "bur26a.p.fdc";
150    ifstream fp(filename);
151    
152    fp >> n;
153    cout << "n =" << n << endl;
154    char buffer[1024];
155    fp.getline(buffer, sizeof(buffer));
156 
157    for (i = 0; i <= bn; i++)
158    {
159        for (j = 0; j <= n + 1; j++)
160        {
161            //先读到temp中,然后检查是否存在与pm中,如果存在bn-1,否则,加入pm中
162            fp >> temp[j];           
163        }  
164       if (isExistedInPm(n, bn, temp, pm))    //过滤相同的记录
165          i--;
166       else
167       {
168         for (k = 0; k<=n+1; k++)  pm[i][k] = temp[k];
169       }
170            
171    }
172   print_matrix(n, bn, pm);   
173 
174 #if 0
175    while (fp.good())
176    {
177      int n;
178      char buffer[1024];     
179 
180      fp.getline(buffer, sizeof(buffer));
181      cout << buffer << endl;     
182 
183      //分割字符
184      char *p, *sp = buffer;
185      int nchars;
186      do
187      {
188        if ( (p = strchr(sp, ':')) == NULL)
189            p = sp + strlen(sp);
190        nchars = p - sp;
191        //if (sp > buffer) putchar(':');
192        printf("%.*s\n", nchars, sp);
193        sp = p + 1;
194      }while (*!= '\0');
195 
196      i++;
197      if (i == bn) break;
198    }
199 #endif  
200   
201 }
202 
203 void print_matrix(long n, long row, p_matrix mp)
204 {
205   int i,j;
206   for (i =0; i < row; i++)
207   {
208       for (j = 0; j <= n + 1; j++)
209           printf("%3d|", mp[i][j]);
210       cout << endl;
211   }
212 }
213 
214 int isInTemp(int size, int value, const int *temp)
215 {
216   int i;
217   for (i = 0; i <= size; i++)
218      if (temp[i] == value) return 1;
219   return 0;
220 }
221 
222 /*-----------------------------------------------------------------------
223                      统计结果
224 ------------------------------------------------------------------------*/
225 
226 void stat(long n, long row, p_matrix mp)
227 {
228   int i,j,k,m;
229   int *elements = new int[row*n];           //每位上的所有元素,不重复
230   int *freq = new int[row*n];               //每个元素的个数
231   int *temp = new int[row];                 //临时数组,保存每位上不重复的元素
232   int *schema = new int[n];                 //解模式
233   float *probability = new float[n];         //每位上放置的频率
234 
235   for (m = 0; m < row; m++) temp[m] = 0;    //初始化为0
236   for (m = 0; m < n*row - 1; m++); freq[m] = 0;
237 
238      //第一遍扫描,得到每位上的所有不重复的元素
239      for (j = 1; j <= n; j++)
240      {
241        //按列
242        m = 0;
243        for(k = 0; k< row; k++)
244        {
245          if (!isInTemp(k, mp[k][j], temp))
246          {
247            temp[k] = mp[k][j];
248            elements[(j-1)*row + m] = mp[k][j];
249            //cout << "elements[" << (j-1)*row + k << "]=" << elements[(j-1)*row + k] << endl;
250            m++;
251          }
252        }       
253       
254        //补齐数组elements
255        if (m < row) 
256            for (i = m; i < row; i++
257                elements[(j-1)*row + i] = 0;
258 
259        for (m = 0; m < row; m++) temp[m] = 0;    //初始化temp为0
260     
261      }
262    
263 if (isViewElem)
264 {
265    cout <<  "\n----------elements" << endl;
266    for (i = 0; i < row*n-1; i++
267    {
268      printf("%3d|",elements[i]);
269       if ( ((i + 1% row) == 0) cout << endl;
270    }
271 }
272 
273    //根据每位上不同的元素,得出他的频率
274    for (i =0; i < row*- 1; i++)
275    {
276      //elements中每row个元素代表第(i \ row)列上不同的元素集合,后面的用0填充
277      m = i / row; //第m列的元素
278      freq[i] = 0;     
279      
280      j=0;
281      if (elements[i])
282      for (j = 0; j < row; j++)
283      {
284        if (elements[i] == mp[j][m+1])
285         freq[i] = freq[i] + 1;
286      }
287    }
288 
289 if (isViewProb)
290 {
291    cout << "\n----------freq" << endl;
292    for (i = 0; i < row*n-1; i++
293    {
294       printf("%3d|",freq[i]);
295       if ( ((i + 1% row) == 0) cout << endl;
296    }
297 }
298    
299    //得出最大频率的元素,填入到相应的位置上
300    i = 1;
301    int maxFreq;
302    int subscript;
303    int flag = 0;
304    
305       j = 0;
306       for (j = 0; j < row*- 1; j=j+row)
307       {
308          //从fenq中得出最大的元素,将相应的elements中的值填入sechma[i]中
309          
310          m = j / row;  //第几列?
311          schema[m] = 0;
312          probability[m] = 0;
313          
314          k = 1;
315          //i = j;
316          flag = 0;
317          subscript = j;
318          //如果已经在schema中存在,下标加1
319          while (isInTemp(k, elements[subscript], schema))
320          {
321              subscript = j + 1;
322              //i++;
323          }
324          maxFreq = freq[subscript];
325          if (freq[subscript])
326          for (k = subscript; k < row; k++)
327          {
328            if (isInTemp(k, elements[j+ k -1 ], schema)) subscript = j + 1;
329            if (freq[j + k] > maxFreq
330                && !isInTemp(k, elements[j+k], schema))
331            {
332                maxFreq = freq[j+k];
333                subscript = j + k;
334                flag = 1;
335            }
336          }
337 
338          schema[m] = elements[subscript]; 
339          probability[m] = float(freq[subscript]) / row;
340       }
341   
342    cout << "\n----------schema" << endl;
343    for (i = 0; i < n; i++)
344    {
345      printf("%3d|",schema[i]);
346    }
347    
348    cout << "\n\n----------probability" << endl;
349    for (i = 0; i < n; i++)
350    {
351      printf("%3.2f|",probability[i]) ;
352    }
353    cout << endl;
354 
355    //print solution schema by probability
356    cout << "\n----------schema by probability" << endl;
357    for (i = 0; i < n; i++)
358    {
359      if (probability[i] >= probabilityLevel)
360          printf("%3d|", schema[i]) ;
361      else
362          printf("%3s""*|");
363    }
364    cout << endl;
365 
366 
367   
368   delete[] temp;
369   delete[] freq;
370   delete[] probability;
371   delete[] elements;
372 }

posted on 2006-07-17 17:03 soochow_hhb 以java论成败 以架构论英雄 阅读(1099) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。


网站导航: