Algorithm 版 (精华区)

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

下面的程序经过调试，可在任何c中测试运行
#include "memory.h"
#include "math.h"
#include "stdlib.h"
#include "stdio.h"

        #include "sys/timeb.h"
    _timeb t_e , t_b ;
        
        #define BEGINTIME _ftime(&t_b) ;
        #define _DF t_e.time-t_b.time+(t_e.millitm-t_b.millitm)*0.001 
        #define SHOWTIME _ftime(&t_e); printf("%fsecond\n",_DF);_ftime(&t_b);

class CPoint
{
public:
        int x , y ;
} ;
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 ;
        pN = new int [n] ;
        memset( pN , 0 , n*sizeof(int) ) ;
        for( i=n ; i-- ; )
        for( j = i ; 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] ;
        for( i=1 ; i<=n ; i++ ) pp[i]=pp[i-1]+pN[i-1] ;

        memset( pN , 0 , n*sizeof(int) ) ;
        for( i=n ; i-- ; )
        for( j = i ; 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 = -1 , select = -1 , i ;
     for( i = n ; i-- ;  )
         {
             if( p[i]>max )
                 {
                         select = i ;
                         max = p[i] ;
                 }
         }
         if( select==-1 ) return -1 ;
         i = select  ; p[i] = -1 ;
         int j , m ;
         for( n = pp[i+1]-pp[i] ; n-- ; )
         {
                 j = pp[i][n] ;
                 if( p[j]<0 ) continue ;
                 p[j] = -1 ;
                 for( m = pp[j+1]-pp[j] ; m-- ; )
                 { 
                        p[pp[j][m]]-- ;
                 }
         }
         return select ;
}

int GetCover( CPoint* pPoint , int n , int* pCover , double r )
//得到n个点的距离为r的最小覆盖邻域, m为邻域数pCover为邻域序号
{
        BEGINTIME
    int **pp = GetNear( pPoint , n , r ) ;
        printf( " getnear use " ) ;
        SHOWTIME
        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 ;
        }
        printf( " getcover use " ) ;
        SHOWTIME
        delete p ;
        delete pp[0] ;
        delete pp ;
        return m ;
}

main()
{
        CPoint *p ;
        int *pC ;
        int max ; 
        int r ;
        printf( "input point num " ) ;
        scanf( "%d" , &max ) ;
        printf( "input radius " ) ;
        scanf( "%d" , &r ) ;
        p = new CPoint[max] ;
        pC = new int[max] ;
        for( int i = 0 ; i<max ; i++ )
        {
                p[i].x = rand() ;
                p[i].y = rand() ;
        }
        
        int m = GetCover( p , max , pC , r ) ;
        printf( "%d\n" , m ) ;
        delete p ;
        delete pC ;
        return 0 ;
}
: 【 在 Hopen (开心小剑) 的大作中提到: 】
: :   看似可行，但我觉得在实际运算中要获得包含元素最多的子集并不容易
: : ，这种方法比随机去寻找的运算量还要大，比较可行的是在随机寻找邻域
: : 头节点的时候加入一些启发信息，减少随机选取的盲目性。

--
※ 来源:　武汉白云黄鹤站 bbs.whnet.edu.cn. [FROM: 202.114.113.240] 
※ 修改:．shs 于 Sep  9 12:54:45 修改本文．[FROM: as.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: as.hit.edu.cn]

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