VPF::Задача коммивояжера - Форум программистов

Invisible

Дата 13.5.2006, 21:29 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 63
Регистрация: 26.5.2005

Репутация: нет
Всего: нет

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

Это сообщение отредактировал(а) Invisible - 13.5.2006, 21:31

Dov

Дата 13.5.2006, 22:53 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: нет
Всего: 88

Invisible, пойди в раздел АЛГОРИТМЫ и сделай поиск по ключевым словам, наверняка там что-нибудь накопаешь.

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

bsa

Дата 14.5.2006, 01:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: нет
Всего: 196

Все просто. Представляешь город, как структуру, одно из полей которой содержит список всех примыкающих городов (тех, с которыми есть непосредственная связь) и растояний до них...

Код

struct town;
struct totown {
      struct town * town;        //указатель на город
      int distance;                    //рассояние от текущего города до того, на который указывает ссылка
};

struct town {
      std::string name;                        //название города (например)
      std::list<struct totown> towns;  //список всех городов, с которыми есть непосредственная связь
};

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

dips

Дата 14.5.2006, 07:27 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 12.5.2006

Репутация: нет
Всего: нет

Вот тебе пример решения задачи методом перебора,
тут всё описано, правда на паскале, ну мне в своё
время этого вполне хватило чтоб понять суть

Присоединённый файл ( Кол-во скачиваний: 173 )

Voyager.doc 76,00 Kb

bsa

Дата 15.5.2006, 15:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: нет
Всего: 196

В приведенном примере struct totown - это описатель маршрута до соседнего города, а struct town - это описатель самого города.
Таким образом, каждый город имеет список маршрутов к соседним городам.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Mayk

Дата 15.5.2006, 18:51 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 2
Всего: 134

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

Модератор: перемещено в алгоритмы

Это сообщение отредактировал(а) Mayk - 15.5.2006, 19:03

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Invisible

Дата 24.5.2006, 22:14 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 63
Регистрация: 26.5.2005

Репутация: нет
Всего: нет

итак, есть конкретное решение на MVC , здача коммивояжера

Код


/*задача коммивояжёра

Коммивояжёр (бродячий торговец) должен выйти из первого города, посетить по разу
в неизвестном порядке города и вернуться в первый город.
Расстояние между городами известны. В каком порядке следует обходить города,
чтобы замкнутый путь (тур) коммивояжёра был кротчайшим.
Иными словами, коммивояжёр должен обойти все города по кротчайшему пути и
при этом посещая каждый город только один раз.
Расстояния берутся из файла. В файле матрица с произвольными правильными
значениями (т.е. значение не отрицательны и такие, что проход коммивояжёром
всех городов возможен).
Программа ищет путь с помощью метода ветвей и границ.
*/
#include <fstream.h>
const int maxn=100;                //максимум городов
int n,i,s,min,count,found;        //n-количество городов
                                //i-счетчик
                                //s-текущая сумма
                                //min-минимальная сумма
                                //count-счетчик пройденных городов
                                //found-найден ли город
int a[maxn][maxn];                //матрица рассояний
int m[maxn],minm[maxn];            //m-текущий путь
                                //minm-минимальный путь

void _input()                    //ввод данных
{
 ifstream fin("input.txt");     //открыли файл
 fin >> n;                        //считали n
 for (int i=1;i<=n;i++)    
   for (int j=1;j<=n;j++)
    fin >> a[i][j];                //считали матрицу расстояний
}

void _output()                    //вывод данных
{
 ofstream fout("output.txt");   //открыли файл
 if (found)                        //если найден маршрут...
    {
    fout << "Lenght of min path = " << min << endl;
    fout << "Path : ";
    int c=1;                    //номер в порядке обхода городов
    for (int i=1;i<=n;i++)      //пробегаем по всем городам
    {
    int j=1;
    while ((j<=n)&&                //ищем следующий город в порядке обхода    
               (minm[j]!=c)) j++;
    fout << j <<"->";
    c++;
    }
    fout << minm[1] << endl;    //обход завершается первым городом
    }
    else fout << "Path not found!";
}
void search(int x)                //поиск следующего города в порядке 
                                //обхода после города с номером Х
{
if ((count==n)&&                //если просмотрели все города
    (a[x][1]!=0)&&                //из последнего города есть путь в первый город
    (s+a[x][1]<min))            //новая сумма расстояний меньше минимальной суммы
     {
     found=1;                    //маршрут найден
     min=s+a[x][1];                //изменяем: новая минимальная сумма расстояний
     for (int i=1;i<=n;i++)minm[i]=m[i];//изменяем: новый минимальный путь
     }
     else
     {
     for (int i=1;i<=n;i++)     //из текущего города просматриваем все города
    if ((i!=x)&&                //новый город не совпадает с текущим    
        (a[x][i]!=0)&&            //есть прямой путь из x в i
            (m[i]==0)&&            //новый город еще не простотрен
            (s+a[x][i]<min))    //текущая сумма не превышает минимальной
        {
        s+=a[x][i];                //наращиваем сумму
        count++;                //количество просмотренных городав
        m[i]=count;                //отмечаем у нового города новый номер в порядке обхода
        search(i);                //поиск нового города начиная с города i
        m[i]=0;                    //возвращаем все назад
        count--;                //-"-
        s-=a[x][i];                //-"-
        }
     }
}
void run()
{                                //инициализация                                
s=0;
found=0;
min=32767;
for (int i=1;i<=n;i++) m[i]=0;
count=1;
m[1]=count;                        //считаем что поиск начинается с первого города
search(1);                        //считаем что поиск начинается с первого города
}

void main()
{
_input();                        //ввод данных
run();                            //запуск основного алгоритма
_output();                        //вывод результатов
}

пример файла input.txt

Код


4

0    6    1    5
6    0    3    1
1    3    0    2
5    1    2    0

Юля4310

Дата 18.5.2009, 16:24 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 41
Регистрация: 18.5.2009

Репутация: нет
Всего: нет

а нельзя эту программу перевести на Delphi? очень очень надо, помогите пожалуйста

aleksanr

Дата 5.6.2009, 16:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 28.5.2009

Репутация: нет
Всего: нет

при компиляция данная прога выдает ошибку

Ошибка 3 error C2872: min: неоднозначный символ

помогите ее исправить пожалуста!!!!!

n4ela

Дата 22.9.2009, 01:22 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 15.8.2009

Репутация: нет
Всего: нет

Я может быть археолог, но в примере выше разве не метод полного перебора?

maxim1000

Дата 22.9.2009, 08:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

думаю, гораздо больше потенциальных помощников перевести на Delphi будет в разделе Delphi, так что с подобными вопросами стоит обратиться туда

то же самое с min - тут лучше обратиться в C++-раздел

--------------------

qqq

AlexeroN

Дата 10.5.2010, 12:32 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 32
Регистрация: 10.11.2009
Где: Екатеринбург

Репутация: нет
Всего: нет

Про ошибку можно почитать тут http://msdn.microsoft.com/ru-ru/library/t57wswcs.aspx
А я решил проблему элементарно, просто в этом min добавил подчерк, чтоб было _min, и все ок

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »