3
我試圖解決以下問題：尋找最好的子
給定一個連通圖G =（V，E）和頂點牛逼∈V，我需要找到一個子圖G「=（V」 ，E'）其中t∈V'。 G'應該最大化一些目標函數並且最小化它包含的頂點數。
Max f(G')
Min |V'|
在這個多目標優化問題中，最大化f（G'）比最小化頂點數量更重要。
讓我們來看看實際情況類似的問題：
假設我們要設計的建築物，其中客戶端設備有一個固定位置的ad hoc無線網絡而且也只是連接到有線網絡的一個AP 。最初，我們在每個房間放置AP，並使用傳播模型計算可連接的AP以及它們提供覆蓋的客戶端設備。在這個初始分佈中，可能有幾個AP將覆蓋同一個客戶端設備，所以我們需要對其進行優化。
圖1紅點代表連接到所述有線網絡的AP點和黑點分別表示受影響的其餘部分。 AP之間的實線向我們展示了它們是如何連接的。
形成圖1中AP的連接的圖表示我們問題的連通圖G，連接到有線網絡的AP是節點t。優化代表這種初始網絡設計的圖表意味着找到一個包含連接到有線網絡的AP的子圖，並最大化覆蓋客戶端設備的百分比（Max f（G'）），以最大限度地減少AP的數量（Min | V'| ）。就像問題一樣，最大化客戶端設備的百分比是主要目標。
圖2，一種可能的解決方案。
使用蠻力算法，它似乎是一個NP完全性問題;找到最佳解決方案需要檢查所有可能的子圖（都包含節點t）並證明可能的解決方案。你有什麼想法？
如果我們專門研究這個問題，可以在O（n^3）中找到所有頂點最短路徑（使用f'作爲度量）並找到與其他頂點距離最小（最大）總和的頂點？並使用這個頂點作爲答案？ – Eugen
感謝Eugen，一個有趣的想法是找到所有使用函數作爲度量的頂點之間的最短路徑。注意我正在尋找一個子圖，而不是一個節點;我不明白你最後的問題。 –
看來我有點誤解了你的問題。好的，也許我會在接下來的幾天裏考慮這個問題。 – Eugen