Стратегии оптимизации для поиска пути обхода графа без повторного посещения (все вершины) - PullRequest
0 голосов
/ 27 апреля 2020

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

Я хочу найти путь, который посещает все координаты (вершины) в сетке 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.

Итак, мой вопрос здесь о том, какие стратегии можно применять для оптимизации для этой конкретной проблемы?

1 Ответ

1 голос
/ 27 апреля 2020

Ваша задача - задача о гамильтоновом пути , которая NP-полна для произвольных графов. Это означает, что не существует известного эффективного алгоритма, поэтому попытка решить его для произвольных графов будет довольно бесплодной.

Вместо этого используйте тот факт, что вы решаете его на сетке . Вы можете просто go построчно, оборачиваясь на концах.

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

...