Стремясь стереть свои немного ржавые навыки программирования, я пытаюсь решить эту проблему обхода графа, с которой столкнулся.
Я хочу найти путь, который посещает все координаты (вершины) в сетке 10x10. Существуют некоторые ограничения движения, например, возможность перемещаться только на 3 шага в любом направлении (x +/- 3 ИЛИ y +/- 3) или на 2 шага по диагонали (x +/- 2 И y +/- 2). Из того, что я понимаю, эти ограничения на самом деле не имеют большого значения, так как это всего лишь граф с вершинами и ребрами, и я могу достаточно легко смоделировать это в своем решении.
Я дошел до того, что смог решить эту проблему. проблема для сетки 6x6 с использованием «простой» стратегии DFS (по крайней мере, я думаю, что это то, что я создал :). Но, увеличиваясь, я сталкиваюсь с проблемами производительности, так как O (n) моего алгоритма - своего рода дерьмо. 7x7 занимает на моем компьютере 45 минут, поэтому 10x10 просто забывают об этом.
Я понял, что сетка 5x5 всегда может быть решена, поэтому я думаю, что одной жизнеспособной стратой было бы разделить 10x10 на 4x5x5. Но это не похоже на правильное решение, и даже если бы оно решало сетки со сторонами, кратными 5, я все равно не смог бы решить 8x8 и 11x11 et c.
Итак, мой вопрос здесь о том, какие стратегии можно применять для оптимизации для этой конкретной проблемы?