Traveling Salesman Problem, Решаем "задачу коммивояжера" Налаштування

[nikelong]

Проект "Traveling Salesman Problem"

----------------------------------------------------------------------------------------------------------

• Официальный сайт - в дауне. You don't have permission to access /tsp/ on this server.
• Официальная статистика по команде "Ukraine" - там же.
  
• Статистика на фришниках
• Статистика на фришниках по команде "Ukraine"

----------------------------------------------------------------------------------------------------------
ТОП-20 участников:

----------------------------------------------------------------------------------------------------------
Дата основания команды - 22.10.2007 Капитан - uNiUs
----------------------------------------------------------------------------------------------------------
Для присоединения к команде Украины:
1. Загрузите BOINC менеджер (Если его у Вас еще нет!)
2. Перейдите в "расширенный вид"
3. Выберите сервис ---> добавить проект
4. Введите адрес проекта http://bob.myisland.as/tsp/
5. Введите свои регистрационные данные.
6. Найдите нашу команду. Она называется Ukraine и адрес ее статистики вы могли видеть выше.
7. Если есть доступные для загрузки задания Вы их получите и начнете расчеты.
----------------------------------------------------------------------------------------------------------
Полезная информация:
Для идентификации пользователя в BOINC могут служить 2 вещи:
1) пара e-mail/пароль
2) межпроектный идентификационный ID (Cross-project ID) - 32значное шестнадцатиричное число.

Если Вы пожелаете подключится ещё и к другому BOINC-проекту, то помните: чтобы не плодить новых аккаунтов при подключении к новому проекту или команде, нужно обязательно везде регистрироваться с одним и тем же e-mail/паролем либо CPID. если при регистрации в проекте указать другие e-mail или пароль, BOINC создаст новый аккаунт с тем же именем!
----------------------------------------------------------------------------------------------------------

О проекте:
(Traveling Salesman Problem, TSP) - Классический пример такой задачи, известный как "задача коммивояжера" , формулируется так: коммивояжеру требуется объехать несколько городов, побывав в каждом один раз, и вернуться в исходную точку. Нужно найти кратчайший маршрут.

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

Сейчас Математики не нашли "Эффективное общее решение", и по этому project TSP с начала решает трудную задачу использования методом brute force (грубой силы), чтобы найти оптимальное решение, а уже в дальнейшем будут исследовать полученный результат.

Описание:
TSP (The Traveling Salesman Problem) задача формулируется следующим образом: дано N городов, известны расстояния между любыми из них, нужно найти наикротчайший путь, чтобы посетить все из них. Проблема в том, что для 10 городов существует 362880 возможных путей, для 20 городов существует 1,216 x 1017 возможностей посетить все из них. TSP проект ищет кратчайший путь для 48 населенных пунктов.

Ссылки по теме:

• Википедия - "Задача коммивояжера"

График ППД команды за последние 60 дней:

(Show/Hide)

Финал - 211 место.

http://www.boinc-af.org/content/view/830/278/

http://www.dp.by/wiki/Projects/Tsp

http://wiki.bc-team.org/index.php?title=TSP/en

Це повідомлення відредагував nikelong: Aug 29 2010, 23:49

[Mally]

шукала щось по дипломній роботі і знайшла щось тут...

принаймні цю проблему вирішують. На даному етапі її розв`язано генетичним алгоритмом, що найефективніше зі всіх раніше розглянутих.