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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.69
Decoyfromptz
0 / 0 / 0
Регистрация: 10.10.2009
Сообщений: 4
#1

Коммивояжер (бродячий торговец) - C++

10.10.2009, 21:53. Просмотров 3401. Ответов 8
Метки нет (Все метки)

Ребят, помогите с реализацией задачи о коммивояжере, желательно простое решение полным перебором: потому как, входные данные будут больше не больше 10 городов, а 9! - вполне решабильно.
У меня есть некоторые наработки, но сроки поджимать начинают, поэтому прошу помощи....

Зарание спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.10.2009, 21:53     Коммивояжер (бродячий торговец)
Посмотрите здесь:

Коммивояжер - C++
Доброго времени суток! Для полного графа и n <= 20 нужно написать программу для задачи коммивояжера за приемлемое время Какой алгоритм...

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
11.10.2009, 10:26     Коммивояжер (бродячий торговец) #2
Хорошая и основательная задачка.
Показывай, что есть, поможем.
Готовый код был в интернете, но за него просили деньги (где-то натыкался).
Я реализовывал подобное, но там были условия по жёстче и ограничение на время, полный перебор не катил (шибко долго).
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
11.10.2009, 11:54     Коммивояжер (бродячий торговец) #3
Цитата Сообщение от Decoyfromptz Посмотреть сообщение
Ребят, помогите с реализацией задачи о коммивояжере,
а! это та задача, где коммивояжер играет в тэтрис и нужно угадать, что у него в кармане?
Decoyfromptz
0 / 0 / 0
Регистрация: 10.10.2009
Сообщений: 4
11.10.2009, 12:39  [ТС]     Коммивояжер (бродячий торговец) #4
Цитата Сообщение от zim22 Посмотреть сообщение
а! это та задача, где коммивояжер играет в тэтрис и нужно угадать, что у него в кармане?
Нет, это задача о бродячем торговце, которому нужно обходить города, так чтобы сумарная длинна его пути была наименьшей.
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
11.10.2009, 13:22     Коммивояжер (бродячий торговец) #5
так или иначе в чём ваши затруднения?
Decoyfromptz
0 / 0 / 0
Регистрация: 10.10.2009
Сообщений: 4
11.10.2009, 14:08  [ТС]     Коммивояжер (бродячий торговец) #6
к примеру я генерирую все перестановки чисел.
Не могу организовать обход матриц стоимости, по каждой из последовательности.

P.S. Все в памяти не храню, все перестановки сохраняю в файле чтобы не держать в ram.

Добавлено через 27 секунд
P.P.S с алгоритмами у меня плоховато)))
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
11.10.2009, 15:23     Коммивояжер (бродячий торговец) #7
алгоритм посвоей сути прост:
1.если есть больше одного варианта перемещения, выбрать один, а остальные сохранить (в вашем случае в фаил).
2. когда в итоге упрётесь в конец пути, сравнить результат с имеющимся (для вас длина пути)
3. взять следующий вариатн из сохранённых
4. выполнять пока не исчерпаются все варианты
5. вывести правильный результат.

P.S. для вашего случая лучше с файлом не заморачиваться, рам у вас хватит с лихвой и проблем меньше. Иначе придётся каждый раз с файлом работать, когда добавить/удалить случай потребуется, в рам это, имхо, проще
P.S.S. Какой язык? С? С++?
Decoyfromptz
0 / 0 / 0
Регистрация: 10.10.2009
Сообщений: 4
11.10.2009, 20:03  [ТС]     Коммивояжер (бродячий торговец) #8
Почти закончил... По поводу экономии места в ram, просто это уже чисто мое, не люблю всякие вспомогательные данные в ней держать, да не смотря что ее 4 Гб)
Работать с файлом мне почему-то показалось проще, потому как за основу взял этот кусок

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std; 
void placement(int citems,int iter,int const cboxes,char* output)
{
        if(iter==citems)
                cout<<output<<'\n';
        else
                for(int i=0;i<cboxes;i++)
                {
                        if(output[i]!='0')
                                continue;
                        output[i]=49+iter;
                        placement(citems,iter+1,cboxes,output);
                        output[i]='0';
                }
}
 
int main()
{
        int n,m;
        cout<<"input count of items:";
        cin>>n;
        cout<<"\ninput count of boxes:";
        cin>>m;
        if(n>m)
        cout<<"No solutions";
        else
        {
                char* output=new char[m+1];
                for(int i=0;i<m;i++)
                        output[i]='0';
                output[m]=0;
                placement(n,0,m,output);
        }
        cout<<'\n';
        return 0;
}
Язык... Мммм, иногда на С, иногда C++... Мне без разницы, смотря что писать...
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
11.10.2009, 20:06     Коммивояжер (бродячий торговец) #9
Цитата Сообщение от Decoyfromptz Посмотреть сообщение
Почти закончил...
Язык... Мммм, иногда на С, иногда C++... Мне без разницы, смотря что писать...
имхо, подобное на С++ удобнее. со стандартными контейнерами особенно
Yandex
Объявления
11.10.2009, 20:06     Коммивояжер (бродячий торговец)
Ответ Создать тему
Опции темы

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