解决计划问题

Question

解决计划问题

4

我是一个新手，对AI/算法领域不熟悉，目前正在尝试解决一个问题，之前只在2D网格数组上实现了A*寻路。

问题如下：

考虑一个由40名学生（20女，20男）组成的班级，他们的身高各不相同，并且有自己的座位偏好（行、列或两者都有），教室里有50个座位，每个学生必须占据一个座位，座位的布局如下：

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

              [ WHITE BOARD ]

为了最佳的座位安排，我们选择了一个评分图表：

不要有学生直接坐在前面：+4分
直接坐在前面的学生至少比你矮2厘米：+4分
旁边坐的学生异性：+8分
一列中有4个同性别的学生：-10分
从白板开始高度递增的列：+20分
根据个人喜好安排座位：+2分

目标是获得最大可能的分数。

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

起点：所有学生都未就座

路径成本：转换后的分数增量

目标：所有学生就座

这里的问题是，不知道能够获得的最大分数，并且我预见到可能会出现程序无法提前计划的情况（程序可能会先选择+8，然后再选择+4，但更好的方法是先选择+2，接着选择+20）。我知道可以查找特定深度，比如深度为5。这引出另一个问题：我应该使用多少深度？我不想访问所有可能的状态。

1. 这种问题有多难？（从解决迷宫到解决国际象棋的规模）

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

- Mc Kevin

A* 可能不是一个好的方法。至少我无法理解启发式会是什么样子。 - Martin G

2

对于这个问题来说，A* 算法似乎是不太合适的工具。因为 A* 算法是用于最小化成本的，而你要尝试最大化收益，并且它不允许出现负成本。我没有看到将这个问题转化为最小化机会成本的好方法，也没有好的办法解决分数上涨和下跌的问题。 - user2357112

通常来说，将所有的约束条件都以否定的形式陈述是很容易的。例如：不要说“前面的学生至少比自己低2厘米：+4”，而要说“前面的学生没有至少比自己低2厘米：-4”。@user2357112 - Geoffrey De Smet

@GeoffreyDeSmet：再次查看评分标准，我对我的担忧不确定。我认为将这样的翻译应用于此问题会导致成本结构，其中移动往往具有大致相等的高成本，这些成本被你没有获得的所有奖金所主导，从而导致搜索倾向于退化为广度优先。在第二次阅读评分标准时，似乎奖金并不是以这种方式起作用。您比我更有优化问题的经验，因此您可能更了解事物的运作方式。 - user2357112

规则3如何评分[M]-[F]-[M]？它会是28吗，因为有两条图边？它会是38吗，因为每个人都坐在至少一个异性旁边？还是会是4*8，因为中间的人坐在两个异性旁边？ - Larry OBrien

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Geoffrey De Smet · Accepted Answer

第6个限制看起来暗示了这个问题可能是NP完全或者NP难的。这意味着：A*算法在这种情况下无法（很好地）工作，因为除非P=NP，否则不可能创建一个良好的可接受启发式函数。可接受的意思是，启发式函数应该总是低估或等于最优解的分数，它永远不会高估。

如果您需要包含第6个约束条件，我建议使用Tabu搜索、模拟退火或Late Acceptance等算法，这些算法在类似的用例中表现良好，例如晚宴座位安排和课程安排。

没有第6个限制，我认为像首次递减适配算法这样简单的算法可以被设计成最优的：

所有偶数座位都给女性，所有奇数座位都给男性（如果没有足够的座位给1个性别，则将溢出的座位添加到另一个性别）。独立地安排两个性别。在安排1个性别时，忽略另一个性别的座位。
按照身高对一个性别组中的所有学生进行排序。按递减高度逐个分配它们。
对于每一步，将最大的未分配学生分配到最高行的未分配座位（次要是最左边的座位）

不过, 第2个限制可能仍然不是最优的...您可能仍然需要在其上应用一些Tabu搜索或Late Acceptance。