算法学习笔记–贪婪算法

学习目标

如何处理不可能完成的任务：没有快速算法的问题学习近似算法，可以快速找到NP完全问题的近似解学习贪婪策略，一种非常简单的问题解决策略

什么是贪婪算法？

贪婪算法就是每一步都采取最优的做法。 也可以说是每一步都是选择的局部最优解。

背包问题

幂集

设有集合A，由A的所有子集（包括空集）组成的集合，称为A的幂集，记作2^A 。 所以特征选择就是一个幂集问题，很难找出最优的特征集合。

实现

集合覆盖 广播覆盖州的问题：以最少的广播覆盖所有的州

def function(): pass if __name__ == '__main__': states_needed = set(["mt","wa","or","id","nv","ut","ca","az"]) 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"]) final_stations = set() while states_needed: best_stations = None states_covered = set() for station, states_for_station in stations.items(): print 'station, states_for_station: ', station, states_for_station covered = states_needed & states_for_station if len(covered) > len(states_covered): best_stations = station states_covered = covered stations.pop(best_stations) states_needed -= states_covered print 'states_needed: ',states_needed final_stations.add(best_stations) print 'final_stations: ',final_stations