單獨組

Question

我有一羣人。我需要儘可能移動至少有一名同組成員的組。

實施例：

GroupA - John, Bob, Nick 
GroupB - Jack, Nick 
GroupC - Brian, Alex, Steve 

正如你可以看到組A和組B重疊（它們都包含尼克） 我需要一種算法來設定基作爲GroupA-> GroupC->組B

謝謝

Answer 1

這取決於您如何完全確定問題 - 具有重疊和成本以及事物。

這可能會降低到Travelling salesman problem - 你可以設置邊權重爲0，如果組i和j沒有任何共同之處，以及一些功能f(i,j)依賴於它們之間的共同項目的數量。然後，你需要一個從一個組到最後一個組的列表，每個組訪問一次，最小化一些重疊功能。

你或許可以（與問候真的取決於你的意思是具體怎麼用的「最遠越好」，競重疊）減少TSP一個版本的這個類似。

不幸的是，這是NP-complete，這意味着你應該開始尋找的東西，是「足夠好」。

Answer 2

此問題不具有唯一的，甚至有意義的解決方案，如果你有任意組。例如，請參閱：

GroupA = {Alice, Bob} 
GroupB = {Bob, David} 
GroupC = {David, Alice}