表/座位分配算法

我目前正在開發一個預訂系統，並且需要基於某些條件和預定義值爲公司參與者分配座位的算法。表/座位分配算法

的條件是：

從每個不同的公司，至少兩個參與者必須放置在相同的表。（鑑於該公司至少有2名參與者）
公司有競爭對手的定義。公司不能與競爭對手坐在同一張桌子上。

預定義的值是：

表和座位預定。
公司參與者和競爭對手的關係是預定義的。

實體的定義：

表： ID（中間體，PK），描述（字符串），號（INT），

TableSeat： ID（中間體，PK）， Number（Int）， TableID（FK）， CustomerID（Nullable Int，FK）

公司： ID（PK）名稱（字符串） DefaultNumberOfParticipants（INT） CompetitorID（FK）

Competior： ID（PK） CompanyID（FK） CompanyID2（FK）

所以，如果我，例如，有以下預設定義：

表：

表1具有6個座位
表2具有4個座位
表3具有6個座位
表4具有3個座位

公司/參加者：

Company1有3個參與者，沒有競爭對手
Company2 h作爲2名參與者和公司3作爲競爭對手
公司3有4名參與者和Company2的競爭對手的

我需要自動分配共有9人蔘加，從3家公司上4代表總數的19席。根據條件，公司2和公司3的參與者不能坐在同一張桌子上。此外，當一個參與者坐在桌旁時，他應該由同伴參與者陪同（如果可能的話）。

任何想法或指向一個合適的算法將不勝感激。謝謝。

來源

2014-10-30 MartinChristensen

如果你想快速編程，你可以嘗試'貪婪隨機'metaheuristics（GRASP）http://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_procedure – Seb 2014-10-30 13:01:24

你可以試試下面的變化對這個算法：Distributing players to tables

同樣的總體思路是對的過程依次在每個表中的每個座位，在座位是隨機的剩餘和有效的人。如果沒有這樣的人可用，則該算法終止而沒有結果（使其成爲所謂的Las Vegas算法）。

取決於有多少有效的解決方案，您可能必須在找到解決方案之前運行該算法幾百次，但這是正確的，因爲單次運行非常快：我估計，對於你給出的例子，你應該在不到一秒的時間內找到結果，至少比通過所有可能的排列進行徹底搜索要快得多。

沒有競爭對手2應在同一表中允許的條件可以很容易地執行：選擇下一人的時候，在桌子座位，只排除已經坐在那張桌子所有人的競爭對手。

另一種情況是，一個人應該最好與至少一個同事坐在一起是比較困難的。它仍然可以作爲一個硬性限制來實施，但我懷疑可能有很多情況不會產生任何結果。
因此，我想建議通過最初完全忽略這個條件來使這個條件成爲一個「軟約束」，但是通過給每個沒有與同事坐在一起的人頒發一個懲罰點來評估每個結果。

這保證即使在不是每個人都可以與同事坐在一起的情況下，您仍然可以獲得一個稍微可以接受的座位。

算法變爲：

//Place everyone at a table while avoiding seating competitors together 
for each table T: 
    UP = a randomly shuffled list of unseated people 
    for each person X from UP 
     While there still is at least one seat available at T AND 
      X is not a competitor of anyone already seated at T 
      seat X at T 

    if T still has one or more seats available 
     abort; //With the decisions taken so far, noone can be seated at T. This run has no result. 

//Complete seat configuration found. Award a penalty point for evey person not seated with a colleague. 
penaltyPoints = 0 
for each table T: 
    for each person X seated at T 
     If there is no other person at T that is from X's company 
     Add a penalty point.

運行該算法幾個（？十萬）次，並保持與結果的點球點數量最少。

來源

2014-10-31 19:39:31 Astrotrain

我覺得這個問題可以簡化爲圖的頂點着色。競爭對手公司的參與者連接在圖中。顏色的數量等於表的數量。還有一個附加約束條件是每個顏色/表格都有最大數量的節點與其相關聯。

至於同一公司至少有2人需要坐在同一張桌子上的問題，每當你爲一個新節點着色時，忍受同一公司的另一個節點具有相同的顏色，否則嘗試着色同一家公司的另一個節點具有相同的顏色。

來源

2014-10-30 13:33:40 navari

表/座位分配算法

回答

相關問題