搜索和匹配算法

我試圖想出一個算法來做到以下幾點：搜索和匹配算法

我共有12個格，我需要填補，直到程序停止。我有3行，每行有4列。

舉一個例子，讓我在飛機上進行說明。所以你有3排，每排有4列，你有窗戶/過道座位。每排會有一個靠窗座位，過道座位，過道座位和靠窗座位（| WA AW |就像飛機座位一樣）。在每次迭代中（不同組的乘客），都會有一定數量的乘客（介於1和12之間），我需要將它們放在一起最近（座椅在一起）。我爲下一個組（每次迭代）做這個，直到程序停止（當我完成每個組時，它將停止）。

例如，我有3名乘客（A，B和C），A想坐在窗口中，B要坐在過道上，C想坐在Window中。假設所有的座位（全部12個）都可用，我可以將它們放置爲| A＃BC |或| CB #A |並標記座位髒（所以我不會再選擇下一個乘客同樣的座位）。我爲下一組（迭代）做了這個。我不確定這個論壇是否正確，但如果有人能告訴我我應該如何完成，我會非常感激。
謝謝。

來源

2010-03-12 Tony

男人，如果只有我不在工作。這聽起來像一個有趣的問題。乘客坐下後可以移動嗎？ – ChaosPandion 2010-03-12 18:23:13

Oh jeez，我的TI-83在哪裏... – dclowd9901 2010-03-12 18:24:05

@mmyers - 我正在進行相同的編輯。 :) – ChaosPandion 2010-03-12 18:26:02

如果輸入按順序排列，並且假設座位數總是達到12，那麼在每個州（乘客組）都可以乘坐座位的方式只有2^12。您可以使用它來減少暴力/記憶解決方案的狀態數量。

僞代碼：

IsSeatingPossible(mask, passengers) = 
    if (no more passengers) return true 
    return IsSeatingPossible = 
     new_mask = mask + brute force on passenger constraints 
     if any IsSeatingPossible(new_mask, 
         passengers - just processed passengers)

更多說明：

掩模基本上是12個布爾陣列，說明seat_i是否採取對於每個i（你可以轉換2D (x,y) - > 1D (x)容易）。然後你重複可能性。如果這個乘客組(A_1, A_2, .., A_k)每個都有一個座位，並且其餘乘客有座位，則可以有一個完整的座位。

因此，傳入英文的面具就是坐席。假設您坐在(x_1, x_2, .., x_k)的座位(A_1, A_2, .., A_k)。有許多乘客可以乘坐的子集 - 以N choose k爲界，在這種情況下，它很小。這是你蠻橫的一部分。給定一個特定的(x_1, x_2, .., x_k)，這個座位是可能的，如果(x_1, x_2, .., x_k)與當前面罩沒有重疊（基本上沒有衝突座位），並且可以處理其餘的乘客請求，因爲新面罩只是設置添加當前的面具和(x_1, x_2, .., x_k)。（所採取的新套座位。）

這可能也可能不夠快。整潔的事情注意到，除了注意哪些座位被採取以及處理了哪些乘客之外，針對某個子問題的解決方案是相同的。因此，您可以通過使用memoization來簡化這個過程。這產生了一個O(N 2^N)空間解決方案。

該掩碼最好使用位掩碼來實現，特別是對於N = 12，因此名稱。對於乘客請求列表，您可能需要跟蹤哪個索引。

來源

2010-03-12 18:39:26 Larry

嗨拉里，所以，蠻力算法基本上是從基地（1名乘客）開始，看看是否有可能乘坐1名乘客並增加1名乘客，看看是否有可能乘坐2名乘客等等，直到一組中的總乘客x已經坐下。我在這裏沒有真正遵循的是new_maks，mask，以及爲什麼要在乘客限制上添加面具+蠻力？感謝您的時間。 – Tony 2010-03-15 14:15:16

我提出了一些解釋，讓我知道你是否需要更多。 – Larry 2010-03-16 02:05:12

如果它實際上只有12個單元，並且組大小事先已知，那麼動態編程可能是非常合適的。計算每組佔用席位（2^12）和每個k（0 < = k < = 12）是否可以適當地放置前k個組以恰好佔據該組席位。（作爲優化，k由組的大小決定。）最後，向後工作：如果我將最後一組放在這裏，我是否可以將其餘組放入座位中？等等。

來源

2010-03-12 18:37:48 user287792

這是Knapsack problem類型的一個實例，具有以前已知的解決方案。

來源

2010-03-12 18:47:08

搜索和匹配算法

回答

相關問題