[算法，AHP层次分析]93数模B题之足球队排名(某校论文算法的实现).

93年试题B重述:

下表给出了我国12支足球队在1988-1989年全国足球级联赛中的成绩，要求:

1设计一个依据这些成绩排出诸队名次的算法，并给出该算法排名次的结果。

2把算法推广到任意N个队的情况.

3讨论:数据应具备什么样的条件，用你的方法才能排出诸队的名次.

球队比赛成绩表格这里就省略了:

我这里对北京大学获得一等奖的论文中的加以实现。

主要的思考方法就是层次分析法（AHP），可以去查相关的次料.

北大队给出的算法具有比较好的通用性.

算法步骤:

1）首先要构造的是一个关于比赛区成绩的正互反矩阵，这是这个算法中最重要的一步。

比赛的胜负场次作为主要因素，而净胜球则作为次要因素.

主要需要两个数据矩阵:

interWinTimes:

netWinGoals:

一个判断矩阵:

For i<-1 to n

For j<-1 to n

If(interWinTimes[i][j]=interWinTimes[j][i]) then

If netWinGoals[i][j]=0 then

a[i][j]=a[j][i]=1

continue;

End if

If netWinGoals[i][j]>0 then

a[i][j]=1

a[j][i]=1

End if

K=interWinTimes[i][j]- interWinTimes[j][i]

If k>0 then

根据k值设定相应的tmpB,用的是一个尺度判定的方法.

再根据Ti胜Tj每场净胜球数来决定tmpD

a[i][j]=tmpB+tmpD

a[j][i]=1/a[i][j]

End if

If interWinTimes[i][j]=-1 then

a[i][j]=a[j][i]=0

End if

End for

这里要指出是，发表的论文里在上述算法里并不能保证a是一个正互反对称矩阵.

最后还要再用一个处理来使得对角线上元素全为1，原因是本队和本队之前的实力比较一定是1。

接下来所做的就是一些成文的方法。

2）检查a可约性，用Washall算法求联通性即可。

3）构造输助矩阵a’(详情见程序)

4)再计算a’ 的主特征根maxLamda和主特征向量，这里用的是幂法.

参考:

http://blog.csdn.net/EmilMatthew/archive/2005/08/21/460657.aspx

5)根据主特征向量排列各队名次。

6）计算2h及r查卡方分布表得本算法的可信赖度.

好了，下面就是主要程序了，首先是输入数据:

//interWinTimesData.txt 各队彼此间互胜场次的数据，-1表示二者间没有比赛记录

12,12;

-1,1,1,3,1,1,0,1,2,0,-1,-1;

1,-1,1,1,0,1,0,0,1,0,-1,-1;

1,2,-1,1,1,1,1,1,1,1,-1,-1;

0,0,0,-1,0,0,0,1,0,0,-1,-1;

0,0,1,1,-1,0,-1,-1,-1,-1,1,0;

0,0,1,1,1,-1,-1,-1,-1,-1,-1,-1;

2,0,1,2,-1,-1,-1,2,3,2,1,1;

1,0,1,1,-1,-1,0,-1,1,1,1,0;

0,0,1,1,-1,-1,0,2,-1,2,1,1;

0,1,1,1,-1,-1,0,1,0,-1,1,1;

-1,-1,-1,-1,1,-1,0,0,0,0,-1,0;

-1,-1,-1,-1,0,-1,0,0,0,0,1,-1;

//netWinGoalsData.txt 各队净胜球数据，由于是对称的，所以只列出上三角部分，-1既表示二者之间没有比赛，同样也表示I对j的净胜球为-1,由于二者没有比赛记录是通过interWinTimesArr首先判定和处理的，所以I,j队没有比赛的情况会被首先挑出来令a[i][j]=a[j][i]=0.这里的-1不会造成二义性.

0,-1,5,2,1,-3,-1,5,0,-1,-1;

-1,2,0,1,0,0,2,-2,-1,-1;

2,1,3,-2,1,0,1,-1,-1;

-1,-1,-6,-1,-1,-1,-1,-1;

-1,-1,-1,-1,-1,0,0;

-1,-1,-1,-1,-1,-1;

3,5,5,2,2;

0,0,2,0;

4,1,1;

1,2;

-1;

/*核心程序段*/主要分成两个部分

步骤1：求特征向量。（算法步骤的1-4）

#include "Global.h"

#include "Ulti.h"

#include "Matrix.h"

#include "MyAssert.h"

#include "GraphAlgorithm.h"

#include <time.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

char *inFileName="inputData.txt";

input data specification

row,col;

//Arr

a11,a12,...;

, , , ,

an1,an2,...;

}

char *outFileName="outputData.txt";

#define DEBUG 1

void main(int argc,char* argv[])

{

FILE *inputFile;/*input file*/

FILE *outputFile;/*output file*/

double startTime,endTime,tweenTime;/*time callopsed info*/

int rowNum,colNum;

int i=0,j=0;/*iterator num*/

int flag;

Type k;

Type** netWinGoalsArr,** interWinTimesArr;

Type** ansArr,** aidAnsArr;

char* netWinGoalsData="netWinGoalsData.txt";

char* interWinTimesData="interWinTimesData.txt";

Type maxLamda;

Type tmpB,tmpD,tmpM;/*for temp use*/

int n;/*arr deminision for squre matrix*/

/*default input file open*/

if(argc>1)strcpy(inFileName,argv[1]);

assertF((inputFile=fopen(inFileName,"rb"))!=NULL,"input file error");

printf("input file open success\n");

/*default outpout file open*/

if(argc>2)strcpy(outFileName,argv[2]);

assertF((outputFile=fopen(outFileName,"wb"))!=NULL,"output file error");

printf("output file open success\n");

/*This function,automatically fullfill the task of

apply the mem for the 2d pointers. Perfect,right? :)*/

read2DArrFloat(&interWinTimesArr,&rowNum,&colNum,interWinTimesData);

twoDArrMemApply(&netWinGoalsArr,rowNum,colNum);

for(i=0;i<rowNum-1;i++)

{

for(j=i+1;j<rowNum-1;j++)

fscanf(inputFile,"%f,",&netWinGoalsArr[i][j]);

fscanf(inputFile,"%f;",&netWinGoalsArr[i][j]);

}

for(i=0;i<rowNum;i++)

netWinGoalsArr[i][i]=-1;

for(i=0;i<rowNum;i++)

for(j=0;j<i;j++)

netWinGoalsArr[i][j]=-netWinGoalsArr[j][i];

//output2DArrFloat(netWinGoalsArr,rowNum,colNum,outputFile);

/*mem apply*/

twoDArrMemApply(&ansArr,rowNum,colNum);

twoDArrMemApply(&aidAnsArr,rowNum,colNum);

#if DEBUG

printf("\n*******start of test program******\n");

printf("now is runnig,please wait...\n");

startTime=(double)clock()/(double)CLOCKS_PER_SEC;

/******************Core program code*************/

/*argu prepare*/

assertF(colNum==rowNum,"in test colNum!=rowNum");

n=rowNum;/*get the size of square matrix*/

fprintf(outputFile,"interWinTimesArr:\r\n");

output2DArrFloat(interWinTimesArr,rowNum,colNum,outputFile);

fprintf(outputFile,"netWinGoalsArr:\r\n");

output2DArrFloat(netWinGoalsArr,rowNum,colNum,outputFile);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

flag=0;

k=0;

if(interWinTimesArr[i][j]==-1)

{

//fprintf(outputFile,"level1%d,%d,\r\n",i,j);

ansArr[i][j]=ansArr[j][i]=0;

flag=1;

}

else if(interWinTimesArr[i][j]==interWinTimesArr[j][i]&&interWinTimesArr[i][j]!=-1&&interWinTimesArr[j][i]!=-1)

{

// fprintf(outputFile,"level2%d,%d,",i,j);

if(netWinGoalsArr[i][j]==0)

{

ansArr[i][j]=ansArr[j][i]=1;

flag=1;

}

else if(netWinGoalsArr[i][j]>0)

k=1;

}

if(k!=1)k=interWinTimesArr[i][j]-interWinTimesArr[j][i];

if(k>0&&!flag)

{

// fprintf(outputFile,"level3%d,%d,%f\r\n",i,j,k);

/*Element 1 ---b*/

if(k>=1&&k<=4)tmpB=2*k;

else if(k>4)tmpB=9.0;

/*Element 2---d*/

tmpM=netWinGoalsArr[i][j]/interWinTimesArr[i][j];

if(tmpM>2)tmpD=1;

else if(tmpM>=0)tmpD=0;

else tmpD=-1;

ansArr[i][j]=tmpB+tmpD;

ansArr[j][i]=1/ansArr[i][j];

}

fprintf(outputFile,"ansArr:\r\n");

for(i=0;i<n;i++)

ansArr[i][i]=1;

output2DArrFloat(ansArr,rowNum,colNum,outputFile);

/*step2*/

assertF(unKeYueMatirx(ansArr,n),"ansArr is not ke yue\n");//可约性判定,不可约则继续

/*step3*/

//构造辅助矩阵

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

if(i!=j&&ansArr[i][j]!=0)aidAnsArr[i][j]=ansArr[i][j];

else if(i==j)aidAnsArr[i][j]=(float)countDataTimesInRow(ansArr,i,0,n,n);

else if(ansArr[i][j]==0)aidAnsArr[i][j]=0;

}

fprintf(outputFile,"aidAnsArr:\r\n");

output2DArrFloat(aidAnsArr,rowNum,colNum,outputFile);

/*step three*/

powerMethodForLamda(aidAnsArr,n,"maxLamda.txt");

/******************End of Core program**********/

endTime=(double)clock()/(double)CLOCKS_PER_SEC;

tweenTime=endTime-startTime;/*Get the time collapsed*/

/*Time collapsed output*/

printf("the collapsed time in this algorithm implement is:%f\n",tweenTime);

fprintf(outputFile,"the collapsed time in this algorithm implement is:%f\r\n",tweenTime);

printf("\n*******end of test program******\n");

#endif

twoDArrMemFree(&aidAnsArr,rowNum);

twoDArrMemFree(&ansArr,rowNum);

twoDArrMemFree(&netWinGoalsArr,rowNum);

twoDArrMemFree(&interWinTimesArr,rowNum);

printf("program end successfully,\n you have to preess any key to clean the buffer area to output,otherwise,you wiil not get the total answer.\n");

getchar();/*Screen Delay Control*/

return;

}

输出数据.

ansArr:

1.000000,1.000000,0.500000,6.000000,2.000000,2.000000,0.250000,0.500000,5.000000,1.000000,0.000000,0.000000;

1.000000,1.000000,0.500000,2.000000,1.000000,2.000000,1.000000,1.000000,2.000000,0.500000,0.000000,0.000000;

2.000000,2.000000,1.000000,2.000000,2.000000,3.000000,0.500000,2.000000,1.000000,2.000000,0.000000,0.000000;

0.166667,0.500000,0.500000,1.000000,0.500000,0.500000,0.200000,0.500000,0.500000,0.500000,0.000000,0.000000;

0.500000,1.000000,0.500000,2.000000,1.000000,0.500000,0.000000,0.000000,0.000000,0.000000,1.000000,1.000000;

0.500000,0.500000,0.333333,2.000000,2.000000,1.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000;

4.000000,1.000000,2.000000,5.000000,0.000000,0.000000,1.000000,4.000000,6.000000,5.000000,2.000000,2.000000;

2.000000,1.000000,0.500000,2.000000,0.000000,0.000000,0.250000,1.000000,0.500000,1.000000,2.000000,1.000000;

0.200000,0.500000,1.000000,2.000000,0.000000,0.000000,0.166667,2.000000,1.000000,4.000000,2.000000,2.000000;

1.000000,2.000000,0.500000,2.000000,0.000000,0.000000,0.200000,1.000000,0.250000,1.000000,2.000000,2.000000;

0.000000,0.000000,0.000000,0.000000,1.000000,0.000000,0.500000,0.500000,0.500000,0.500000,1.000000,0.500000;

0.000000,0.000000,0.000000,0.000000,1.000000,0.000000,0.500000,1.000000,0.500000,0.500000,2.000000,1.000000;

aidAnsArr:

2.000000,1.000000,0.500000,6.000000,2.000000,2.000000,0.250000,0.500000,5.000000,1.000000,0.000000,0.000000;

1.000000,2.000000,0.500000,2.000000,1.000000,2.000000,1.000000,1.000000,2.000000,0.500000,0.000000,0.000000;

2.000000,2.000000,2.000000,2.000000,2.000000,3.000000,0.500000,2.000000,1.000000,2.000000,0.000000,0.000000;

0.166667,0.500000,0.500000,2.000000,0.500000,0.500000,0.200000,0.500000,0.500000,0.500000,0.000000,0.000000;

0.500000,1.000000,0.500000,2.000000,4.000000,0.500000,0.000000,0.000000,0.000000,0.000000,1.000000,1.000000;

0.500000,0.500000,0.333333,2.000000,2.000000,6.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000;

4.000000,1.000000,2.000000,5.000000,0.000000,0.000000,2.000000,4.000000,6.000000,5.000000,2.000000,2.000000;

2.000000,1.000000,0.500000,2.000000,0.000000,0.000000,0.250000,2.000000,0.500000,1.000000,2.000000,1.000000;

0.200000,0.500000,1.000000,2.000000,0.000000,0.000000,0.166667,2.000000,2.000000,4.000000,2.000000,2.000000;

1.000000,2.000000,0.500000,2.000000,0.000000,0.000000,0.200000,1.000000,0.250000,2.000000,2.000000,2.000000;

0.000000,0.000000,0.000000,0.000000,1.000000,0.000000,0.500000,0.500000,0.500000,0.500000,5.000000,0.500000;

0.000000,0.000000,0.000000,0.000000,1.000000,0.000000,0.500000,1.000000,0.500000,0.500000,2.000000,5.000000;

iteratorTime maxUk

0 5.000000

0 8.200000

0 13.500000

0 12.291298

0 12.149267

0 12.165865

0 12.185198

0 12.200407

0 12.212255

0 12.220396

0 12.225513

0 12.228601

0 12.230438

0 12.231518

0 12.232148

0 12.232513

0 12.232726

0 12.232847

0 12.232918

charactstic vector is:

0.493164,0.384973,0.515180,0.142782,0.207706,0.210439,1.000000,0.322516,0.395693,0.321313,0.186548,0.243590;//这个还不是主特征向量，主特征向量要将这里的每个元素都除以这个列向量各个元素之和.

the max lamda is:

12.232918.

步骤2(算法步聚的5-6)

//这里的工作相对轻松

#include "Global.h"

#include "Ulti.h"

#include "Matrix.h"

#include "MyAssert.h"

#include "GraphAlgorithm.h"

#include <time.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

typedef struct{

Type data;

int index;

}wVector;

void bubbleSort2(wVector* arr,int len);/*bubble sort algorithm*/

void swapArrData2(wVector* arr,int pos1,int pos2);

char *inFileName="inputData.txt";

input data specification

row,col;

//Arr

a11,a12,...;

, , , ,

an1,an2,...;

}

char *outFileName="outputData.txt";

#define DEBUG 0

void main(int argc,char* argv[])

{

FILE *inputFile;/*input file*/

FILE *outputFile;/*output file*/

double startTime,endTime,tweenTime;/*time callopsed info*/

int rowNum,colNum;

int i=0,j=0;/*iterator num*/

int flag;

int len;

Type h,Y;

Type sum;

Type k;

Type** ansArr;

Type* tmpList;

wVector* wList,* wList2;

char* listDataFile="wData.txt";

char* aDataAddress="aData.txt";

int n;/*arr deminision for squre matrix*/

/*default input file open*/

if(argc>1)strcpy(inFileName,argv[1]);

assertF((inputFile=fopen(inFileName,"rb"))!=NULL,"input file error");

printf("input file open success\n");

/*default outpout file open*/

if(argc>2)strcpy(outFileName,argv[2]);

assertF((outputFile=fopen(outFileName,"wb"))!=NULL,"output file error");

printf("output file open success\n");

/*This function,automatically fullfill the task of

apply the mem for the 2d pointers. Perfect,right? :)*/

readListFloat(&tmpList,&len,listDataFile);

/*adjusting*/

sum=0;

for(i=0;i<len;i++)

sum+=tmpList[i];

for(i=0;i<len;i++)

tmpList[i]/=sum;

wList=(wVector*)malloc(sizeof(wVector)*len);

wList2=(wVector*)malloc(sizeof(wVector)*len);

for(i=0;i<len;i++)

{

wList[i].data=tmpList[i];

wList[i].index=i;

}

read2DArrFloat(&ansArr,&rowNum,&colNum,aDataAddress);

for(i=0;i<len;i++)

printf("%d :%f\n",wList[i].index,wList[i].data);

//output2DArrFloat(ansArr,rowNum,colNum,outputFile);

bubbleSort2(wList,len);

for(i=len-1;i>=0;i--)

fprintf(outputFile,"%d:%f\r\n",wList[i].index+1,wList[i].data);

/*rever operator*/

j=len;

for(i=0;i<len;i++)

{ j--;

wList2[i].data=wList[j].data;

wList2[i].index=wList[j].index;

}

/*copy back*/

for(i=0;i<len;i++)

{

wList[i].data=tmpList[i]*sum;

wList[i].index=i;

}

h=0;

Y=0;

for(i=0;i<len;i++)

for(j=0;j<len;j++)

{

if(wList[i].data>wList[j].data&&ansArr[i][j]!=0)

h+=(ansArr[i][j]/(wList[i].data/wList2[j].data)-1)*(ansArr[i][j]/(wList[i].data/wList2[j].data)-1);

else if(wList[i].data==wList[j].data&&ansArr[i][j]!=0&&i>j)

h+=(ansArr[i][j]/(wList[i].data/wList2[j].data)-1)*(ansArr[i][j]/(wList[i].data/wList2[j].data)-1);

}

for(i=0;i<len;i++)

Y-=((float)countDataTimesInRow(ansArr,i,0,len,len))/2.0;

Y+=(float)((float)len*((float)len-1.0)/2.0);

fprintf(outputFile,"===========\r\n");

fprintf(outputFile,"h:%f\r\n",h);

fprintf(outputFile,"2h:%f\r\n",2*h);

fprintf(outputFile,"Y:%f\r\n",Y);

twoDArrMemFree(&ansArr,rowNum);

free(tmpList);

free(wList);

printf("program end successfully,\n you have to preess any key to clean the buffer area to output,otherwise,you wiil not get the total answer.\n");

getchar();/*Screen Delay Control*/

return;

}

void bubbleSort2(wVector* arr,int len)/*bubble sort algorithm*/

{

int i=0,j=0;/*iterator value*/

assertF(arr!=NULL,"In bubble sort,arr is NULL\n");

for (i=len;i>1;i--)

for(j=0;j<i-1;j++)

if(arr[j].data>arr[j+1].data)swapArrData2(arr,j,j+1);

}

void swapArrData2(wVector* arr,int pos1,int pos2)

{

Type tmpData;

int tmpIndex;

assertF(arr!=NULL,"In swapArrData,arr is NULL\n");

tmpData=arr[pos1].data;

tmpIndex=arr[pos1].index;

arr[pos1].data=arr[pos2].data;

arr[pos1].index=arr[pos2].index;

arr[pos2].data=tmpData;

arr[pos2].index=tmpIndex;

}

输出结果:

7:0.226045

3:0.116454

1:0.111477

9:0.089444

2:0.087021

8:0.072903

10:0.072631

12:0.055062

6:0.047569

5:0.046951

11:0.042168

4:0.032275

===========

h:23.464479

2h:46.928959

r:48.000000

对输出结果的说明:

7:0.226045表示第7号球队实力最强，其权值为0.226045.其余的类推，可知4号队实力最差.

最后的2h,r为计算卡方分布信赖度的数值。

与北大队结果的对比，排名上除了第8队和第10队略有出入（换了一下位置，由于权值实在很接近，可能是精度的问题）外，其余的排名全部正确.

2h北大队结果为47.56，

R为48

我这里也相差不大，主要是幂法在计算误差及初始向量的选定上的不同多少会对结果造成点小影响.

尽管是看了别人的论文后对其进行一下实现，但我对得到的这个结果还是满意的。：）