# 算法图解8-12 贪心 DP k近邻浅析 ### 贪心算法

```array = ['mt','wa','or','id','nv','ut','ca','az']
states_needed = set(array)
# 转换为集合
stations = {}
stations['kone'] = set(['id','nv','ut'])
stations['ktwo'] = set(['wa','id','mt'])
stations['kthree'] = set(['or','nv','ca'])
stations['kfour'] = set(['nv','ut'])
stations['kfive'] = set(['ca','az'])
stations_array = []
while states_needed:
bast_station = None
states_covered = set()
for station,state_for_station in stations.items():
# print(station,state_for_station)
covered  = state_for_station & states_needed

if len(covered) > len(states_covered):
bast_station = station
states_covered = covered
states_needed = states_needed - states_covered
# print(states_needed)

stations_array.append(bast_station) #最好的station

print(stations_array)
```
• 贪心算法思路:每步都选择最有解,从而达到整体最优解
• 不适用场景:背包问题/只能找到非常接近最优解的解法
```#递归实现
def find_station(states_needed):
if states_needed:
bast_station = None
states_covered = set()
for station,state_for_station in stations.items():
# print(station,state_for_station)
covered  = state_for_station & states_needed

if len(covered) > len(states_covered):
bast_station = station
states_covered = covered
states_needed = states_needed - states_covered

return  [bast_station] +find_station(states_needed)
else:
return []
print(find_station(states_needed))
```

2.将这个加入队列 3.更新未被覆盖区域 4.重复1-3

### NP完全问题

1. 元素较少运行速度快,元素越来越多速度会变得非常慢.
2. 涉及所有组合的通常是NP完全问题
3. 不能分割成小问题,需要考虑各种情况的
4. 问题涉及旅行商序列等的且难以解决的
5. 问题涉及广播台集合的
6. 问题可以转换为旅行商或者集合覆盖的问题的
```graph = {}
graph['a'] = {}
graph['a']['b'] = 3
graph['a']['c'] = 6
graph['a']['d'] = 1
graph['c'] = {}
graph['c']['a'] = 6
graph['c']['b'] = 2
graph['c']['d'] = 7
graph['b'] = {}
graph['b']['c'] = 2
graph['b']['d'] = 5
graph['b']['a'] = 3
graph['d'] = {}
graph['d']['c'] = 7
graph['d']['a'] = 1
graph['d']['b'] = 5

list_city_array=list(graph.keys())

def find_fast(graph,next_array):
if next_array:
finded_array = []
city = next_array.pop()
list_array = list(graph.keys())
cost = 0

finded_array.append(city)
while len(finded_array) < len(list_array):

low_cost = float('inf')
low_cost_city = None
for neibo in graph[city].keys():
if graph[city][neibo]<low_cost and neibo not in finded_array:
low_cost = graph[city][neibo]
low_cost_city = neibo

# print(low_cost)
cost += low_cost
finded_array.append(low_cost_city)

city = low_cost_city

mined =  min(find_fast(graph,next_array),cost)
return mined
else:

return float("inf")

print(find_fast(graph,list_city_array))
```

2.寻找这个城市最近距离的城市,且不再已查找列表 3.更新时间花费,将被查找城市加入已查找队列
4.以这个城市为起点查找最近距离城市 5.重复2-4

### 动态规划

```word_a = 'HISH'
word_b = 'VISTA'
cell = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
]
for i in range(len(word_a)):
for j in range(len(word_b)):
if word_a[i] == word_b[j]:
cell[i][j] = cell[i-1][j-1]+1
else:
cell[i][j] = 0
print(cell)
```

1. 循环遍历横向和纵向
2. 如果两个数据相同就等于左上角的值+1
3. 如果不相等就等于0

4. 需要在给定约束条件优化某种指标的时候,动态规划很有作用

5. 问题可以分散为子问题的时候,可以用动态规划解决
6. 每种动态规划方案都涉及网格
7. 单元格的值通常是你需要优化的值
8. 每个单元格都是子问题,因此你需要考虑如何将问题分解为子问题
9. 没有四海皆准的计算动态规划解决方案的公式

### k最近邻算法

```from numpy import *
import operator

#给出训练数据
def createDataSet():
group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
labels = ['A','A','B','B']
return group,labels
#通过KNN分类
def classify(input,dataSet,label,k):
#获取维度 x
dataSize = dataSet.shape
#和训练集维度相同的
dataSet_new=tile(input,(dataSize,1))
diff = dataSet_new-dataSet
sqdiff = diff**2 #求差值平方
# print(sqdiff)
squareDist = sum(sqdiff,axis=1)#行向量相加
dis = squareDist ** 0.5#开平方
print(
dis
)
sortedDistIndex = argsort(dis) #排序提取其索引
print(sortedDistIndex)
classCount = {}
for i in range(k): #选取k个邻居
#sortedDistIndex[i]的值为距离

voteLabel = label[sortedDistIndex[i]] #??最近邻居吗 这明显有问题
#get()第二个值是默认值为0
classCount[voteLabel] = classCount.get(voteLabel,0)+1
#给字典的value 自加

maxCount = 0
classes = 0
for key, value in classCount.items():
if value > maxCount:
maxCount = value
classes = key
return classes
# print(classCount)
if __name__ == '__main__':
group,labels = createDataSet()
k=3
input = array([1.1,0.1])
print(classify(input,group,labels,k))
```