利用神经网络解决骑士巡游问题

Question

我在研究骑士巡逻问题时，决定尝试用神经网络在Python中实现它，以找到解决方案。

关于这种方法的总体解释可以在维基百科上找到。

虽然我觉得我实现得还不错（我看不出其他错误），但它并没有正常工作。它更新了一些链接，去掉了那些连接点度数超过两个的边，但就是找不到解决方案。

我在想有没有人能告诉我我哪里实现得不对（抱歉代码写得很糟糕）。

编辑
可以在GitHub上找到可用的代码，链接是https://github.com/Yacoby/KnightsTour

Answer 1

看了你的代码，我觉得你对你用的公式的解释可能有点问题。你提到在更新状态时，你加了四而不是两个，并且还减去了神经元自身的输出。但我觉得你实际上是把神经元自身的输出减了两次。你的代码在找邻居时似乎没有区分神经元的邻居和神经元本身，而且你这个代码运行了两次——每个顶点各一次。

我自己测试的代码似乎也证实了这一点。当我把神经元自身的输出减去两次而不是一次时，收敛速度明显提高。

Answer 2

我的第一印象是，你的棋盘只有一个缓冲区。我是根据没有看到在每次迭代之间有缓冲区的交换来判断的——我没有仔细看，可能会有错误。

如果你在原地修改这个缓冲区，当你计算邻居的数量时，你是基于一个部分修改过的棋盘来计算的，而不是你一开始的棋盘。

Answer 3

你不能直接在原地更新神经元。因为U[t+1]是依赖于U[t]和V[t]的，如果你已经更新了V，那么计算U的时候就会出错。

我觉得你应该把更新分成两个阶段：先更新状态（update_state），再更新输出（update_output），这样所有的U都更新完了，然后再更新所有的V。

    for n in neurons:
        n.update_state()
    for n in neurons:
        n.update_output()