Форум программистов, компьютерный форум CyberForum.ru

Коммивояжер - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 48, средняя оценка - 4.77
АТерентьев
20 / 19 / 1
Регистрация: 16.10.2009
Сообщений: 933
05.01.2011, 22:11     Коммивояжер #1
Доброго времени суток!
Для полного графа и n <= 20 нужно написать программу для задачи коммивояжера за приемлемое время
Какой алгоритм - возможен ли полный перебор, ветвей и границ или ?
Спасибо за любую идею или ссылку!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 23:15     Коммивояжер #2
http://ru.wikipedia.org/wiki/Задача_о_коммивояжёре
АТерентьев
20 / 19 / 1
Регистрация: 16.10.2009
Сообщений: 933
06.01.2011, 00:47  [ТС]     Коммивояжер #3
Спасибо! Теорию я знаю - в книжке Мудрова - хорошо рассказано. Есть интересные реализации - ищу их ввиду недостатка времени.

 Комментарий модератора 
Ссылка удалена, правила форума, п. 3.10
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 00:51     Коммивояжер #4
АТерентьев, так что нужно? Написать программу которая будет выполняться за приемлемое время? А какое тогда время приемлемое?
АТерентьев
20 / 19 / 1
Регистрация: 16.10.2009
Сообщений: 933
06.01.2011, 09:11  [ТС]     Коммивояжер #5
Да, нужна программа, я думаю минут 5 - это нормально. Я смотрю метод ветвей и границ - судя по тому, что посмотрел - вроде подходит. Предпочитаю C# , но не уверен, что это наиболее подходит в данном случае. Видел реализацию алгоритма Дейкстры на C++ - очень понравилось использование контейнеров типа векторов, векторов от векторов и множеств - очень компактно получилось и красиво. Главная проблема - время, поэтому искал готовое
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 10:26     Коммивояжер #6
Готового у меня нет. Лучше поищите в интернете сами, там очень много разных рефератов, курсовых работ с готовыми программами даже есть. Лучше что там есть Вам вряд ли кто здесь напишет.
АТерентьев
20 / 19 / 1
Регистрация: 16.10.2009
Сообщений: 933
06.01.2011, 12:05  [ТС]     Коммивояжер #7
Сделаю - выложу. Все равно разбираться - что к чему . Вариант интересный есть.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 13:12     Коммивояжер #8
АТерентьев, Если честно меня немного смущает: n <= 20 (имею ввиду n равное 20) и 5 минут. Но все может быть... Если что-то найдете и выложите, то обязательно посмотрю.
АТерентьев
20 / 19 / 1
Регистрация: 16.10.2009
Сообщений: 933
06.01.2011, 14:09  [ТС]     Коммивояжер #9
Время - на вскидку сказал. Сейчас запустил на Паскале - для n=6 тестовый пример из книжки считает мгновенно. Прогу приложил с тестовым примером.
Вложения
Тип файла: zip commivgr.zip (2.3 Кб, 674 просмотров)
Тип файла: zip input.zip (171 байт, 325 просмотров)
АТерентьев
20 / 19 / 1
Регистрация: 16.10.2009
Сообщений: 933
06.01.2011, 14:14  [ТС]     Коммивояжер #10
Добавил входной файл для примера из книжки Мудрова - для метода ветвей и границ
Вложения
Тип файла: zip input.zip (265 байт, 310 просмотров)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 15:59     Коммивояжер #11
АТерентьев, К сожалению с паскалем знаком очень поверхностно, можно сказать вообще "в первый раз вижу". Компилятора для паскаля не имею, и не умею с ним работать.
Ради интереса, загрузите такой тест:
20
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
2 2 0 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
3 3 3 0 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
4 4 4 4 0 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
5 5 5 5 5 0 6 7 8 9 0 1 2 3 4 5 6 7 8 9
6 6 6 6 6 6 0 7 8 9 0 1 2 3 4 5 6 7 8 9
7 7 7 7 7 7 7 0 8 9 0 1 2 3 4 5 6 7 8 9
8 8 8 8 8 8 8 8 0 9 0 1 2 3 4 5 6 7 8 9
9 9 9 9 9 9 9 9 9 0 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1 1 0 2 3 4 5 6 7 8 9
2 2 2 2 2 2 2 2 2 2 2 2 0 3 4 5 6 7 8 9
3 3 3 3 3 3 3 3 3 3 3 3 3 0 4 5 6 7 8 9
4 4 4 4 4 4 4 4 4 4 4 4 4 4 0 5 6 7 8 9
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 0 6 7 8 9
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0 7 8 9
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 0 8 9
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 0 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0

И напишите сколько по времени получилось?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.01.2011, 18:39     Коммивояжер
Еще ссылки по теме:

Решение курсового проекта задачи про коммивояжер
[C] Разработать программу "Коммивояжер"
C# Нужно разработать программу коммивояжер. Не слишком сложную

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
АТерентьев
20 / 19 / 1
Регистрация: 16.10.2009
Сообщений: 933
06.01.2011, 18:39  [ТС]     Коммивояжер #12
Я по диагонали поставил 30000 - это аналог бесконечности, т.е. нет дуг, замкнутых на себя.
Посчитала мгновенно.
Ответ:
Кратчайший цикл - 1 11 10 12 9 13 8 14 7 15 6 16 5 17 4 18 3 19 2 20
Его длина - 90
Вроде похоже на правду.
Входные данные.
20
30000 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0 30000 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0 1 30000 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0 1 2 30000 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0 1 2 3 30000 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 30000 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 30000 7 8 9 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 30000 8 9 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 30000 9 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 30000 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 30000 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 30000 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 1 30000 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 1 2 30000 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 1 2 3 30000 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 30000 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 30000 7 8 9
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 30000 8 9
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 30000 9
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 30000
Yandex
Объявления
06.01.2011, 18:39     Коммивояжер
Ответ Создать тему
Опции темы

Текущее время: 16:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru