考虑冗余的极小碰集问题研究

针对海上采油平台可燃气体探测器布设优化问题，首先建立了一个精确理论模型；通过对精确理论模型进行降维、简化和数字化处理，得到一个近似应用模型，该模型可视为极小碰集问题的一个变体，即考虑冗余的极小碰集问题。证明了冗余度大于或等于2的极小碰集问题都是NP-完备的。结合探测器布设的应用背景，针对冗余度为2的问题设计了一个启发式算法，旨在保证冗余度的前提下，极小化所需探测器的数目。仿真结果表明，该算法可以在不显著增加或减少探测器安装数目的情况下，使得任何一个拟泄漏点在任何风向下发生泄漏，都可以至少被两个探测器探测到，从而大大提高平台的安全性。