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

Question

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

Answer 1

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

我们将展示Partition <=(P) L，因此这个问题是 NP-Hard 问题，并且没有已知的多项式解。

证明
设 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