我正在尝试解决以下问题：
给定一个连通图 G = (V, E) 和一个顶点 t ∈ V，我需要找到一个子图 G'= (V', E')，其中 t ∈ V'。G' 应该最大化一些目标函数并最小化它包含的顶点数。
Max f(G')
Min |V'|
在这个多目标优化问题中，最大化 f (G') 比最小化顶点数更重要。
让我们检查一个有类似问题的实际情况：
假设我们必须在客户端设备具有固定位置并且只有一个接入点连接到有线网络的建筑物中设计一个自组织无线网络。最初，我们在每个房间放置一个 AP，并使用传播模型计算可以连接的 AP 以及它们提供覆盖的客户端设备。在这个初始分布中，可能有几个 AP 会为同一个客户端设备提供覆盖，因此我们需要对其进行优化。
图 1. 红点表示连接到有线网络的 AP，黑点表示其余的 AP。AP 之间的实线向我们展示了它们是如何连接的。
图 1 中形成 AP 连接的图表示我们问题的连接图 G，连接到有线网络的 AP 是节点 t。优化表示此初始网络设计的图意味着找到一个包含连接到有线网络的 AP 的子图，并最大化覆盖客户端设备的百分比 (Max f(G') ) 最小化 AP 的数量 (Min |V'| ）。与问题一样，最大化覆盖客户端设备的百分比是主要目标。
图 2. 一种可能的解决方案。
使用蛮力算法，这似乎是一个 NP-Completeness 问题；找到最佳解决方案需要检查所有可能的子图（都包含节点 t）并证明一个可能的解决方案。你有什么想法？