algorithm - 搜索和匹配算法

Question

我正在尝试提出一种算法来执行以下操作:

在程序停止之前，我总共需要填充 12 个单元格。我有 3 行，每行有 4 列。

举个例子，让我用飞机来说明这一点。所以你有 3 行，每行有 4 列，你有靠窗/过道的座位。每排将有一个靠窗的座位，靠过道的座位，靠过道的座位和靠窗的座位(|WA AW| 就像飞机上的座位安排)。在每次迭代(不同的乘客组)中，都会有一定数量的乘客(在 1 到 12 之间)，我需要尽可能让他们坐在一起(Seat together)。我为下一组(每次迭代)执行此操作，直到程序停止(当我完成每个组时它会停止)。

例如，我有 3 位乘客(A、B 和 C)，A 想坐在靠窗的座位上，B 想坐在过道的座位上，C 想坐在靠窗的座位上。假设所有座位(全部 12 个)都有空位，我可以将它们放置为 |A# BC|或 |CB #A|并将座位标记为脏(这样我就不会再为下一位乘客选择相同的座位)。我为下一组(迭代)执行此操作。我不确定这个论坛是否合适，但如果有人能告诉我应该如何完成，我将不胜感激。
谢谢。

Answer 1

如果输入是按顺序进行的，并且假设座位数总是最多 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 个 bool 值的数组，说明每个 i 是否使用 seat_i(您可以将 2D (x,y) -> 1D (x)轻松)。然后你遍历各种可能性。如果对于这个乘客集 (A_1, A_2, .., A_k) 每个人都有一个座位，并且其余乘客都有座位，那么一个完整的座位是可能的。

所以传入的掩码，用英文来说，就是被占用的座位。因此，假设您将 (A_1, A_2, .., A_k) 安排在 (x_1, x_2, .., x_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，因此得名。对于乘客请求列表，您可能只需要跟踪哪个索引。