算法學習筆記–貪婪算法

學習目标

• 如何處理不可能完成的任務：沒有快速算法的問題
• 學習近似算法，可以快速找到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