Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » коммивояжер на полном графе
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Есть плоскость, на которой находится N точек с координатами (x1, y1), (x2, y2) … (xN, yN). Человек находится в точке с координатами (0, 0). Его максимальная скорость передвижения V. Нужно определить минимальное время, за которое он сможет обойти все точки и вернуться в исходную позицию.
Ограничения:
Время 20 с, память 256 мб
1 ? N ? 20,
1 ? V ? 1000,
-1000 ? Xi, Yi ? 1000.
Т.к точек (N <= 20),то можно написать динамику по маскам,а именно
F(I, J) - минимальное время прохождения всех вершин маски I,при этом мы остановились в вершине J.
Дальше мы перебираем вершину которая не помечена ещё в маске,и следовательно переходим в новое состояние
F(newI, newJ) = MIN( F(newI, newJ), F(I, J) + DIST( J, newJ ) / V );
Где DIST( I, J ) - расстояние между точками I и J.
(I <= 2^N, J <= N).
Время работы ~O(2^N * N^2).
Память ~O(2^N * N).
Спасибо. Задачу сдал с показателями 10.453 c / 173308 Кб.
по-моему это задача называется гамильтонов цикл
Можно ссылку на задачу?
Задача называется действительно комвияжор,и для решения такой задачи с весами рёбер обычно используют динамику описанную выше.
Только сложность описанной выше динамики выходит O(N^2*2^N), потому что состояний O(N*2^N) и из каждого состояния мы перебираем O(N) переходов.
Да, верно. 
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » коммивояжер на полном графе