實現在表分發客人的算法座位

Question

可能重複：
Seat guests based on prioritized parameters

我一直在掙扎了一段時間，現在這個問題。我無法把頭圍住它。如果有人更聰明，或者有更多的算法和/或數學知識，可以向我解釋我應該如何着手，我會非常感激。

客戶端被安排坐在活動，從餐館到大型場館不同。我客戶的軟件的目標是向客人提供一封短信/電子郵件/紙質票據，表明客人在抵達活動時應該坐在哪裏。 （這應該客人坐在那裏）座椅必須手動控制，一些表是「VIP」等我工作的一種算法，可以讓他確定了一些參數，比如哪些公司做客屬於並幫助用戶客人可以說什麼語言。今天，座位過程是在大型白板上手工製作的（如果活動是1k +客人，則一次一個）。

我的工作就是自動執行此一點，不完全，但「足夠好」。我已經構建了一個可以直觀呈現桌子，椅子（座椅）和客人的應用程序。但是，最重要的功能仍然缺失;以便能夠根據用戶選擇的參數將客人分配到現有的桌子和座位。

參數是每個客人的任意數量的數據，例如：「39歲，男性，Redwine Corp，首席技術官，英語&意大利語」。用戶需要這些（所有客人都有相同的數據字段）並按重要性排序。每個參數也必須設置爲「接近」或「分開」。因此，例如，用戶可以控制所講同一種語言的客人應該彼此相鄰坐，但那些在同一家公司工作應該彼此分開就座。

鑑於此，我即將實現的函數定義如下所示：function getGuestSeatings(tables, seats, guests, parameters)並返回一個陣列，其中的嘉賓應該坐在哪個席位上。參數tables，seats和guests包含您的信息的選擇，但最重要的可能是X，椅子Y的。這與椅子連接的桌子上的信息相結合，應該足以計算出「足夠好」的客人坐姿配置。當然，parameters變量包含有關參數優先級的信息，以及該參數是「座位接近」還是「座位分開」參數。

我在問的問題是：什麼算法可以用來提供解決方案，以及如何實現它？數學答案可能沒有用，所以爲了安全起見，我建議使用代碼（JS/C/C＃）或僞代碼。

我給你一些更多的信息，可能會或可能不會填補空缺的解決方案（我將與您的評論的反饋在這裏補充）：

• 該表可以是橢圓形或長方形
• 如果沒有與標準（優先參數）相匹配的座位配置，那麼我仍然需要一個「足夠好」的解決方案，儘管它不會是最好的。我知道調查所有可能性可能會耗費內存
• 或許懶惰loade d某種基於點的樹系統可以滿足要求嗎？只是調查前景看好的路徑，忽略其他路徑......？

這裏是一個小樣，讓你的軟件背後的想法：

Answer 1

Simulated Annealing.

的想法是你的人座椅的初始分配，和你有一個「善」的功能。 你想最大化善良功能。粗略地說，你這樣做的方式是隨機改變人的座位，如果這導致了功能的更高價值，那麼你從那裏開始再做一次。 如果開關導致善良函數的值較低，您可能仍然會隨機接受它，這可以幫助您避免局部最大值。 這叫做Metropolis-Hastings。

你讓它運行數千次，看看你得到了什麼。

Answer 2

我會放在第一人在第一個表，然後從那裏，基於參數和優先級計算得分，每桌，每位客人。與該表格中其他人的語言匹配是正分數，乘以優先級（更大數字優先級是更高優先級），如果他們來自同一家公司或不同語言或其他因素將其分散出去，則將其作爲負分數。如果在得分後客人沒有足夠高的分數（或積極分數），則轉到下一張桌子，然後在那裏與客人再次嘗試，如果沒有客人，則將該客人放在那裏，或者將客人放在客房中幾桌之遙。重複每個客人。另一種方法可能是爲每位客人計算每個已分配客人的表的分數，無論這個客人獲得分配給該表的最高分數。如果所有分數都是負數，那麼如果可能的話，將它們移動到一個新的表格中，並與其他表格均勻分隔

只是一個想法，祝​​你好運。