Max Home IndustryВы, наверное, знаете, что задача коммивояжера — одна из классических задач теории информатики. Теперь у нас есть новая задача — задача коммивояжера, и каждый может присоединиться к ней.
Задача физического коммивояжера (PTSP) — это действительно очень весело. Идея аналогична оригинальной задаче коммивояжера — вам просто нужно посетить каждый город или точку по очереди и преодолеть наименьшее расстояние. «Физическое» в названии задачи связано с дополнительными трудностями при фактическом вождении транспортного средства по трассе.
В этом случае транспортное средство моделируется и подчиняется простому набору динамических правил — ему приходится иметь дело как с трением, так и с инерцией. В результате вы не можете просто двигаться по прямой от одной точки к другой. Вы должны двигаться по трассе, давая время для замедления и поворота на поворотах.
Вы можете принять участие в двух соревнованиях: человеческое решение или решение на основе ботов. Для соревнований людей вы просто авторизуетесь на сайте и начинаете управлять кораблем.
Для версии бота вам нужно разработать программу, которая выполняет ту же работу. Кодирование выполняется на Java, и все, что вам нужно сделать, это предоставить список действий, выбранных из шести возможных действий, чтобы направить «корабль» по курсу. Корабль может сталкиваться с препятствиями, и цель — пройти путь за минимальное количество шагов.
Чтобы процитировать сайт:
PTSP был впервые представлен как соревнование на конференции по генетическим и эволюционным вычислениям (GECCO) в 2005 году. По сравнению с TSP, PTSP добавляет некоторые интересные проблемы по сравнению со стандартным TSP. Для заданного количества путевых точек решения PTSP намного длиннее. Например, карта с 10 путевыми точками может потребовать последовательности из нескольких сотен действий (векторов сил) для ее решения. Кроме того, длина оптимальной последовательности заранее неизвестна.
Если вы посмотрите видео, вы увидите человеческое решение проблемы и получите хороший шанс увлечься этим вызовом — так что вас предупредили!
Как в соревнованиях людей, так и среди ботов есть списки лидеров, и будет интересно посмотреть, будут ли боты лучше людей — конечно, так и будет. Вам нужно собрать 20 карт, и все программное обеспечение легко загрузить и использовать. Поскольку количество карт, похоже, имеет небольшое количество точек для посещения, большинство трудностей в алгоритме будет связано с построением курса, и это предполагает, что какое-то динамическое программирование, оптимизация, генетический алгоритм и т. Д., Скорее всего, будет успешным. .
Соревнование среди людей продлится до 7 мая, а финальные испытания соревнования ботов начнутся 27 мая 2012 года.