algorithm - 在座位图中分配连续的座位

我必须编写一个在座位图中分配连续座位的算法。例如:在体育场中分配座位。座位图可以看作是一个 N 行 M 列的二维数组。系统必须为一起进行的预订分配连续的座位。由于没有向用户呈现座位图，系统应自动分配对应于每次购买的可用座位。除此之外，它应该以这样一种方式进行，使得座椅中的孔/间隙最小化。

最佳答案

找到一个完美的解决方案是 NP-hard 。看等价语言问题:L={((x1,x2,...,xk),n,m)} 其中 xi 是共同预订的门票数量，n,m 是体育场的大小。

我们将证明 Partition
证明
让 S=(x1,x2,..,xk) 作为分区问题的输入，让 sum=x1+...+xk看下面的减少:

Input: S=(x1,...,xk)
Output:((x1,...,xk),sum/2,2)

正确性:
如果 S 有一个分区，让它是 S1=(x_i1,x_i2,...,x_it) ，那么根据分区的定义， x_i1+...+x_it=sum/2 ，这样我们就可以在第一行插入 x_i1,..,x_it ，第二行插入其余部分，所以 ((x1,...,xk),sum/2,2) 在 L 中
如果 ((x1,...,xk),sum/2,2) 在 L 中，那么根据定义，有 t 个预订使得 x_i1,x_i2,...,x_it 形成完美的第一行，因此 x_i1+x_i2+...+x_it=sum/2 ，因此它是一个有效的分区，S 在分区问题中

结论:
由于 L 是 NP-Hard，并且您寻求的问题是该语言的优化问题，因此没有已知的多项式解决方案。对于精确的解决方案，您可以使用 backtracking [检查所有可能性，并选择最好的]，但这会花费很多时间，或者您可以尝试使用启发式解决方案，例如 greedy ，但不会对其进行优化。

编辑: 回溯解决方案 [伪代码]:

solve(X,n,m):
   global bestVal <- infinity
   global bestSol <- null
   solve(X,new Solution(n,m))
solve(X,solution):
   if (X is empty):
       gaps <- solution.numGaps()
       if (gaps < bestVal):
            bestVal <- gaps
            bestSol <- solution
       return
   temp <- X.first
   X.removeFirst()
   for i from 0 to m:
       solution.addToLine(i,temp)
       solve(X,solution)
       solution.removeFromLine(i,temp)
   X.addFirst(temp)

假设 Solution 是一个已实现的类，并且对于非法解决方案 [即一排人太多] numGaps() == infinity

关于algorithm - 在座位图中分配连续的座位，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8025931/