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 (*p != '\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*n - 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*n - 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 }