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

n4ela

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

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

Загрузка ...

Новичок

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

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

Надо решить задачу коммивояжера методом ветвей и границ. В гугле облазил все что можно( включая зарубежные сайты) нашел алгоритм Прима на Си, и на Си#, а мне надо метод ветвей и границ на Си/С++. Готового кода в интернете точно нету. Нашел код на TP, решил первести на Си. Вот что получилось:

Код


#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <fstream>
#define Max             20
#define Infty           30000
#define ToInfty         20000
#define MaxW            65535

typedef struct tmatrix
{
    int size;
    int indi[Max],indj[Max],indirev[Max],indjrev[Max];
    int data[Max][Max];
} tmatrix;

typedef struct tperm
{
    int size;
    int dir[Max], rev[Max];
} tperm;

typedef struct node
{
    tmatrix *c;
    tperm *solv;
    int est, got;
} node;

int best;
tperm *bsolv;
node mains;

int to0( tmatrix *c )
{
    int m = 0, res = 0;
    for ( int i = 0; i < c->size; i++ )
    {
        m = MaxW;
        for ( int j = 0; j < c->size; j++ )
            if ( c->data[i][j] <= m )
                m = c->data[i][j];
        for ( int j = 0; j < c->size; j++ )
            c->data[i][j] -= m;
        res += m;
    }
    for ( int j = 0; j < c->size; j++ )
    {
        m = MaxW;
        for ( int i = 0; i < c->size; i++ )
            if ( c->data[i][j] <= m )
                m = c->data[i][j];
        for ( int i = 0; i < c->size; i++ )
            c->data[i][j] -= m;
        res += m;
    }
    return res;
}

void choseedge( tmatrix *c, int &im, int &jm )
{
    int i = 0, j = 0, k = 0;
    int m = 0, m1 = 0;
    im = 0; jm = 0;
    for ( i = 0; i < c->size; i++ )
    {
        for ( j = 0; j < c->size; j++ )
            if ( c->data[i][j] == 0 )
                break;
        m1 = MaxW;
        for ( k = 0; k < c->size; k++ )
            if ( c->data[i][k] <= m1 && j != k )
                m1 = c->data[i][k];
    
        if ( m1 >= m )
        {
            m = m1;
            im = i;
            jm = j;
        }
    }
}

void add ( tperm *p, int i, int ip, tperm *res )
{
    res = new tperm;
    res = p;
    res->dir[i] = ip;
    res->rev[ip] = i;
}

void process( node &n )
{
    int i = 0, j = 0, k = 0, l = 0, i1 = 0, j1 = 0;
    node n1, n2;
    int first = 0;
    int los = 0;
    if ( n.c->size == 1 )
    { 
        if ( best >= n.got )
        {
            best = n.got;
            if ( bsolv != NULL )
                delete bsolv;
            add( n.solv, n.c->indi[0], n.c->indj[0], bsolv );
        }
    }
    else 
    {
        if ( n.est < best )
        {
            choseedge( n.c, i, j );
            n1.c = new tmatrix;
            n1.c->size = n.c->size-1;
            memset( n1.c->indi, 0, sizeof( n1.c->indi ) );
            memset( n1.c->indj, 0, sizeof( n1.c->indj ) );
            memset( n1.c->indirev, 0, sizeof( n1.c->indirev ) );
            memset( n1.c->indjrev, 0, sizeof( n1.c->indjrev ) );
            i1 = 0;
            first = 1;
            for ( k = 0; k < n.c->size; k++ )
                if ( k != i )
                {
                    i1++;
                    n1.c->indi[i1] = n.c->indi[k];
                    n1.c->indirev[n.c->indi[k]] = i1;
                    j1 = 0;
                    for ( l = 0; l < n.c->size; l++ )
                        if ( l!=j )
                        {
                            j1++;
                            if ( first )
                            {
                                n1.c->indj[j1] = n.c->indj[l];
                                n1.c->indjrev[n.c->indj[l]] = j1;
                            }
                            n1.c->data[i1][j1] = n.c->data[k][l];
                        }
                    first = 0;
                }
            k = n.c->indi[i];
            l = n.c->indj[j];
            add( n.solv, k, l, n1.solv );
            if ( n1.c->size > 1 )
            {
                i1 = k;
                while ( n1.solv->rev[i1] > 0 )
                    i1 = n1.solv->rev[i1];
                j1 = l;
                while ( n1.solv->dir[j1] > 0 )
                    j1 = n1.solv->dir[j1];
                if ( n1.c->indirev[j1] > 0 && n1.c->indjrev[i1] > 0 )
                    n1.c->data[n1.c->indirev[j1]][n1.c->indjrev[i1]] = Infty;
            }
            los = to0( n1.c );
            if ( los < ToInfty )
            {
                n1.est = n.est + los;
                n1.got = n.got + los;
                process( n1 );
            }
            n.c->data[i][j] = Infty;
            los = to0( n.c );
            if ( los < ToInfty )
            {
                n.est += los;
                n.got += los;
                process( n );
            }
        }
    }
}
void out()
{
    int i = 0;
    std::cout << "Shortest cycle: ";
    i = 1;
    do
    {
        std::cout << i << " ";
        i = bsolv->dir[i];
    } while ( i == 1 );
    std::cout << std::endl;
    std::cout << "Its length: " << best;
} 

void read()
{
    std::fstream file("input.txt", std::ios_base::in );
    mains.c = new tmatrix;
    mains.solv = new tperm;
    file >> mains.c->size;
    for ( int i = 0; i < mains.c->size; i++ )
    {
        mains.c->indi[i] = i;
        mains.c->indj[i] = i;
        mains.c->indirev[i] = i;
        mains.c->indjrev[i] = i;
    }
    for ( int i = 0; i < mains.c->size; i++ )
        for ( int j = 0; j < mains.c->size; j++ )
        {
            file >> mains.c->data[i][j];
            if ( i == j )
                mains.c->data[i][j] = Infty;
        }
    mains.solv->size = mains.c->size;
    memset( mains.solv->dir, sizeof( mains.solv->dir ), 0 );
    memset( mains.solv->rev, sizeof( mains.solv->rev ), 0 );
    mains.est = to0( mains.c );
    mains.got = mains.est;
    best = MaxW;
    bsolv = new tperm;
}
int main()
{
    read();
    process(mains);
    out();
    return 0;
}

http://paste.org.ru/?nefu2d
Оригинал на Паскале http://paste.org.ru/?xdqjoh
Входные данные:

Код


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

Мой код выдает ошибку сегментирования, видимо я напутал что то с указателями или выделением памяти, самом найти ошибку не получается.
Может кто то сможет помочь, и найти ошибку, или у кого то есть готовый пример на сях?
Заранее благодарен.
**********************
Решил написать с нуля, так что не актуально, всем спасибо.

Это сообщение отредактировал(а) n4ela - 25.9.2009, 01:51

bsa

Дата 23.9.2009, 15:14 (ссылка)

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

Загрузка ...

Эксперт

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

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

отладчиком пройдись. Хотя бы определишь, в каком месте сегфолт.
Если работает под Linux, то прогони через valgrind --tool=memcheck

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

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

ДобренькийПапаша

Дата 23.9.2009, 15:17 (ссылка)

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

Загрузка ...

Эксперт

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

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

маленький оффтопчик:
И не забудьте поставить ограничение на количество вершин, а то Ваша машина вряд ли поднимет NP-полную задачу smile

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

Меня зовут Себастьян Парейра, торговец чёрным деревом.

n4ela

Дата 23.9.2009, 16:32 (ссылка)

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

Загрузка ...

Новичок

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

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

Вылетает на 147 строчке,
Вот в этом месте:

Код


               i1 = k;
                while ( n1.solv->rev[i1] > 0 )
                    i1 = n1.solv->rev[i1];

Потому что в n1.solv->rev[i1] выходит за пределы памяти. А вот почему это происходит я не понял.

Anikmar

Дата 23.9.2009, 16:48 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

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

Странный какой-то цикл у вас

Ошибся, не туда глянул.

Это сообщение отредактировал(а) Anikmar - 23.9.2009, 16:48

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