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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 48, средняя оценка - 4.77
АТерентьев
21 / 20 / 1
Регистрация: 16.10.2009
Сообщений: 947
#1

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

05.01.2011, 22:11. Просмотров 6437. Ответов 11
Метки нет (Все метки)

Доброго времени суток!
Для полного графа и n <= 20 нужно написать программу для задачи коммивояжера за приемлемое время
Какой алгоритм - возможен ли полный перебор, ветвей и границ или ?
Спасибо за любую идею или ссылку!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2011, 22:11     Коммивояжер
Посмотрите здесь:

Коммивояжер (бродячий торговец) - C++
Ребят, помогите с реализацией задачи о коммивояжере, желательно простое решение полным перебором: потому как, входные данные будут больше...

коммивояжер - Pascal
не могу найти подходящую приложению для коммивояжер!

Коммивояжер. Расчёт минимального пути - C#
нужно переделать функцию которая считает минимальный путь с помощью метода ветвей и границ, на функцию полного перебора public void...

Коммивояжер (полный перебор), и сколько стоит? - C#
Здравствуйте, подскажите работающую программу для решения задачи коммивояжера методом полного перебора Цитата: поиск самого...

Определить, сможет ли коммивояжер обойти все клетки и вернутся в исходную клетку - VBA
Имеется клеточное поле размером N*M. Из каждой клетки можно перемещатся в одну из соседних, если она есть ( вверх, вправо, вниз, влево)....

Определить маршрут, которым должен двигаться коммивояжер так, чтобы заключить максимально возможное число контрактов - Алгоритмы
Множество городов, обслуживаемых фирмой X представлено графом, вершины которого соответствуют городам, а ребра – соединяющим их маршрутам,...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 23:15     Коммивояжер #2
http://ru.wikipedia.org/wiki/Задача_о_коммивояжёре
АТерентьев
21 / 20 / 1
Регистрация: 16.10.2009
Сообщений: 947
06.01.2011, 00:47  [ТС]     Коммивояжер #3
Спасибо! Теорию я знаю - в книжке Мудрова - хорошо рассказано. Есть интересные реализации - ищу их ввиду недостатка времени.

 Комментарий модератора 
Ссылка удалена, правила форума, п. 3.10
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 00:51     Коммивояжер #4
АТерентьев, так что нужно? Написать программу которая будет выполняться за приемлемое время? А какое тогда время приемлемое?
АТерентьев
21 / 20 / 1
Регистрация: 16.10.2009
Сообщений: 947
06.01.2011, 09:11  [ТС]     Коммивояжер #5
Да, нужна программа, я думаю минут 5 - это нормально. Я смотрю метод ветвей и границ - судя по тому, что посмотрел - вроде подходит. Предпочитаю C# , но не уверен, что это наиболее подходит в данном случае. Видел реализацию алгоритма Дейкстры на C++ - очень понравилось использование контейнеров типа векторов, векторов от векторов и множеств - очень компактно получилось и красиво. Главная проблема - время, поэтому искал готовое
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 10:26     Коммивояжер #6
Готового у меня нет. Лучше поищите в интернете сами, там очень много разных рефератов, курсовых работ с готовыми программами даже есть. Лучше что там есть Вам вряд ли кто здесь напишет.
АТерентьев
21 / 20 / 1
Регистрация: 16.10.2009
Сообщений: 947
06.01.2011, 12:05  [ТС]     Коммивояжер #7
Сделаю - выложу. Все равно разбираться - что к чему . Вариант интересный есть.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 13:12     Коммивояжер #8
АТерентьев, Если честно меня немного смущает: n <= 20 (имею ввиду n равное 20) и 5 минут. Но все может быть... Если что-то найдете и выложите, то обязательно посмотрю.
АТерентьев
21 / 20 / 1
Регистрация: 16.10.2009
Сообщений: 947
06.01.2011, 14:09  [ТС]     Коммивояжер #9
Время - на вскидку сказал. Сейчас запустил на Паскале - для n=6 тестовый пример из книжки считает мгновенно. Прогу приложил с тестовым примером.
Вложения
Тип файла: zip commivgr.zip (2.3 Кб, 697 просмотров)
Тип файла: zip input.zip (171 байт, 333 просмотров)
АТерентьев
21 / 20 / 1
Регистрация: 16.10.2009
Сообщений: 947
06.01.2011, 14:14  [ТС]     Коммивояжер #10
Добавил входной файл для примера из книжки Мудрова - для метода ветвей и границ
Вложения
Тип файла: zip input.zip (265 байт, 317 просмотров)
valeriikozlov
Эксперт C++
4669 / 2495 / 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

И напишите сколько по времени получилось?
АТерентьев
21 / 20 / 1
Регистрация: 16.10.2009
Сообщений: 947
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     Коммивояжер
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru