解决规划问题

Question

我是AI/ algorithm领域的新手，目前正试图解决一个问题，到目前为止，我只在2d网格数组上实现了A*路径查找。

问题是这样的：

假设每班40人(20楼，20米)，身高不同，有自己的座位偏好(排、列或两者都有)，以及一个教室50个座位，每个学生必须占有一个座位，座位排列如下：

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

              [ WHITE BOARD ]

在理想的情况下，我们选择了一个得分图表来安排他们的位置：

1. 不允许学生直接坐在前面：+4分
2. 直接坐在前面的学生座位缩短了至少2cm :+4点
3. 你旁边的学生座位是异性的：+8分
4. 4名同性别学生占据一栏：-10分
5. 从白板上上升高度的列：+20点
6. 根据个人喜好的座位：+2分

目标是尽可能多的得分。

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

起跑:所有学生下课

路径成本:过渡后点数的增加

目标:全体学生就位

这里的问题是，最大可能的点是未知的，我可以预见，可能会出现这样的情况，即程序没有提前计划(程序可能选择+8，然后再加上+4，更好的方法是选择+2，然后再加上+20)，我知道我可以寻找一定的深度，比如5。这就引出了另一个问题:我应该使用的深度是多少？我真的不想访问所有可能的州。

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

2.我是否走上了解决这一问题的正确道路？

Answer 1

约束6看起来意味着这个问题可能是NP-完全的或NP-硬的。这意味着: A*算法对此不起作用，因为不可能(除非P= NP)创建一个很好的可接受的启发式函数。可容许性意味着启发式函数应该总是低估或等于最优解的分数，它从不高估。如果您需要包含约束6，我建议使用诸如禁忌搜索、模拟退火或延迟接受等算法，这些算法在类似的用例(如宴会座位和课程调度 )上很好地工作。

在没有约束的情况下，我认为像一次拟合递减算法这样简单的东西可以设计成最优的：

1. 所有偶数席位都属于女性，所有奇数席位都属于男性(如果没有足够的席位容纳1种性别，则在另一种性别中添加溢出)。两人都要独立安排。在排定一个性别时，忽略另一个性别的席位。
2. 根据身高对一个性别组的所有学生进行排序。把它们一个接一个地分配给下降的高度。
3. 在每一步中，将最大的未分配学生分配到最高排的未分配的座位上(其次是左边的最大位置)。

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