@kunjut19

Более эффективный способ организовать бэктрекинг?

Пишу алгоритм для построения лабиринта на основе бэктрекинга. Хотелось бы узнать, как наиболее эффективно реализовать бэктрекинг, чтобы алгоритм выполнялся быстрее для очень больших по размеру лабиринтов. Идея такова:
Массив клеток лабиринта, где каждый элемент либо 0, либо 1 - стена или проход. Изначально все пространство - стены, в которых по ходу алгоритма пробивается проход. Попали в тупик? Отмечаем текущую клетку как тупик. Далее рандомно выбираем клетку с уже прорытым проходом, которая пока не является тупиком. Начинаем рыть проход из этой клетки. Когда все клетки с проходами станут тупиками - лабиринт построен. Но я не знаю, какой метод выбора нетупикового прохода лучше в плане скорости поиска. У меня есть 2 идеи:

1) Каждый элемент массива помимо состояния стена / проход должен хранить состояние тупик / не тупик. Тогда при поиске нетупиковой клетки придется выбирать все нетупиковые из всех существующих клеток пространства, а уже потом среди них выбрать одну рандомную. Такой метод мне не нравится тем, что общее количество клеток пространства может быть огромное количество. И каждый раз придется снова пробегать по всему массиву в поисках нетупиковых элементов и выбора из них одного случайного.

2) Второй подход - это хранить все клетки с проходами в отдельном массиве. А массив с состояниями клеток оставить одномерным. При попадании в тупик нужно будет удалять из массива с проходами текущую клетку, чтобы не обращаться к ней в следующий раз. В итоге выбирать рандомно нетупиковую клетку придется с каждым разом среди всё меньшего количества клеток. Но такой подход мне не нравится большим количеством операций с массивом. Прорыли новый проход - добавить в массив. Попали в тупик - удалить из массива (почти всегда откуда-то из середины массива).
Что бы вы посоветовали? Может, какой-нибудь другой вариант?
  • Вопрос задан
  • 63 просмотра
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы