VPF::Упрощение алгоритма - Форум программистов

sQu1rr

Дата 13.11.2009, 23:04 (ссылка)

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

Загрузка ...

Опытный

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

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

В школе проходит олимпиада по информатике. У меня появилось пара вопросов
Вот собственно задания
https://docs.google.com/fileview?id=0B579cK...jNzFl&hl=ru

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

Код


#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
using namespace std;

const size_t iNumOfRows = 3;

int myabs( int val ) {
    if( val < 0 )
        return ( -val );
    else
        return val;
}

struct sTriple {
    int iFir;
    int iSec;
    int iThr;
    size_t iFirPos;
    size_t iSecPos;
    size_t iThrPos;
    int Diameter() {
        int iBig = iFir;
        int iSml = iSec;
        if( iFir < iSec ) {
            iBig = iSec;
            iSml = iFir;
        }
        if( iThr > iBig )
            iBig = iThr;
        if( iThr < iSml )
            iSml = iThr;
        return myabs( iBig - iSml );
    }
};

void FindRightTriple( vector<int> & vFirst, vector<int> & vSecond, vector<int> & vThird, ostringstream & strResult );

int main() {
    // Variables
    size_t iArrSize;
    vector<int> vFirst;
    vector<int> vSecond;
    vector<int> vThird;
    vector<int> * pVector;
    ostringstream strResult;

    // Input File
    ifstream ifile("kolm.sis");
    ifile >> iArrSize;
    vFirst.reserve( iArrSize );
    vSecond.reserve( iArrSize );
    vThird.reserve( iArrSize );
    for( size_t iV = 0; iV < iNumOfRows; ++iV ) {
        if( iV == 0 ) pVector = &vFirst;
        if( iV == 1 ) pVector = &vSecond;
        if( iV == 2 ) pVector = &vThird;
        for( size_t iI = 0; iI < iArrSize; ++iI ) {
            int iTemp;
            ifile >> iTemp;
            pVector->push_back( iTemp );
        }
    }
    ifile.close();

    // Functions
    FindRightTriple( vFirst, vSecond, vThird, strResult );

    // Output File
    ofstream ofile("kolm.val");
    ofile << strResult.str();
    ofile.close();
    // End of Code

    return 0;
}

void FindRightTriple( vector<int> & vFirst, vector<int> & vSecond, vector<int> & vThird, ostringstream & strResult ) {
    sTriple rightTriple;
    size_t fPos, sPos, tPos;
    vector<int>::iterator ITF, ITS, ITT;
    for( ITF = vFirst.begin(), fPos = 1; ITF != vFirst.end(); ++ITF, ++fPos ) {
        sTriple tempTriple;
        tempTriple.iFir = *ITF;
        tempTriple.iFirPos = fPos;
        for( ITS = vSecond.begin(), sPos = 1; ITS != vSecond.end(); ++ITS, ++sPos ) {
            if( ITS == vSecond.begin() ) {
                tempTriple.iSec = *ITS;
                tempTriple.iSecPos = sPos;
            }
            else if( tempTriple.iFir == *ITS ) {
                tempTriple.iSec = *ITS;
                tempTriple.iSecPos = sPos;
                break;
            }
            else if( myabs( tempTriple.iFir - tempTriple.iSec ) > myabs( tempTriple.iFir - *ITS ) ) {
                tempTriple.iSec = *ITS;
                tempTriple.iSecPos = sPos;
            }
            else if( myabs( tempTriple.iFir - tempTriple.iSec ) < myabs( tempTriple.iFir - *ITS ) )
                break;
        }
        for( ITT = vThird.begin(), tPos = 1; ITT != vThird.end(); ++ITT, ++tPos ) {
            if( ITT == vThird.begin() ) {
                tempTriple.iThr = *ITT;
                tempTriple.iThrPos = tPos;
            }
            else if( tempTriple.iSec == *ITT  ) {
                tempTriple.iThr = *ITT;
                tempTriple.iThrPos = tPos;
                break;
            }
            else if( myabs( tempTriple.iSec - tempTriple.iThr ) > myabs( tempTriple.iSec - *ITT ) ) {
                tempTriple.iThr = *ITT;
                tempTriple.iThrPos = tPos;
            }
            else if( myabs( tempTriple.iSec - tempTriple.iThr ) < myabs( tempTriple.iSec - *ITT ) )
                break;
        }
        if( ( ITF == vFirst.begin() ) || ( rightTriple.Diameter() > tempTriple.Diameter() ) )
            rightTriple = tempTriple;
        if( tempTriple.Diameter() == 0 )
            break;
    }
    strResult << rightTriple.iFirPos << " " << rightTriple.iSecPos << " " << rightTriple.iThrPos << endl;
}

6. Алгоритм сделал, но это тупой перебор всех ходов. Ну не может компьютер за нормальное кол-во времени выполнить поиск путей если комнат больше 10. Или я чтото неправильно делаю, или я не могу найти более простого пути. Сделал через рекурсию.

Код


#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct sRoom {
    int iNum;
    vector<int> vWays;
    bool isPassed;
    bool isLast;
    bool operator == ( const sRoom & rhs ) { return rhs.iNum == iNum; }
};

__int64 FindAllWays( vector<sRoom> vRooms, int iNum );

int main() {
    // Variables
    int iArrSize = 0;
    int iWays;
    vector<sRoom> vRooms;

    // Input File
    ifstream ifile("rott.sis");
    ifile >> iArrSize;
    ifile >> iWays;
    for( int iI = 0; iI < iArrSize; ++iI ) {
        sRoom tempRoom;
        tempRoom.iNum = iI + 1;
        tempRoom.isPassed = false;
        tempRoom.isLast = false;
        if( iI == iArrSize - 1 )
            tempRoom.isLast = true;
        vRooms.push_back( tempRoom );
    }
    for( int iI = 0; iI < iWays; ++iI ) {
        int iTemp, iRec;
        ifile >> iTemp;
        sRoom findRoom;
        findRoom.iNum = iTemp;
        ifile >> iRec;
        (*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.push_back( iRec );
        findRoom.iNum = iRec;
        (*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.push_back( iTemp );
    }
    ifile.close();

    // Output
    ofstream ofile("rott.val");
    ofile << FindAllWays( vRooms, 1 );
    ofile.close();
    // End of Code
    return 0;
}

__int64 FindAllWays( vector<sRoom> vRooms, int iNum ) {
    __int64 iResult = 0;
    sRoom findRoom;
    findRoom.iNum = iNum;
    (*find( vRooms.begin(), vRooms.end(), findRoom )).isPassed = true;
    if( (*find( vRooms.begin(), vRooms.end(), findRoom )).isLast )
        return 1;
    for( vector<int>::iterator IT = (*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.begin(); IT < (*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.end(); ++IT ) {
        sRoom findNextRoom;
        findNextRoom.iNum = *IT;
        if( !(*find( vRooms.begin(), vRooms.end(), findNextRoom )).isPassed ) {
            iResult += FindAllWays( vRooms, *IT );
        }
    }
    return iResult;
}

Не то что нуждаюсь в помощи, а просто ради интереса. Учитывая то что 5 заданий я сделал ( 3 походу и так сойдет ), я прошел первый тур олимпиады. И всетаки хочется увидеть более простые и интересные решения

Abyx

Дата 14.11.2009, 00:11 (ссылка)

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

Загрузка ...

Опытный

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

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

3.
надо использовать то, что числа упорядочены по неубыванию
это значит, что
если у тройки A[i] < B[j] <= C[k] диаметр равен D[i][j][k]
то если A[i+1]<=B[j] то D[i+1][j][k]<=D[i][j][k]
а если A[i+1]>B[j], то последовательности меняются местами,
получается либо B[j] < A[i+1] <= C[k] либо B[j] <= C[k] <= A[i+1]
при этом, диаметр либо уменьшается, либьо увеличивается.
если уменьшается - следующий шаг, иначе сохраняем результат i,j,k как лучший найденный
и ищем дальше

Добавлено через 2 минуты и 6 секунд
6. классическая задача на графы. только перебор. читай гугл

sQu1rr

Дата 14.11.2009, 00:27 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Abyx @ 14.11.2009, 00:11

)

если уменьшается - следующий шаг, иначе сохраняем результат i,j,k как лучший найденный
и ищем дальше

У меня примерно так и сделано. Ну ваше решение немного получше будет. Спасибо )

Цитата(Abyx @ 14.11.2009, 00:11

)

классическая задача на графы. только перебор. читай гугл

А можно самый простой вариант, просто с графами сталкиваюсь первый раз. перебор то перебором, но было б неплохо какойнибудь быстрый вариант ( по производительности )

zkv

Дата 14.11.2009, 00:35 (ссылка)

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

Загрузка ...

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

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

Цитата(Abyx @ 14.11.2009, 00:11

)

6. классическая задача на графы. только перебор.

как бы неполный перебор. Принцип распространения волн Гюйгенеса может и должен (?) быть применен.
Судя по коду рабочей функции (FindAllWays()) это сделано в точном соответствии с ним.

sQu1rr

Дата 14.11.2009, 00:53 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(zkv @ 14.11.2009, 00:35

)

Судя по коду рабочей функции (FindAllWays()) это сделано в точном соответствии с ним.

Делал просто с логической точки зрения
Код медленный изза постоянного применения разных функций, я его уже чутка подправил, стал получше smile

А нету другого способа. Там значения до 10000 есть, а у меня 11 считает несколько минут на 4х ядерном core 2 ((((((

Подравил:

Код


__int64 FindAllWays( vector<sRoom> & vRooms, sRoom * pRoom ) {
    __int64 iResult = 0;
    pRoom->isPassed = true;
    if( pRoom->isLast )
        return 1;
    for( vector<sRoom *>::iterator IT = pRoom->vWays.begin(); IT < pRoom->vWays.end(); ++IT ) {
        if( !(*IT)->isPassed ) {
            vector<bool> vBool;
            vector<sRoom>::iterator ST;
            vector<bool>::iterator BT;
            for( ST = vRooms.begin(); ST < vRooms.end(); ++ST )
                vBool.push_back( (*ST).isPassed );
            iResult += FindAllWays( vRooms, *IT );
            for(  ST = vRooms.begin(), BT = vBool.begin(); ST < vRooms.end(); ++ST, ++BT )
                (*ST).isPassed = *BT;
        }
    }
    return iResult;
}

И всетаки работает ужасно медленно. 11 комнат с 66 ходами "изучает" аж 4.5 минуты. Не представляю что будет с 100 комнатами. а с 1000?

Это сообщение отредактировал(а) sQu1rr - 14.11.2009, 01:11

W4FhLF

Дата 14.11.2009, 09:17 (ссылка)

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

Загрузка ...

found myself

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

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

А какая теоретическая сложность у алгоритма?

Для оптимизации кода:

1. Откажись от использования vector<bool>. Очень медленный контейнер. Заюзая vector<unsigned char>.
2. vBool.push_back( (*ST).isPassed ); -- при вставке происходит постоянное перераспределение памяти. Тебе ведь заранее известен размер vBool, выделяй всю память при объявлении.
3.

Цитата(sQu1rr @ 14.11.2009, 00:53

)

Там значения до 10000 есть, а у меня 11 считает несколько минут на 4х ядерном core 2 ((((((

А ты где-то используешь параллельные вычисления? Что-то я не вижу.

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

"Бог умер" © Ницше
"Ницше умер" © Бог

Любитель

Дата 14.11.2009, 11:01 (ссылка)

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

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

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

Цитата(sQu1rr @ 13.11.2009, 23:04

)

(*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.push_back( iTemp );

От таких конструкций 100% лучше избавиться. Это же линейный проход по массиву! Учитывая, что твой оператор сравнения просто сравнивает номера - можно же просто обрашаться по индексу.

Код


for( ST = vRooms.begin(); ST < vRooms.end(); ++ST )
     vBool.push_back( (*ST).isPassed );
iResult += FindAllWays( vRooms, *IT );
for(  ST = vRooms.begin(), BT = vBool.begin(); ST < vRooms.end(); ++ST, ++BT )
    (*ST).isPassed = *BT;

Это тоже не понял. Ты хочешь полностью сохранить состояние посещённых комнат, а потом вернуть? Ну.. в принципе лучше это делать инкрементно (благо в данном случае это очень просто), но явно не делая два полных (!) прохода по всем комнатам. А вообще - само собой лучше избавиться от рекурсии (используя очередь).

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

http://oryolalex.mybrute.com

sQu1rr

Дата 14.11.2009, 12:53 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(W4FhLF @ 14.11.2009, 09:17

)

1. Откажись от использования vector<bool>. Очень медленный контейнер. Заюзая vector<unsigned char>.

Не думаю, что это слишком поможет. Ну увеличится скорость на пару десятков процентов... и что? У меня 150 комнат считает больше 10 часов (((

Цитата(W4FhLF @ 14.11.2009, 09:17

)

2. vBool.push_back( (*ST).isPassed ); -- при вставке происходит постоянное перераспределение памяти. Тебе ведь заранее известен размер vBool, выделяй всю память при объявлении.

Не подумал. Но это тоже не спасет производительность.

Цитата(W4FhLF @ 14.11.2009, 09:17

)

А ты где-то используешь параллельные вычисления? Что-то я не вижу.

Некогда не сталкивался с такой проблеммой, не умею

Цитата(Любитель @ 14.11.2009, 11:01

)

Попробую. исправить это

Цитата(Любитель @ 14.11.2009, 11:01

)

Так как vRooms содержит комнаты с указателями на комнаты, а копировать долго это все, то я просто сохраняю статус "пройденности" комнот перед рекурсией, потом восстанавливаю. Ато рекурсия работает пару раз, потом прекращается, так как все комнаты пройдены

Любитель

Дата 14.11.2009, 12:58 (ссылка)

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

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

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

Цитата(sQu1rr @ 14.11.2009, 12:53

)

На каждом шаге рекурсии ты заходишь в одну комнату. Её и помечаешь пройдённой. А в конце функции - убираешь этот флаг. Это я и называл инкрементным способом в данном случае (иначе - вычисление state[n+1] основано на state[n]).

И, ещё раз - вообще рекурсия (с достаточно большим уровнем вложенности, в данном случае - до M) - это большой удар по производительности.

Цитата(sQu1rr @ 14.11.2009, 12:53

)

ИМХО, vector<bool> как раз быстрее.

Цитата(W4FhLF @ 14.11.2009, 09:17

)

vBool.push_back( (*ST).isPassed ); -- при вставке происходит постоянное перераспределение памяти. Тебе ведь заранее известен размер vBool, выделяй всю память при объявлении.

Выигрыш без сомнения будет, но действительно не значителен.

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

http://oryolalex.mybrute.com

sQu1rr

Дата 14.11.2009, 13:03 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Любитель @ 14.11.2009, 12:58

)

Я чтото не догадался срасывать флаг вконце рекурсии
То что рекурсия все портит, согласен, но я просто не представляю, как можно сделать по другому (((

Цитата(Любитель @ 14.11.2009, 12:58

)

ИМХО, vector<bool> как раз быстрее.

Только что попробовал ваш "инкриментный способ". Время уменишилось почти в 250 раз. Тоесть вместо 4 минут задача решилась за 1 секунду.
Попробую дальше, Спасибо огромное!

Это сообщение отредактировал(а) sQu1rr - 14.11.2009, 13:10

Любитель

Дата 14.11.2009, 14:11 (ссылка)

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

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

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

Цитата(sQu1rr @ 14.11.2009, 13:03

)

То что рекурсия все портит, согласен, но я просто не представляю, как можно сделать по другому (((

Любую рекурсию можно развернуть с использование стека или очереди.

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

http://oryolalex.mybrute.com

sQu1rr

Дата 14.11.2009, 14:20 (ссылка)

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

Загрузка ...

Опытный

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

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

Даже если я так сделаю, скорость вряд ли увеличится на много. Думаю, что нужен другой алгоритм решения. Не представляю какой smile

Это сообщение отредактировал(а) sQu1rr - 14.11.2009, 14:20

Любитель

Дата 14.11.2009, 14:54 (ссылка)

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

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

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

Проигрыш при использовании рекурсии достаточно значителен. Алгоритм - по-моему, тут особо больше ничего не придумаешь.

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

http://oryolalex.mybrute.com

sQu1rr

Дата 14.11.2009, 15:48 (ссылка)

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

Загрузка ...

Опытный

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

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

Код


__int64 FindAllWays( cRoom ** paRooms, cRoom * pRoom, const int & iArrSize ) {
    // If last
    if( *pRoom == iArrSize )
        return 1;
    __int64 iResult = 0;
    pRoom->isPassed = true;
    int iI = 0;
    cRoom * pNextRoom = NULL;
    while( ( pNextRoom = (*pRoom)[iI++] ) != NULL ) {
        if( !pNextRoom->isPassed )
            iResult += FindAllWays( paRooms, pNextRoom, iArrSize );
    }
    pRoom->isPassed = false;
    return iResult;
}

Я пока что сделал так - время уменьшилось на 40%. Ушел от STL, теперь все полностью на стандартных типах.
Ща буду рекурсию переробатывать. Надеюсь получится. Если не сложно, опишите алгоритм именно для моей задачи. А то я чтото понять не могу ( *в размышлениях* )

Это сообщение отредактировал(а) sQu1rr - 14.11.2009, 15:53

Dov

Дата 14.11.2009, 18:14 (ссылка)

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

Загрузка ...

аСинизатор

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

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

Цитата(sQu1rr @ 13.11.2009, 22:04

)

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

А так не пойдёт? Я особо не тестировал.

Код

#define N 4

int minElem(int a, int b, int c)
{
    return (a < b && a < c ? a : b < c ? b : c);
}

int maxElem(int a, int b, int c)
{
    return (a > b && a > c ? a : b > c ? b : c);
}

void findVal(int* a, int* b, int* c, int size, int& imin, int& jmin, int& kmin)
{
    int i, j, k, mindiameter = INT_MAX;

    i = j = k = 0;
    while(i < size && j < size && k < size)
    {
        int max = maxElem(a[i], b[j], c[k]);

        while(i < size - 1 && a[i + 1] <= max)  i++;
        while(j < size - 1 && b[j + 1] <= max)  j++;
        while(k < size - 1 && c[k + 1] <= max)  k++;

        int min = minElem(a[i], b[j], c[k]);
        
        int diameter = max - min;
        if(diameter < mindiameter)
            mindiameter = diameter, imin = i + 1, jmin = j + 1, kmin = k + 1;

        min == a[i] ? i++ : min == b[j] ? j++ : k++;
    }
}

int main()
{
    int A[] = {0, 1, 2, 5};
    int B[] = {3, 4, 6, 7};
    int C[] = {0, 1, 2, 8};
    int i, j, k;

    findVal(A, B, C, N, i, j, k);
    cout << i << ' ' << j << ' ' << k << endl;

    return 0;
}

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

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

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