Python之贪婪算法

系统管理员 2022-02-20 09:22 281阅读 0赞

**NP完全问题：**  
找不到快速算法的问题。

**识别NP完全问题，以免浪费时间去寻找解决它们的快速算法：**  
没办法判断问题是不是NP完全问题，但还是有一些蛛丝马迹可循的。  
1、元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。  
2、涉及“所有组合”的问题通常是NP完全问题。  
3、不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。  
4、如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。  
5、如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。  
6、如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

在获得精确解需要的时间太长时，可使用近似算法（approximation algorithm），使用它们可快速找到NP完全问题的近似解。

**判断近似算法优劣的标准如下：**  
1、速度有多快；2、得到的近似解与最优解的接近程度。

**贪婪算法：**  
又称贪心算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。贪婪策略不能获得最优解，但非常接近。

**示例：广播台覆盖问题**

# 创建待覆盖州的列表，并转换为集合
    states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
    
    # 可供选择的广播台，使用散列表来表示，其中键为广播台名称，值为广播台覆盖的州。
    stations = {} 
    stations["kone"] = set(["id", "nv", "ut"]) 
    stations["ktwo"] = set(["wa", "id", "mt", "nn"]) 
    stations["kthree"] = set(["or", "nv", "ca"]) 
    stations["kfour"] = set(["nv", "ut"]) 
    stations["kfive"] = set(["ca", "az"])
    
    # 使用集合存储最终选择的广播台。
    final_stations = set()
    
    while states_needed: 									#如果待覆盖的州列表不为空，则继续循环
    	best_station = None 								#初始化选择的广播台
    	states_covered = set()  							#初始化覆盖的州
    	for station,states_for_station in stations.items(): #遍历所有广播台
    		covered = states_needed & states_for_station 	#获取待覆盖的州与该广播台覆盖州的交集
    		#选出覆盖最广的广播台
    		if len(covered) > len(states_covered): 			#限制每次while循环选择一个覆盖最广的广播台
    			best_station = station  					#将该广播台标记为被选择
    			states_covered = covered 					#将上面的交集州标记为被覆盖的州
    
    	states_needed -= states_covered 					#从待覆盖的州中去除已标记为被覆盖的州
    	final_stations.add(best_station)					#将选择的广播台添加到最终集合，并循环
    	del stations[best_station]							#删除已选择广播台，避免重复循环
    
    print(final_stations)									#打印最终选择广播台

**结果为：**

{'kone', 'kfive', 'ktwo', 'kthree'}