一条河把一个国家分为南北两边,每边分别有你=8个城市,且北岸在南岸必有一个友好城市。在友好城市之间要修建轮渡。由于天气原因,航线不能交叉。如友好城市对为(北->南),1->3,2->7,3->1,4->4,5->6,6->8,7->2,8->5.这边的修建方案力求使航线最多,设城市有2<=n<=1000.那位大哥能够提供一段程序或是一个算法啊,谢,给高分!!!

解决方案 »

  1.   

    对这道题的最一般想法是进行回溯,但是回溯对于数据规模达到5000的情况是不可行的。
         于是我们改变一下思路,将每对友好城市看成一条线段,则这道题的描述化为:有N条线段,问最少去掉多少条线,可以使剩下的线段互不交叉?
         顺理成章,删掉的线应该是和其它线交叉最多的,其"交叉数"最大。所谓"交叉数"是指某线与其它线的交叉情况,初始值为0,若和其它线交叉则加1所得的值。按"交叉数"从大到小删除线,直到所有线都不交叉为止。此时,我们要解决的问题有:1、如何计算交叉数?2、怎么删线?
         对第一个问题,以北岸为线的起点而南岸为线的终点;先将所有的线按照起点坐标值从小到大排序,按照每条线的终点坐标计算交叉数:求线I的交叉数J[I],则检查所有1..I-1条线,若线J( 1< = J < I )的终点值大于线I的终点值,则线I与线J相交。J[I]与J[J]同时加1。整个搜索量最大为5000 X 5000。 
         对第二个问题,将J数组从大到小排序,每删除一条线,则将与之相交的线的J值减1,重复这个过程,直到所有J值都为0。此时剩下的线则全不交叉。 
        如上数据,则可得下面结果:
    编号  南岸  北岸  交叉数 
    1 1 3 1 
    2 2 4 2 
    3 3 1 2 
    4 4 5 1 
    5 4 2 2 
        此时,2、3、5航线的交叉数都一样,如果删去的是5、3线,则剩下的1、2、5线互不相交,最多航线数为3;但如果删去的是2、3,则还要删去第5线才符合要求,此时的最多航线数为2,不是最优解。 
         于是,我们从上面的分析中再深入,将航线按起点坐标排好序后,如上所述,在本题中,只要线J的起点小于线I的起点,同时它的终点也小于线I的终点,则线J和线I不相交。因此,求所有线中最多能有多少条线不相交,实际上是从终点坐标值数列中求一个最长不下降序列。这就把题目转化为一个非常典型的动态规划题目了。 
         求最长不下降序列的规划方程如下:
         L(Si)=max{L(Sj)}+1;1< = j < i且 Sj < Si。 Si为航线的终点坐标值。
         如上数据可以得下解:
    编号  南岸  北岸  L值和前趋 
    1 1 3 1,0 
    2 2 4 2,1  
    3 3 1 1,0  
    4 4 5 3,2  
    5 4 2 2,3  
    非常明显,可以得出解为3,航线为4,2,1。 
        从以上分析过程可以得出:当我们拿到一道题时,不要急于求解,而应先将题目的表面现象一层层象剥竹笋一样去掉,只留下最实质的内容。这时再来设计算法,往往能事半功倍。