如何通过贪婪算法图解理解集合覆盖与NP完全问题？

本文共计1451个文字，预计阅读时间需要6分钟。

Hello，大家好，我是Dream，一个有趣的Python博主。小白一枚，多关照！入门必备知识：这片乐园从不缺乏天才，努力才是你最终入场券！最后，愿我们都能在看不到的地方闪闪发光。

Hello，大家好我叫是Dream呀，一个有趣的Python博主，小白一枚，多多关照 ?

入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！

最后，愿我们都能在看不到的地方闪闪发光，一起加油进步

“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~

第八章：贪婪算法

• ​​8.1集合覆盖问题​​
• ​​8.2NP完全问题​​

• ​​8.2.1旅行商问题​​
• ​​8.2.2如何识别Np完全问题​​

• ​​8.3小结​​
• ​​二级目录​​
• ​​三级目录​​
• ​​最后的福利​​

8.1集合覆盖问题

假如你办了个广播节目，要让所有的州的听众都能听到。在每个广播台播出都需要收费，因此你要保证尽可能少的广播可以播出，每个广播台都覆盖特定区域，不同的广播台覆盖区域可能会重叠。

如何找出覆盖所有州的广播台集合呢？我们可以采用贪婪算法。

近似算法

贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。

1.选出一个这样的广播台，即它覆盖了最多的未覆盖州。

2.重复第一步，直到覆盖了所有的州。