posts - 403, comments - 310, trackbacks - 0, articles - 7
          
	
 
BlogJava ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理


          
		          		
	
          
	
          
		
			
          
			
          
		          		
		
			
          
				
					
	
          
		
          
			
          
				CLRS 習題 16.1-3 Interval-graph Coloring Problem
			
          
 			Posted on 2007-10-14 00:48 ZelluX 閱讀(1507) 評論(2)  編輯  收藏  所屬分類: Algorithm 
			
			


		
          
		
          問題：
          
已知一些活動的起止時間{Si}, {Fi}，把它們安排在若干個大廳中進行，要求任一大廳任意時間段內不能有兩項活動同時進行，求出所需的最少的大廳數。
          

          
分析：(from CLRS Instructor's Manual)
          

          
這是一個區間圖的著色問題(Interval-graph Coloring Problem)，用點表示活動，把時間沖突的活動連起來，然后進行點的著色，要求同一線段的兩端不能有相同顏色的點。
          

          
首先最容易想到的就是用書上的Greedy-Activity-Selector找出可安排在大廳1的最長序列，然后刪去這些活動，再次調用該方法，找出安排在大廳2的活動，以此類推。
          
復雜度O(n*n)
          

          
還有一個O(n*logn)的算法，甚至在起止時間都是比較小的數字時復雜度只有O(n)。
          

          
主要思想是依次遍歷每個活動，把它們安排到不同的大廳中。
          
維護兩張表，一張記錄當前時間t已經安排了活動的大廳，另一張記錄當前時間空閑的大廳
          
然后從頭掃描排序后的時間點序列（如果事件a的結束時間等于時間b的開始時間，那么前者應該排在后者后面）
          
碰到開始時間t，把該活動放到空閑列表的第一個大廳中（如果空閑列表為空則新加一個大廳），然后把該大廳放入已安排的大廳列表中；
          
碰到結束時間t，從已安排的大廳列表中移出相應大廳到空閑列表。
          

          
復雜度分析：
          
排序：O(n logn)，如果時間范圍有限制還可以做到O(n)
          
處理：O(n) 

          
	
          
	


          
	    
    

          

          評論
          
	
			
          
				
          
					
          
						# re: CLRS 習題 16.1-3 Interval-graph Coloring Problem  回復  更多評論
						  
					
          
					2007-12-12 11:11 by clseeyou
				
          
				
          活動選擇問題只是求解相容活動的最大數量,如下:

          解為2,最優解為(1)(3)

          (1) ---

          (2)-----

          (3)       --

          (4)      ----

          如果用你所說的方法求解區間圖著色問題,那么解為3:{(1)(3)}{(2)}{(4)}

          明顯可以看出最優解為2:{(1)(4)}{(2)(3)}

          該算法還是有問題的```
          
			
          
		
			
          
				
          
					
          
						# re: CLRS 習題 16.1-3 Interval-graph Coloring Problem  回復  更多評論
						  
					
          
					2007-12-12 11:59 by ZelluX
				
          
				
          我沒說后面是區間圖的著色問題的解法啊 @.@

          只是前面提了一下而已
          
			
          
		




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          



    







          
        
	




主站蜘蛛池模板：
舞阳县|
汉中市|
齐齐哈尔市|
克山县|
中卫市|
牙克石市|
襄城县|
凤翔县|
班玛县|
峨山|
蒲城县|
托克逊县|
桐柏县|
徐闻县|
临武县|
曲沃县|
平遥县|
遵义县|
兖州市|
汾阳市|
崇信县|
泰兴市|
漾濞|
威海市|
西藏|
济宁市|
桂平市|
永登县|
徐州市|
常宁市|
独山县|
英吉沙县|
藁城市|
淄博市|
隆回县|
河南省|
鹤峰县|
临沂市|
方正县|
托里县|
花垣县|