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

@Decoyfromptz · Регистрация: 10.10.2009

Студворк — интернет-сервис помощи студентам

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

Зарание спасибо.

@TanT · 11.10.2009, 10:26

Хорошая и основательная задачка.
Показывай, что есть, поможем.
Готовый код был в интернете, но за него просили деньги (где-то натыкался).
Я реализовывал подобное, но там были условия по жёстче и ограничение на время, полный перебор не катил (шибко долго).

@zim22 · 11.10.2009, 11:54

Сообщение от Decoyfromptz

Ребят, помогите с реализацией задачи о коммивояжере,

а! это та задача, где коммивояжер играет в тэтрис и нужно угадать, что у него в кармане?

@Decoyfromptz · 11.10.2009, 12:39 **[ТС]**

Сообщение от zim22

а! это та задача, где коммивояжер играет в тэтрис и нужно угадать, что у него в кармане?

Нет, это задача о бродячем торговце, которому нужно обходить города, так чтобы сумарная длинна его пути была наименьшей.

@TanT · 11.10.2009, 13:22

так или иначе в чём ваши затруднения?

@Decoyfromptz · 11.10.2009, 14:08 **[ТС]**

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

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

Добавлено через 27 секунд
P.P.S с алгоритмами у меня плоховато)))

@TanT · 11.10.2009, 15:23

алгоритм посвоей сути прост:
1.если есть больше одного варианта перемещения, выбрать один, а остальные сохранить (в вашем случае в фаил).
2. когда в итоге упрётесь в конец пути, сравнить результат с имеющимся (для вас длина пути)
3. взять следующий вариатн из сохранённых
4. выполнять пока не исчерпаются все варианты
5. вывести правильный результат.

P.S. для вашего случая лучше с файлом не заморачиваться, рам у вас хватит с лихвой и проблем меньше. Иначе придётся каждый раз с файлом работать, когда добавить/удалить случай потребуется, в рам это, имхо, проще
P.S.S. Какой язык? С? С++?

@Decoyfromptz · 11.10.2009, 20:03 **[ТС]**

Почти закончил... По поводу экономии места в 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 · 11.10.2009, 20:06

Сообщение от Decoyfromptz

Почти закончил...
Язык... Мммм, иногда на С, иногда C++... Мне без разницы, смотря что писать...

имхо, подобное на С++ удобнее. со стандартными контейнерами особенно

Новые блоги и статьи Все статьи Все блоги /
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .

@Decoyfromptz 0 / 0 / 0 Регистрация: 10.10.2009 Сообщений: 4

	Коммивояжер (бродячий торговец) 10.10.2009, 21:53. Показов 6058. Ответов 8 Метки нет (Все метки) Ребят, помогите с реализацией задачи о коммивояжере, желательно простое решение полным перебором: потому как, входные данные будут больше не больше 10 городов, а 9! - вполне решабильно. У меня есть некоторые наработки, но сроки поджимать начинают, поэтому прошу помощи.... Зарание спасибо. 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	11.10.2009, 10:26
	Хорошая и основательная задачка. Показывай, что есть, поможем. Готовый код был в интернете, но за него просили деньги (где-то натыкался). Я реализовывал подобное, но там были условия по жёстче и ограничение на время, полный перебор не катил (шибко долго). 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	11.10.2009, 13:22
	так или иначе в чём ваши затруднения? 0

@Decoyfromptz 0 / 0 / 0 Регистрация: 10.10.2009 Сообщений: 4
	11.10.2009, 14:08 [ТС]
	к примеру я генерирую все перестановки чисел. Не могу организовать обход матриц стоимости, по каждой из последовательности. P.S. Все в памяти не храню, все перестановки сохраняю в файле чтобы не держать в ram. Добавлено через 27 секунд P.P.S с алгоритмами у меня плоховато))) 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	11.10.2009, 15:23
	алгоритм посвоей сути прост: 1.если есть больше одного варианта перемещения, выбрать один, а остальные сохранить (в вашем случае в фаил). 2. когда в итоге упрётесь в конец пути, сравнить результат с имеющимся (для вас длина пути) 3. взять следующий вариатн из сохранённых 4. выполнять пока не исчерпаются все варианты 5. вывести правильный результат. P.S. для вашего случая лучше с файлом не заморачиваться, рам у вас хватит с лихвой и проблем меньше. Иначе придётся каждый раз с файлом работать, когда добавить/удалить случай потребуется, в рам это, имхо, проще P.S.S. Какой язык? С? С++? 0