Задача физического коммивояжера


Вы, наверное, знаете, что задача коммивояжера – одна из классических задач теории информатики. Теперь у нас есть новая задача – задача коммивояжера, и каждый может присоединиться к ней.

Задача физического коммивояжера (PTSP) – это действительно очень весело. Идея аналогична оригинальной задаче коммивояжера – вам просто нужно посетить каждый город или точку по очереди и преодолеть наименьшее расстояние. «Физическое» в названии задачи связано с дополнительными трудностями при фактическом вождении транспортного средства по трассе.

В этом случае транспортное средство моделируется и подчиняется простому набору динамических правил – ему приходится иметь дело как с трением, так и с инерцией. В результате вы не можете просто двигаться по прямой от одной точки к другой. Вы должны двигаться по трассе, давая время для замедления и поворота на поворотах.

Вы можете принять участие в двух соревнованиях: человеческое решение или решение на основе ботов. Для соревнований людей вы просто авторизуетесь на сайте и начинаете управлять кораблем.

Для версии бота вам нужно разработать программу, которая выполняет ту же работу. Кодирование выполняется на Java, и все, что вам нужно сделать, это предоставить список действий, выбранных из шести возможных действий, чтобы направить «корабль» по курсу. Корабль может сталкиваться с препятствиями, и цель – пройти путь за минимальное количество шагов.

Чтобы процитировать сайт:

PTSP был впервые представлен как соревнование на конференции по генетическим и эволюционным вычислениям (GECCO) в 2005 году. По сравнению с TSP, PTSP добавляет некоторые интересные проблемы по сравнению со стандартным TSP. Для заданного количества путевых точек решения PTSP намного длиннее. Например, карта с 10 путевыми точками может потребовать последовательности из нескольких сотен действий (векторов сил) для ее решения. Кроме того, длина оптимальной последовательности заранее неизвестна.

Если вы посмотрите видео, вы увидите человеческое решение проблемы и получите хороший шанс увлечься этим вызовом – так что вас предупредили!

Как в соревнованиях людей, так и среди ботов есть списки лидеров, и будет интересно посмотреть, будут ли боты лучше людей – конечно, так и будет. Вам нужно собрать 20 карт, и все программное обеспечение легко загрузить и использовать. Поскольку количество карт, похоже, имеет небольшое количество точек для посещения, большинство трудностей в алгоритме будет связано с построением курса, и это предполагает, что какое-то динамическое программирование, оптимизация, генетический алгоритм и т. Д., Скорее всего, будет успешным. .

Соревнование среди людей продлится до 7 мая, а финальные испытания соревнования ботов начнутся 27 мая 2012 года.


Добавить комментарий