Traveling Salesman Problem, Решаем "задачу коммивояжера" |
Привіт Гість ( Вхід | Реєстрація )
Traveling Salesman Problem, Решаем "задачу коммивояжера" |
nikelong |
Jan 5 2008, 02:14
Пост
#1
|
Тера ранчер Група: Trusted Members Повідомлень: 11 909 З нами з: 19-March 05 Користувач №: 92 Стать: Чол |
Проект "Traveling Salesman Problem" ----------------------------------------------------------------------------------------------------------
ТОП-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 |
(_KoDAk_) |
Jan 5 2008, 14:45
Пост
#2
|
BOINC-guru Група: Trusted Members Повідомлень: 3 662 З нами з: 11-August 07 З: Kharkov Користувач №: 569 Стать: Чол Парк машин: E3-1245V2@3400-Mhz 16GB 1х GTX760DCMOC2GD5 Q8200@2300-Mhz 4GB + то там то сям |
http://stats.free-dc.org/new/teamstats.php...sp&team=Ukraine
32 очков уже есть задания мелкие по трафику - 2Мб озу - 40 мин (Traveling Salesman Problem, TSP) - Классический пример такой задачи, известный как "задача коммивояжера" , формулируется так: коммивояжеру требуется объехать несколько городов, побывав в каждом один раз, и вернуться в исходную точку. Нужно найти кратчайший маршрут. Самый простой способ найти оптимальное решение - перебрать все возможные значения параметров. При этом не нужно делать никаких предположений о свойствах целевой функции, а задать ее можно просто с помощью таблицы. Однако, чтобы решить таким способом задачу коммивояжера хотя бы для 20 городов, потребуется перебрать около 1020 маршрутов, что совершенно нереально ни для какого вычислительного центра. Таким образом, возникает необходимость в каком-либо новом методе оптимизации, пригодном для практики. Сейчас Математики не нашли "Эффективное общее решение", и по этому project TSP с начало решает трудную задачу использования метод brute force (грубой силы), чтобы найти оптимальное решение, а уже в дальнейшем будут исследовать полученный результат. -------------------- - "ты говоришь так, будто тебя чай ваше не вставляет "
(Show/Hide) Спаcибо автору алфавита за любезно предоставленные буквы. |
Rilian |
Jan 5 2008, 15:34
Пост
#3
|
interstellar Група: Team member Повідомлень: 17 049 З нами з: 22-February 06 З: Торонто Користувач №: 184 Стать: НеСкажу Free-DC_CPID Парк машин: ноут и кусок сервера |
Вроде по Исследованиям Операций на 1-2м курсах в универе мы такое решали, там была куча методов для оптимального решения данной задачи. Зачем перебирать?
-------------------- |
(_KoDAk_) |
Jan 5 2008, 16:05
Пост
#4
|
BOINC-guru Група: Trusted Members Повідомлень: 3 662 З нами з: 11-August 07 З: Kharkov Користувач №: 569 Стать: Чол Парк машин: E3-1245V2@3400-Mhz 16GB 1х GTX760DCMOC2GD5 Q8200@2300-Mhz 4GB + то там то сям |
ДА куча методов есть...
насколько я их понял в данном проекте на данный момент , они тупо ищут оптимальные маршруты между городами Америки -------------------- - "ты говоришь так, будто тебя чай ваше не вставляет "
(Show/Hide) Спаcибо автору алфавита за любезно предоставленные буквы. |
Rilian |
Jan 5 2008, 17:54
Пост
#5
|
interstellar Група: Team member Повідомлень: 17 049 З нами з: 22-February 06 З: Торонто Користувач №: 184 Стать: НеСкажу Free-DC_CPID Парк машин: ноут и кусок сервера |
Не, на буржуев я считать не собираюсь!
-------------------- |
(_KoDAk_) |
Jan 5 2008, 19:36
Пост
#6
|
BOINC-guru Група: Trusted Members Повідомлень: 3 662 З нами з: 11-August 07 З: Kharkov Користувач №: 569 Стать: Чол Парк машин: E3-1245V2@3400-Mhz 16GB 1х GTX760DCMOC2GD5 Q8200@2300-Mhz 4GB + то там то сям |
все наверно будет +64 очка и на этом эксперемет оконченн.
-------------------- - "ты говоришь так, будто тебя чай ваше не вставляет "
(Show/Hide) Спаcибо автору алфавита за любезно предоставленные буквы. |
(_KoDAk_) |
Jan 15 2008, 00:23
Пост
#7
|
BOINC-guru Група: Trusted Members Повідомлень: 3 662 З нами з: 11-August 07 З: Kharkov Користувач №: 569 Стать: Чол Парк машин: E3-1245V2@3400-Mhz 16GB 1х GTX760DCMOC2GD5 Q8200@2300-Mhz 4GB + то там то сям |
Описание:
TSP (The Traveling Salesman Problem) задача формулируется следующим образом: дано N городов, известны расстояния между любыми из них, нужно найти наикротчайший путь, чтобы посетить все из них. Проблема в том, что для 10 городов существует 362880 возможных путей, для 20 городов существует 1,216 x 1017 возможностей посетить все из них. TSP проект ищет наикротчайший путь для 48 населенных пунктов. -------------------- - "ты говоришь так, будто тебя чай ваше не вставляет "
(Show/Hide) Спаcибо автору алфавита за любезно предоставленные буквы. |
(_KoDAk_) |
May 9 2008, 09:45
Пост
#8
|
BOINC-guru Група: Trusted Members Повідомлень: 3 662 З нами з: 11-August 07 З: Kharkov Користувач №: 569 Стать: Чол Парк машин: E3-1245V2@3400-Mhz 16GB 1х GTX760DCMOC2GD5 Q8200@2300-Mhz 4GB + то там то сям |
пока что сервер не раздает заданий Хотя сервак живой и доступен
последняя новость на сайте (2007-04-14) -------------------- - "ты говоришь так, будто тебя чай ваше не вставляет "
(Show/Hide) Спаcибо автору алфавита за любезно предоставленные буквы. |
(_KoDAk_) |
Jan 16 2009, 23:36
Пост
#9
|
BOINC-guru Група: Trusted Members Повідомлень: 3 662 З нами з: 11-August 07 З: Kharkov Користувач №: 569 Стать: Чол Парк машин: E3-1245V2@3400-Mhz 16GB 1х GTX760DCMOC2GD5 Q8200@2300-Mhz 4GB + то там то сям |
все еше пустынно
-------------------- - "ты говоришь так, будто тебя чай ваше не вставляет "
(Show/Hide) Спаcибо автору алфавита за любезно предоставленные буквы. |
Mally |
May 5 2009, 14:06
Пост
#10
|
Так, я створив профіль! Група: New Members Повідомлень: 2 З нами з: 5-May 09 Користувач №: 1 020 Стать: Жін |
шукала щось по дипломній роботі і знайшла щось тут...
принаймні цю проблему вирішують. На даному етапі її розв`язано генетичним алгоритмом, що найефективніше зі всіх раніше розглянутих. |
Death |
May 5 2009, 14:19
Пост
#11
|
<script ///> Група: Moderators Повідомлень: 6 371 З нами з: 5-November 03 З: Kyiv Користувач №: 26 Стать: НеСкажу Free-DC_CPID Парк машин: гидропарк jabber:deadjdona@gmail.com |
Mally, привет.
Надеюсь кроме коммивояжёров тебя заинтересует ещё что-нибудь )))) -------------------- |
Mally |
May 5 2009, 14:29
Пост
#12
|
Так, я створив профіль! Група: New Members Повідомлень: 2 З нами з: 5-May 09 Користувач №: 1 020 Стать: Жін |
|
nikelong |
May 5 2009, 15:52
Пост
#13
|
Тера ранчер Група: Trusted Members Повідомлень: 11 909 З нами з: 19-March 05 Користувач №: 92 Стать: Чол |
Mally,
К сожалению этот проект уже закрыт -------------------- |
Lo-Fi Версія | Поточний час: 20th September 2024 - 10:26 |