咸糖记录编程的地方

念念不忘,必有回响。

目录
算法图解8-12 贪心 DP k近邻浅析
/  

算法图解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))

实现思路:
1.寻找覆盖未被覆盖区域最多的电台
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))

旅行商问题使用近似算法实现
* 基准条件:剩余被查找队列为空
* 递归条件:剩余查找队列不为空
1.从城市列表中获得一个城市
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
  • 需要在给定约束条件优化某种指标的时候,动态规划很有作用
  • 问题可以分散为子问题的时候,可以用动态规划解决
  • 每种动态规划方案都涉及网格
  • 单元格的值通常是你需要优化的值
  • 每个单元格都是子问题,因此你需要考虑如何将问题分解为子问题
  • 没有四海皆准的计算动态规划解决方案的公式

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[0]
    #和训练集维度相同的
    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))


标题:算法图解8-12 贪心 DP k近邻浅析
作者:xiantang
地址:http://xiantang.info/articles/2019/06/03/1559551164746.html

评论