Algorithm 版 (精华区)

发信人: shs (花雨飘), 信区: Algorithm
标  题: Re: 平面点覆盖问题求教
发信站: 哈工大紫丁香 (Sat Sep  9 12:57:01 2000), 转信

这位仁兄可能没有仔细设计酸法，因而得出这种方法比随机去寻找的运算量
还要大的观点。我的酸法设计是这样的：

double distance( CPoint p1 , CPoint p2 )
{
        double dx=p1.x-p2.x , dy=p1.y-p2.y ;
        return sqrt( dx*dx+dy*dy ) ;
}

int** GetNear( CPoint* p , int n , double r )
//得到每个点的邻域 返回的pp[i]到pp[i+1]表示第i个点的邻域包含的点的序号
{
    int i , j , *pN , **pp , m ;
        int* pN = new int [n] ;
        memset( pN , 0 , n*sizeof(int) ) ;
        for( i=n ; i-- ; )
        for( j = i+1 ; j-- ; )
        {
            if( r>distance( p[i] , p[j] ) )
                {
                     pN[i]++ ; pN[j]++ ;
                }
        }
        
        for( i=n , m = 0 ; i-- ; m+=pN[i] ) ;

        pp = new int*[n+1] ;
        pp[0] = new int [m] ;

        memset( pN , 0 , n*sizeof(int) ) ;
        for( i=n ; i-- ; )
        for( j = i+1 ; j-- ; )
        {
            if( r>distance( p[i] , p[j] ) )
                {
                     pp[i][pN[i]++] = j ;
                         pp[j][pN[j]++] = i ;
                }
        }
        delete pN ;
        return pp ;
}

int Find( int**pp , int*p , int n )
//pp是上面函数得到的图的邻域。p[i]为第i个点的邻域中没被覆盖的点的个数
//返回选择的邻域的序号。如果是-1则所有点全部覆盖
{
     int max = 0 , select = -1 ;
     for( i = n ; i-- ;  )
         {
             if( p[i]>max ) select = i ;
         }
         if( select==-1 ) return -1 ;
         p[select] = 0 ;
         for( n = pp[i+1]-pp[i] ; n-- ; p[pp[i][n]]-- ) ;
}

int GetCover( CPoint* pPoint , int n , int* pCover , double r )
//得到n个点的距离为r的最小覆盖邻域, m为邻域数pCover为邻域序号
{
    int **pp = GetNear( pPoint , n , r ) ;
        int * p = new int [n] ;
        int m = 0 , i ;
        for( i = n ; i-- ; p[i] = pp[i+1]-pp[i] ) ;
        for( ; ; )
        {
            i = Find( pp , p , n ) ;
                if( i==-1 ) break ;
                pCover[m++] = i ;
        }
        delete p ;
        delete pp[0] ;
        delete pp ;
        return m ;
}
【 在 Hopen (开心小剑) 的大作中提到: 】
:   看似可行，但我觉得在实际运算中要获得包含元素最多的子集并不容易
: ，这种方法比随机去寻找的运算量还要大，比较可行的是在随机寻找邻域
: 头节点的时候加入一些启发信息，减少随机选取的盲目性。
--
※ 来源:　武汉白云黄鹤站 bbs.whnet.edu.cn. [FROM: 202.114.113.240] 
※ 修改:．shs 于 Sep  9 12:54:39 修改本文．[FROM: as.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: as.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: shs.bbs@bbs.whnet.ed]