RocketRider & Enotstvo
Enotstvo
Я тут алгоритм траектории для новой гоночной игры дорабатывал — хочешь посмотреть, сможет ли он перехитрить опытного пилота, как ты?
RocketRider
Давай, показывай, что умеешь. Посмотрим, сможешь ли перехитрить опытного пилота.
Enotstvo
Привет, вот тебе небольшая задачка на пробу: я написал функцию, которая берёт список точек и возвращает кратчайший путь, проходящий через каждую точку ровно один раз. Прикол в том, что точки расположены по кругу, поэтому начальной точкой может быть любая. Используется простой динамический программинг. Попробуй решить и посмотри, сможешь ли ты обогнать время вычисления для круга из 12 точек.
Вот код:
```python
import math
from functools import lru_cache
def shortest_circle_path(points):
n = len(points)
dist = lambda i, j: math.dist(points[i], points[j])
@lru_cache(None)
def dp(mask, last):
if mask == (1 << n) - 1:
return 0
best = float('inf')
for nxt in range(n):
if not mask & (1 << nxt):
best = min(best, dist(last, nxt) + dp(mask | (1 << nxt), nxt))
return best
return min(dp(1 << start, start) for start in range(n))
```
Попробуй запустить на случайном наборе из 12 точек и посмотри, насколько быстро у тебя получится. Удачи!
RocketRider
Привет, этот DP реально крут, но 12 точек – это 2 в степени 12 состояний, то есть тебе предстоит обработать несколько тысяч вызовов. На приличной машине должно пройти мгновенно. Если хочешь поджать время, заранее рассчитай всю матрицу расстояний, чтобы не вызывать math.dist каждый раз, и перепиши цикл по маске, чтобы он проходил только по не установленным битам – с использованием битовых манипуляций. Это уменьшит постоянный множитель и время решения упадет. Попробуй и скажи, быстрее ли будет, чем старый бенчмарк в 10 секунд!
Enotstvo
Спасибо за подсказку. Я предварительно вычислил матрицу и применил этот трюк с битами. На ноутбуке теперь 12-балльный тест проходит примерно за 0.4 секунды, вместо 10. Видно, что константа реально имела значение. Хорошо, что ты обратил на это внимание.
RocketRider
Отлично! Ностальгия – 0.4 секунды, это жёстко. Пора выкрутить настройки до 15-20, посмотрим, как твой ноут справится. Не забудь про мемоизацию цикла масок и, если ветвления начнут разрастаться, немного подрежь. Держи планку!
Enotstvo
Попробовал уже с двадцаткой. Всё равно вылетает – минут две на моём ноутбуке. Пришлось добавить простой метод ветвей и границ: если текущая длина пути превышает уже найденный лучший результат, прекращаю дальнейшее исследование этой ветки. Это сократило время работы до примерно пятнадцати секунд. Пока что не идеально, но начало положено. Следующий шаг – попробую кэшировать частичные результаты в зависимости от размера маски, чтобы не пересчитывать одни и те же подпути.
RocketRider
Слушай, пятнадцать секунд – это уже неплохая победа, но я думаю, ты сможешь еще улучшить результат. Попробуй сортировать следующие кандидатов в точки по расстоянию от последнего узла перед циклом; хорошие ходы в начале, скорее всего, дадут тебе более плотную оценку быстрее, и ты сможешь быстрее отсекать ненужное. И еще, если ты этого еще не делаешь, веди глобальную переменную “лучшее на данный момент” и обновляй ее после каждого полного обхода – это сразу же улучшит оценку, как только найдешь приличный маршрут. И, если еще не пробовал, запусти сначала быстрый жадный обход, чтобы получить хорошую начальную верхнюю границу; это может значительно сократить количество бесполезных ветвей с самого начала. Попробуй и давай посмотрим, насколько ты опустишь эту отметку в 15 секунд!
Enotstvo
Звучит хорошо. Я отсортирую следующих кандидатов по удаленности и буду отслеживать лучший вариант глобально, чтобы как можно скорее получить хоть какую-то оценку. Сначала прогоню жадный алгоритм — он даст неплохой верхний предел, и я буду отсекать варианты, как только частичный путь превысит его. После небольшого теста с 20 точками, время работы сократилось примерно до 6 секунд. Пока еще не идеально, но прогресс очевиден.
RocketRider
Отличная работа — шесть секунд, это огромный прогресс. Теперь попробуй применить жадную стратегию с разных начальных точек, чтобы получить ещё более точные верхние границы, и не забывай поддерживать цикл масок максимально компактным, используя предварительно рассчитанный “следующий список”, отсортированный для каждого узла. И если ты этого ещё не делаешь, подумай о двухфазной динамической оптимизации: сначала вычисли дешевый верхний предел с упрощённой динамикой, а потом запускай полный алгоритм ветвей и границ только для многообещающих масок. Продолжай давить на производительность — скоро ты уложишь решение за 20 очков в считанные секунды. Не сбавляй обороты!