随笔-141  评论-9  文章-3  trackbacks-0
此题就是是求费马点,可以用到模拟退火算法

模拟退火的主要思想是一开始现在一个大范围内游走,逐渐减小搜索范围,最后找到解
我的程序是令马尔科夫链为200(即每次循环进行200次探索),初始温度为40(随机走若干个t步),衰减量为1(每次t--),则当温度降为0时,即找到答案

/*
ID: lorelei3
TASK: fence3
LANG: C++
*/


#include 
<fstream>
#include 
<ctime>
#include 
<cmath>

using namespace std;

const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};
const int MAXN = 160;

ifstream fin(
"fence3.in");
ofstream fout(
"fence3.out");

double p[MAXN][4];

int n;
void input(){
    fin
>>n;
    
for(int i=0; i<n; ++i){
        fin
>>p[i][0]>>p[i][1]>>p[i][2]>>p[i][3];
        p[i][
0]*=10; p[i][1]*=10; p[i][2]*=10; p[i][3]*=10;
    }

    srand(time(NULL));
}


inline 
int min(int a, int b){
    
return a<b?a:b;
}


inline 
int max(int a, int b){
    
return a>b?a:b;
}


double compute(int x, int y){
    
double ret=0;
    
for(int i=0; i<n; ++i){
        
int x1=p[i][0], y1=p[i][1];
        
int x2=p[i][2], y2=p[i][3];

        
if(y1==y2){
            
int minx=min(x1,x2), maxx=max(x1,x2);
            
int yy=y1;
            
if(x>=minx&&x<=maxx)
                ret
+=abs(yy-y);
            
else if(x>maxx)
                ret 
+= sqrt((y-yy)*(y-yy)+(x-maxx)*(x-maxx));
            
else
                ret 
+= sqrt((y-yy)*(y-yy)+(x-minx)*(x-minx));

        }
else if(x1==x2){
            
int miny=min(y1,y2), maxy=max(y1,y2);
            
int xx=x1;
            
if(y>=miny&&y<=maxy)
                ret
+=abs(xx-x);
            
else if(y>maxy)
                ret 
+= sqrt((y-maxy)*(y-maxy)+(x-xx)*(x-xx));
            
else
                ret 
+= sqrt((y-miny)*(y-miny)+(x-xx)*(x-xx));
        }

    }

    
return ret;
}


int x,y;
double ans;
void sa(){
    x
=p[0][0], y=p[0][1];
    
int t=40, ma=200, LEN=5;
    ans 
= compute(x,y);
    
    
while(--t){
        
for(int i=0; i<ma; ++i){
            
for(int j=0; j<4++j){
                
int d = rand()%LEN;
                
int tx = x+dx[j]*d*t;
                
int ty = y+dy[j]*d*t;
                
if(tx>=0 && ty>=0 && tx<=1000 && ty<=1000){
                    
double tmp = compute(tx,ty);
                    
if(tmp<ans){
                        ans
=tmp, x=tx, y=ty;
                    }

                }

            }

        }

    }

}


void output(){
    fout.setf(ios::
fixed,ios::floatfield);
    fout.precision(
1);
    fout
<<(double)x/10<<" "<<(double)y/10<<" "<<ans/10<<endl;
}


int main(){

    input();
    sa();
    output();

    
return 0;
}

posted on 2011-02-09 13:44 小阮 阅读(730) 评论(3)  编辑 收藏 引用 所属分类: USACO

评论:
# re: USACO 5.2.2 Electric Fences (模拟退火算法) 2011-09-21 16:55 | 匿名
模拟退火算法能将得再详细点么 谢谢  回复  更多评论
  
# re: USACO 5.2.2 Electric Fences (模拟退火算法) 2011-09-21 17:17 | 匿名
我想问问那个d值和len值有什么作用
你不是已经拿一个温度作为大致搜索范围了么
d值是加入随机因素么 是的话你那个len值是根据什么怎么选的  回复  更多评论
  
# re: USACO 5.2.2 Electric Fences (模拟退火算法)[未登录] 2015-08-04 21:45 | xixi
666@匿名
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理