Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 6
На поздних этапах резать путь становится не эффективным, тк чтобы вернуться потом нужно пройти весь цикл.
Змея даже на поздних этапах идет к мыши по кратчайшему пути. Единственное, что я не делаю – это поиск на 100% пути. Если мы не смогли найти за n итераций (где n — число клеточек), то мы просто пускаем змею по Гамельтонову пути. И пробуем найти новый пусть только после того как змея проползет количество клеток равное её длине. В таком случае мы не тратим в пустую время на поиск.
Так я и говорю, зря на поздних этапах змея идет по кратчайшему пути. Было бы быстрее, если бы она так и шла по циклу:
Сокращая пройденное расстояние сейчас, змея дольше идет до следующей цели.
После срезки появляются зоны в которые змея уже не вернётся. Если такая область большая, то вероятность, что новая цель появится там — тоже большая. поэтому лучше не торопиться сейчас, зная, что новая цель появится прямо перед глазами.
на ранних этапах можно экономить за счет срезок, но чем ближе к финишу, тем больше вероятность новых полных циклов.
при движении чисто по циклу, ближе к концу игры цели будут достигаться быстрее в среднем.
я думаю неоптимизированный и данный оптимизированный вариант движения +- равны (интересно было бы измерить или посчитать), просто оптимизированный быстрее проходит начало, неоптимизированный — конец.
но если совместить оба варианта, то думаю будет максимально быстро (тоже можно сравнить).
скорее всего есть какая-то эвристика, когда можно резать, а когда нет, эта я думаю должна учитывать вероятность появления в цели в той или иной области.
Сокращая пройденное расстояние сейчас, змея дольше идет до следующей цели.
После срезки появляются зоны в которые змея уже не вернётся. Если такая область большая, то вероятность, что новая цель появится там — тоже большая. поэтому лучше не торопиться сейчас, зная, что новая цель появится прямо перед глазами.
на ранних этапах можно экономить за счет срезок, но чем ближе к финишу, тем больше вероятность новых полных циклов.
при движении чисто по циклу, ближе к концу игры цели будут достигаться быстрее в среднем.
я думаю неоптимизированный и данный оптимизированный вариант движения +- равны (интересно было бы измерить или посчитать), просто оптимизированный быстрее проходит начало, неоптимизированный — конец.
но если совместить оба варианта, то думаю будет максимально быстро (тоже можно сравнить).
скорее всего есть какая-то эвристика, когда можно резать, а когда нет, эта я думаю должна учитывать вероятность появления в цели в той или иной области.
при движении чисто по циклу, ближе к концу игры цели будут достигаться быстрее в среднем.
я думаю неоптимизированный и данный оптимизированный вариант движения +- равны (интересно было бы измерить или посчитать), просто оптимизированный быстрее проходит начало, неоптимизированный — конец.
Да согласен. Когда остаётся свободных клеточек равное одной длине змеи, то можно просто ползти по пути не сворачивая.
Не возникнут ли проблемы у Гамильтоновского пути в случае если размеры поля нечётные? Для какого-нибудь из положения мыши
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Змейка, мыши и Гамильтон