Рыцарский тур с использованием нейронной сети

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

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

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

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

EDIT
Рабочий код можно найти на GitHub https://github.com/Yacoby/KnightsTour


python graph neural-network
person Yacoby    schedule 11.10.2009    source источник
comment
не могли бы вы опубликовать свое окончательное решение? может быть полезно для некоторых других   -  person scable    schedule 13.10.2009
comment
Хотя мое текущее решение работает нормально, я хочу добавить обнаружение шаблонов, прежде чем публиковать его.   -  person Yacoby    schedule 13.10.2009

Ответы (3)


arrow_upward
3
arrow_downward

Вы не можете обновить нейроны на месте. Поскольку 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()
person John La Rooy    schedule 11.10.2009
comment
Я не могу поверить, как я мог пропустить что-то настолько очевидное. Ответ был принят за несколько лучшее объяснение. - person Yacoby; 12.10.2009

arrow_upward
2
arrow_downward

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

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

person Steve314    schedule 11.10.2009

arrow_upward
0
arrow_downward

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

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

person Strill    schedule 03.12.2011