?
??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?}