貪婪的方法在這裏工作嗎？

假設有N組人和M個表。我們知道每個組的大小和每個表的容量。我們如何將人員與表格相匹配，以避免同一組中的兩個人坐在同一張桌子上？貪婪的方法在這裏工作嗎？

請問這個問題的貪婪方法的工作？（貪婪方法的工作原理如下：對於每張桌子，嘗試用不同組別的人「填充」它）。

來源

2012-01-07 Michael

不，至少不是沒有進一步檢查。考慮兩個表（容量1和2）和兩個組（大小1和2）。如果你第一次嘗試填滿第一張桌子，你可以選擇孤獨者，讓第二組中的兩個成員坐在一起。 – 2012-01-07 17:32:22

馬蒂亞斯：

我懷疑下面的貪婪方法的工作原理：首先是最大的羣體，採取各組分配每桌該組的一個人，採摘第一臺擁有最自由的席位。

確實。而tkleczek的論點的一小部分證明了這一點。

假設有一個解決方案。我們必須證明算法在這種情況下找到了解決方案。

這是空洞地真，如果組的數目是0。

對於感應步驟中，我們必須表明，如果有任何的解決方案，有一個其中最大組中的一個成員坐在各自的（最大組的大小）最大的桌子。

條件L：對於表格的所有對（T1，T2），如果T1和最大組的成員位於T1，則最大組的另一個成員位於T2。

讓S1成爲解決方案。如果S1滿足L，我們就完成了。否則，存在與T1 < T2成對的表（T1，T2），使得最大組的成員位於T1，但最大組的成員不位於T2。由於T2> T1，有一個成員坐在T2，但沒有在T1（或在T2有空位）。因此，這兩個人可以交換席位（或者最大組的成員可以移動到T2處的空閒位置），並且我們獲得解決方案S2，其中有更少的表違反L的表。由於只有有限數量的表，所以在有限的多個步驟之後我們找到了一個解決方案Sk滿足L.

歸納假設：對於N個組的所有星座和所有數目M的表，如果有解，算法將找到一個解。

現在考慮存在解決方案的（N + 1）組和M個表格的星座。通過以上所述，還有根據算法放置最大組的成員的解決方案。把它們放在那裏。這將問題簡化爲N個組和M'個表的可解的星座，這是通過每個歸納假設的算法求解的。

來源

2012-01-08 03:30:52

假設組和表可以是大小不等的，我不認爲貪婪方法所描述的作品（至少在沒有額外的規格）。假設你有一個2T1的表格和一個3T2的表格，以及3個組{A1}，{B1，B2}和{C1，C2}。如果我按照你的算法，T1會收到{A1，B1}，現在你剩下T2和{B2，C1，C2}，這是行不通的。然而存在解T1 {B1，C1}，T2 {A1，B2，C2}。

我懷疑下面的貪婪方法的工作原理：首先是最大的羣體，採取各組分配每桌該組的一個人，採摘第一臺擁有最自由的席位。

來源

2012-01-07 17:43:59 Mathias

你能證明它[修改後的方法]有效嗎？ – amit 2012-01-07 17:46:26

沒有證據，所以我寫了「嫌疑人」;我還找不到一個明顯的反例，但這並沒有說清楚。而「合理的想法」有一種方式可以以非顯而易見的方式用貪婪算法反彈...... – Mathias 2012-01-07 17:51:53

@amit給出的證明。 – 2012-01-08 03:31:42

以下貪心方法工作：

重複下列步驟，直到沒有座位左側：

選擇最大的羣體和最大的表
比賽從所選組一人所選表格
將組大小和表格大小減少1.

證明：

我們只需要證明，執行一個步驟之後，我們依然可以達到最佳的解決方案。

讓我們把最大的一組一個很酷的傢伙中的任何成員。假設有一個不同的最佳解決方案，其中沒有冷靜的傢伙坐在最大的桌子上。讓我們選擇坐在這個解決方案中最大桌子上的任何人，並稱之爲跛腳的傢伙。他必須屬於大小不超過酷組。所以還有另一張桌子，坐着一個很酷的傢伙，但沒有跛腳的傢伙。我們可以安全地交換跛腳和冷靜的人的座位，這也導致了最佳的解決方案。

來源

2012-01-07 20:14:44 tkleczek

貪婪的方法在這裏工作嗎？

回答

相關問題