statview.cpp

求解静态TSP 的IGT算法

   return 0;
} 

void mapped()
{ int start,end,i,j,k,kt,t,disPlace,kDC,kC;  
  double temp_dis=0;
  i=rand()%xColony;
  j=rand()%xColony;
  if(i==j)return;
  if(dis_p[i]<dis_p[j])
  { t=i;i=j;j=t; }
  for(k=0;k<xCity;k++)temp[k]=colony[i][k];
  /////////////////

  start=rand()%xCity;
  end=(start+rand()%(xCity/2)+5)%xCity; //rand()%xCity;   //////////////////////
  kt=position(temp,colony[j][start]);                //部分映射一二位同
  disPlace=kt-start;
  if(temp[(kt+1)%xCity]==colony[j][(start+1)%xCity])
  { 
	if(start<end)
	 for(k=start;k<=end;k++)    
     { kDC=(k+disPlace)%xCity;
	   if(temp[kDC]==colony[j][k])continue;
	   t=position(temp,colony[j][k]);
	   temp[t]=temp[kDC];
       temp[kDC]=colony[j][k];
     }  
    else
	 for(k=start;k<=xCity+end;k++)    
     { kDC=(k+disPlace)%xCity; kC=k%xCity;
	   if(temp[kDC]==colony[j][kC])continue;
	   t=position(temp,colony[j][kC]);
	   temp[t]=temp[kDC];
       temp[kDC]=colony[j][kC];
     }  
  }
  else
  { if(temp[(kt-1+xCity)%xCity]==colony[j][(start+1)%xCity])
    { if(start<end)
	    for(k=kt=start;k<=end;k++,kt--)    
		{ kDC=(kt+xCity+disPlace)%xCity;
		  if(temp[kDC]==colony[j][k])continue;
	      t=position(temp,colony[j][k]);
	      temp[t]=temp[kDC];
          temp[kDC]=colony[j][k];
		} 
	  else
	    for(k=kt=start;k<=end+xCity;k++,kt--)    
		{ kDC=(kt+xCity+disPlace)%xCity; kC=k%xCity;
		  if(temp[kDC]==colony[j][kC])continue;
	      t=position(temp,colony[j][kC]);
	      temp[t]=temp[kDC];
          temp[kDC]=colony[j][kC];
		} 
    }   
    else return;
  } 

  for(j=0;j<xCity-1;j++)
    temp_dis=temp_dis+city_dis[temp[j]][temp[j+1]];
  temp_dis=temp_dis+city_dis[temp[0]][temp[xCity-1]];
  dis_p[i]=temp_dis;
  /*********/
  tempTest(i);
}

//''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
void LastCP()
{ int i,k,j1,j2,k1,k2,turn,length,sign[CITY]; double dc,temp_dis=0,change=0;

  for(k=0;k<xCity;k++)temp[k]=colony[ibest][k]; 
  for(turn=0;turn<xCity/10;turn++)      //可改
  {   for(k1=0;k1<xCity-1;k1+=rand()%4+1)     // rand()%9+1可改
      {  for(i=1;i<xColony;i++)
	     {  if(i==ibest)continue;
		    for(k=0;k<xCity;k++)sign[k]=0;
	        j1=position(colony[i],temp[k1]);
			k2=k1;j2=j1;
			for(length=0;length<xCity/3+10;length++)    // 70 xCity/3+10可改
			{  k2=(++k2)%xCity; j2=(++j2)%xCity; 
			   sign[temp[k2]]=1;
			   if(temp[k2]==colony[i][j2] && length>5)break;  // 5 xCity/10可改
			}
            if(temp[k2]!=colony[i][j2])continue;
            k=j1;
            do k=(++k)%xCity;
			while (sign[colony[i][k]]==1);
            if( (j1<j2 && k<j2) || (j1>j2 && (k>j1 || k<j2)) )continue;  
		    temp_dis=path(temp,k1,k2);
		    dc=path(colony[i],j1,j2);
		    if(temp_dis>dc)
			{  for(k=1;k<=length;k++) 
		         temp[(k1+k)%xCity]=colony[i][(j1+k)%xCity];
			   change+=dc-temp_dis;
			}  
	     }
     } 
  }
  if(change<0)
  {  for(k=0;k<xCity;k++)colony[ibest][k]=temp[k]; 
     dis_p[ibest]+=change;
	 sumbest=dis_p[ibest];

  }
}			

double path(int tmp[],int k1,int k2)
{ 	int j,t1,t2; double temp_dis=0;		
    if(k2>k1) 
		for(j=k1;j<k2;j++)
			temp_dis+=city_dis[tmp[j]][tmp[j+1]];
    else      
		for(j=k1;j<k2+xCity;j++)
		{   t1=j%xCity; t2=(j+1)%xCity;
		    temp_dis+=city_dis[tmp[t1]][tmp[t2]];
		}
	return temp_dis;
}

void CSTATView::Draw(CDC *pDC)
{ int i,j;

for(i=0;i<xCity;i++)
{  disDraw[i].x=(int)cityXY[i][0];
   disDraw[i].y=(int)cityXY[i][1];
 }
  
//int h=400;int w=600;
RECT rectClient;
GetClientRect(&rectClient);
//-------------------
int h=rectClient.bottom-rectClient.top;//求出视图的坐标范围
int w=rectClient.right-rectClient.left;

int minx,maxx,miny,maxy;
for(j=1,miny=disDraw[0].y,maxy=disDraw[0].y,minx=disDraw[0].x,maxx=disDraw[0].x;j<xCity;j++)
{
if(disDraw[j].x>maxx)maxx=disDraw[j].x;
if(disDraw[j].y>maxy)maxy=disDraw[j].y;
if(disDraw[j].x<minx)minx=disDraw[j].x;
if(disDraw[j].y<miny)miny=disDraw[j].y;
}

//___________________________________________
//disDraw为unsignt 型
for(int ha=0;ha<xCity;ha++)//-fminx  -fminy
{  disDraw[ha].x-=minx; //cityXY[ha][0]-=minx;
   disDraw[ha].y-=miny; //cityXY[ha][1]-=miny;
}
//____________________________________________

double  kx,ky,k;
kx=(float)(w)/(maxx-minx);ky=(float)(h)/(maxy-miny);
if(kx>ky)k=ky*0.8;
else k=kx*0.8;

//居中
int dx,dy; //int dx=100;dy=0;
dx=(int)(w-(maxx-minx)*k)/2;
dy=(int)(h-(maxy-miny)*k)/2;

for(i=0;i<xCity;i++){disDraw[i].x=(int)(k*(disDraw[i].x))+dx;disDraw[i].y=(int)(k*(disDraw[i].y))+dy;}//将图形坐标按比例缩放

//画点
CPen pen( PS_SOLID , 2, RGB(0,0,0) ); //设置画笔
pDC->SelectObject(&pen );               //设置画笔
for(i=0;i<xCity;i++)pDC->Ellipse(disDraw[i].x-2,disDraw[i].y-2,disDraw[i].x+2,disDraw[i].y+2);
//i=0;pDC->Ellipse(s[i].x-2,s[i].y-2,s[i].x+2,s[i].y+2);
pDC->SelectStockObject(BLACK_PEN );    //还原画笔
pen.DeleteObject();

i=0;//画线
pDC->MoveTo(disDraw[colony[ibest][i]].x,disDraw[colony[ibest][i]].y);
for(i=1;i<xCity;i++)
    pDC->LineTo(disDraw[colony[ibest][i]].x,disDraw[colony[ibest][i]].y);
pDC->LineTo(disDraw[colony[ibest][0]].x,disDraw[colony[ibest][0]].y);

CString str1,str2,str3;//写最短距离
str1.Format("distance : %f",sumbest);
pDC->TextOut(10,5,str1);
str2.Format("       time : %.2f s",(double)(timeNow-timeStart)/CLOCKS_PER_SEC);
pDC->TextOut(10,25,str2);

if(once==1){once=0;ltimepast=clock();}
str3.Format("%f",(double)(ltimepast-timeStart)/CLOCKS_PER_SEC  );
pDC->TextOut(10,-20,"    ");

if(flagRun==1)Main();

}

void CSTATView::OnMenuRun() 
{
	// TODO: Add your command handler code here

	if(strFilePath=="")
	{ flagRun=0;
	   AfxMessageBox("请打开数据源");
	  return;
	}
	flagRun=1;
	initialize();
    Invalidate(TRUE);

}

void CSTATView::OnMenuPara() 
{
	Node node;

	CDlgPara dlg;

    dlg.m_xColony=xColony;	
    dlg.m_xCity=xCity;
	dlg.m_maxGen=maxGen;
	dlg.m_NOCHANGE=NOCHANGE;
	dlg.m_probab1=probab1;
	dlg.m_probab2=probab2;
    dlg.m_edgeSpeed=edgeSpeed;	
	
	
	dlg.setVar(&node);

    if(dlg.DoModal()==IDCANCEL)return;
    UpdateData(FALSE);
	
	xColony=node.xColony;	
    xCity=node.xCity;
	maxGen=node.maxGen;
	NOCHANGE=node.NOCHANGE;
	probab1=node.probab1;
	probab2=node.probab2;
    edgeSpeed=node.edgeSpeed;

}

void CSTATView::OnFileOpen() 
{
 	// TODO: Add your command handler code here
    // flagOpen=1;
	char *sz="TSP Files(*.tsp)|*.tsp|Text Files(*.txt)|*.txt|All File(*.*)|*.*|";

	CFileDialog file(TRUE,"txt",TEXT(""),
		OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,sz);
    int response=file.DoModal();
    if(response==IDCANCEL)return;

    strFilePath=file.GetPathName();
	
	//int number=strFilePath.GetLength();
	//for(int i=0;i<number;i++)filePath[i]=strFilePath.GetAt(i);
    //AfxMessageBox(filePath);
	//if((fp=fopen(filePath,"r"))==NULL)
  FILE *fp;
    if((fp=fopen(file.GetPathName(),"r"))==NULL)
	{
		AfxMessageBox("无法打开文件!");
		strFilePath="";
        return;
	}

  CString tmp;
  int flagOpen=0;
  while(1)
  {  fscanf(fp,"%s",tmp);
     if(tmp=="EOF" || feof(fp))break;
     if(tmp=="DIMENSION" && flagOpen==0) 
	 {   fscanf(fp,"%s",tmp);
		 if(tmp==":")
		 {	 fscanf(fp,"%d",&xCity); 
		     flagOpen=1;
		 }
	 }
     if(tmp=="DIMENSION:" && flagOpen==0)
	 {   fscanf(fp,"%d",&xCity);  
		 flagOpen=1; 
	 }
     if(tmp=="NODE_COORD_SECTION" && flagOpen==1)
	 { 	 flagOpen=2; 
		 break; 
	 }
  }
  //AfxMessageBox("文件类去去瞧瞧去!");
  if(flagOpen!=2)
  {     AfxMessageBox("文件类型错误!");
        strFilePath="";
        return;
  }
  int j;  double x,y;
  for(j=0;j<xCity;j++)      // initialize cityXY[][]  
  { if(feof(fp))break;
	fscanf(fp,"%*d%Lf%Lf",&x,&y);
    cityXY[j][0]=x;
    cityXY[j][1]=y;
  }
  if(j<xCity)
  { AfxMessageBox("文件数据错误!");
    return;
  }
  fclose(fp);
  probab1=0.02;

}

void CSTATView::OnMenuShow() 
{
	// TODO: Add your command handler code here
	show=(show+1)%2;
}

void CSTATView::OnMenuPause() 
{
	// TODO: Add your command handler code here
    static int pau=0;
    if(pau==0)	flagRun=2;
    else  flagRun=1;
	pau=(pau+1)%2;
    Invalidate();
}

void CSTATView::OnMenuStop() 
{
	// TODO: Add your command handler code here
	flagRun=0;
	strFilePath="";
	Invalidate(TRUE);
}