Это одно из тех заданий, где следует проявить фантазию, и нестандартный подход, а не умение гуглить решение.
4d. фантазия на тему звезд.
Во первых, это 3d. Во вторых, звезды движутся. Предположим, у звезд есть координаты, вектора скорости и кроме этого - релятивиское смещение, из-за ограничения скорости света, некоторые звезды могут к тому же двигаться со скоростями, близкими скорости света. Это потрясающая задача, а вы ее сводите к проблеме коммивояжера и backpack problem.
Я бы считал что задача релятевисткая, динамическая, так как расстояния между звездами - миллионы сетовых лет, а космический корабль не может превысить скорость света при передвижении, то есть по сути, это задача которую невозожно решить точно, в отличие от любой задачи на земле, с конечными нерелятевисткими скоростями,
Я так же допустил бы, что время разгона до крейсерской корости и торможения несущественны, при подлете к звезде и удалении от звезды, так так эти рассояния измеряются световыми годами, то есть на 5-8 порядков меньше расстояний между звездами, кроме того, в звездных сисемах есть кластеры и пустоты, что облегчает задачу, как таковую.
Можно рассмотреть 4 способа решения задач: генетические алгоритмы, нейронные сети, машинное обучение, и стандартный поход - приближенное решение задач с краевыми условиями.
Можно для простоты вообще отказаться от скоростей у звезд, и считать что коммивояжер перемещается с помощью телепортации, то есть зафиксировать время t0. Тогда я бы применил метод Монте-Карло, к примеру, так как никто не гарантирует, что задача будет на малом количестве звезд и из не будут триллионы, либо использовал какое-то условие, которо бы решало, как мы будем решать задачу, приближенно, либо точно.
В любом случае, можно поиграть с 3d, попробовать использовать алгоритмы отсечения который разщработал Кармак в Quake, либо как-то еще выделиться и показать нестандартность мышления, в том числе, попробовать деревья бинарного поиска, самобалансирующие RB-деревья, и так далее.
Средний
