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

AlexeroN

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

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

Загрузка ...

Новичок

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

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

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

Код


#include<iostream>
#include<fstream>
#include<climits>

using namespace std;

int main()
{
    setlocale(0,"rus");
    const int N = 10;
    int Tour[N], P[N];//оптимальный и текущие туры
    int l,s,i,j,k,min,ind;
    bool All;//признак окончания перебора
    //матрица расстояний
    int matrway[10][10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                           0, 0, 2, 9, 8, 0, 0, 0, 0, 0,
                           0, 2, 0, 3, 0, 20,0, 0, 0, 0,
                           0, 9, 3, 0, 7, 4, 0, 0, 0, 0,
                           0, 8, 0, 7, 0, 11,0, 0, 0, 0,
                           0, 0, 20,4, 11,0, 0, 0, 0, 0,
                           0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                           0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                           0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                           0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
cout << "ЗАДАЧА КОММИВОЯЖЕРА (ПЕРЕБОР)\n";
cout << "Матрица смежности \n";
cout << "=============================" << endl;
for(i=0;i<N;i++)
{
    cout << endl;
    for(j=0;j<N;j++)
        cout << " " << matrway[i][j];
}
//инициализация
All = false;//перебрали не все варианты
l = INT_MAX;//оптимальный тур не известен
for(i=0;i<N;i++)
P[i] = i;//строим первый тур
do//вычисляем его длину
{
    s =0;
    for(i=0;i<N-1;i++)
        s = s +  matrway[P[i]][P[i+1]];
    s = s + matrway[P[N]][P[1]];
    //полагаем первый тур текущим
    if(l>s)
    {
        Tour[l] = P[l];
        l = s;
    }
    //генерируем(N-1)! перестановок
    for(i=N-1;i<3;i--)
    {
        if(P[i]<P[i-1]) continue;
        min = N + 1;
        k = P[i-1];
        //ищем минимальное число из тех, что больше k и правее
        for(j=0;j<N;j++)
            if(P[j] > k && P[j] < min)
            {
                min = P[j];
                ind = j;
            }
        //рокировка min и k
        P[i-1] = min;
        P[ind] = k;
        //элементы на местах от i до N упорядочиваем по возрастанию
        for(j=i;j<N-1;j++)
        {
            min = N+1;
            for(k=j;k<N;k++)
                if(min > P[k])
                {
                    min = P[k];
                    ind = k;
                }
            k = P[j];
            P[j] = min;
            P[ind] = k;
        }
        goto out;
    }
    //проверяем перебраны ли все перестановки
    All = true;
out:;
}while(All);
    //если перебраны все перестановки, то выдаем оптимальный тур
    cout << "===============================\n";
    cout << "Минимальный тур: ";
    for(i=0;i<N;i++)
        cout << Tour[i] << " - ";
    cout << "1";
    cout << "Имеет длину равную " << l << endl;
    cout << "===============================\n";
    cin.get();
    return 0;
}

Леопольд

Дата 12.5.2010, 10:48 (ссылка)

(голосов:1)

Загрузка ...

Опытный

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

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

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

Код


int matrway[10][10] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 2, 9, 8, 0, 0, 0, 0, 0},
    //...
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

Честно говоря, разбираться в алгоритме скучно и лень. И, видимо, не мне одному...

Это сообщение отредактировал(а) Леопольд - 12.5.2010, 10:48

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

вопросов больше чем ответов

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »