algorithm - 解决规划问题

Question

我是 AI/算法领域的新手，目前正在尝试解决一个问题，到目前为止，我之前只在二维网格阵列上实现了 A* 路径查找。

问题是这样的:

考虑一个类(class)有 40 名学生(20 英尺，20 米)，他们的高度各不相同，并且有自己的座位偏好(行、列或两者)，教室有 50 个座位，每个学生必须占据一个座位，并且座位正在铺设输出如下:

[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]
[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]
[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]
[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]
[ ] [ ] [ ]   [ ] [ ] [ ] [ ]   [ ] [ ] [ ]

              [ WHITE BOARD ]

为了理想地让他们就座，已选出一个评分图:

1. 没有学生直接坐在前面:+4 分
2. 正前方的学生座位至少短 2 厘米:+4 分
3. 你旁边的学生座位是异性:+8分
4. 4个同性别学生占据一列:-10分
5. 从白板开始高度上升的列:+20 分
6. 根据个人喜好安排座位:+2 分

目标是获得尽可能多的分数。

我的想法是使用A*修改来适应当前的问题:

开始:所有学生下座

路径成本:转换后点的增量

目标:所有学生就座

这里的问题是，可能的最大分数是未知的，我可以预见程序可能会出现无法提前计划的情况，(程序可能会选择 +8 然后选择 +4，其中更好的方法是选择 +2，然后选择 +20)，我知道我可以寻找一定的深度，比如说 5 的深度。这引出了另一个问题:我应该使用什么深度？我真的不想访问所有可能的状态。

1.这种问题有多难？ (从解决迷宫的规模到解决国际象棋/围棋)

2.我是否在解决这个问题的正确道路上？

Answer 1

约束 6 看起来暗示这个问题可能是 NP-complete 或 NP-hard。这意味着:A* 算法在这方面不会(很好)工作，因为不可能(除非 P = NP)创建一个良好的可接受的启发式函数。 可接受 意味着启发式函数应该始终低估或等于最优解的分数，它永远不会高估。 如果您需要包含约束 6，我建议使用禁忌搜索、模拟退火或延迟接受等算法，这些算法在类似用例(例如 Dinner party seating)上效果很好。和 Course scheduling .

没有约束 6，我认为像 First Fit Decreasing 这样简单的东西算法可以被设计成最优的:

1. 所有偶数座位都给女性，所有奇数座位都给男性(如果没有足够的座位供一种性别使用，请添加另一种性别的座位)。独立安排。安排 1 种性别时，忽略另一种性别的座位。
2. 根据高度对 1 个性别组的所有学生进行排序。按递减高度一一分配。
3. 对于每一步，将最大的未分配学生分配到最高行的未分配座位(其次是左侧最多的座位)

尽管如此，约束 2 可能仍然不是最优的......您可能仍需要对其应用一些禁忌搜索或延迟接受。