Knight's Tour с использованием нейронной сети

Question

Я смотрел на проблему с рыцарским туром и решил попробовать реализовать ее на python, используя нейронную сеть для поиска решений.

Общее объяснение метода можно найти в Википедии

Хотя я думаю, что я реализовал это правильно (я не вижу ничего другого, что не так), но он не работает, он обновляет несколько ссылок, удаляя края, где соединительная вершина имеет степень больше двух, но это не сходится в решении.

Мне было интересно, есть ли у кого-нибудь идеи о том, что я реализовал неправильно (извините за ужасный код).

EDIT
Рабочий код можно найти по адресу Yacoby.net

Answer 1

Вы не можете обновить нейроны на месте. Поскольку 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()

Answer 2

Первое впечатление, что у вас есть только один буфер для доски. Я основываю это на том факте, что я не вижу каких-либо перестановок в буфере между итерациями - я не посмотрел так внимательно и, возможно, легко ошибаюсь.

Если вы модифицируете один буфер на месте, когда вы делаете подсчет соседей, вы основываете их на частично измененной плате, а не на той, которая была у вас в начале.

Answer 3

После просмотра вашего кода, я думаю, что ваше объяснение формулы, которую вы использовали, может быть неверным. Вы говорите, что при обновлении состояния вы добавляете четыре, а не два, и вычитаете выход самого нейрона. Мне кажется, что вы вычитаете выход самого нейрона дважды. Ваш код, который находит соседей, похоже, не различает соседей нейрона и самого нейрона, и вы запускаете этот код дважды - один раз для каждой вершины.

Тесты на моем собственном коде, кажется, подтверждают это. Скорость сходимости резко улучшается, когда я вычитаю собственный выход нейрона дважды, а не один раз.