公平吸引算法

Question

公平吸引力问题

我试过的
我尝试将开关视为位字符串的位。基本上，无论状态如何，我都需要将它们全部归零。因为这个问题在关于减少和征服的一章中，所以我试图解决 n=1 的问题。但是，我什至无法想出一个蛮力解决方案来确保关闭一个开关。

如果有什么想法或提示，请帮忙，谢谢。

Answer 1

由于我们获得的唯一反馈是当我们处于目标状态时，问题是尽可能有效地探索所有可能的状态。相关的数学对象称为Gray code。由于您正在寻找递归构造，因此算法是：

• 如果没有开关，那么只有一种状态，我们就在其中。
• 否则，选择一个开关。递归探索其他开关的所有配置。翻转保留的开关，然后再次递归探索其他开关。