Слушаем задачу:

Лабиринт задан матрицей смежности n*n, де Сij = 1, если узел i связан с узлом j дорогой. Одну часть узлов назначили входами, другую выходами. Найти максимальное количество человек, которых можно провести от входов к выходам так, чтобы их пути не пересекались на путях и дорогах.

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

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

Я отмечаю все входы первыми номерами, а выходы - последними (в постановке задачи никаких ограничений по этому поводу нет, кроме того, какая графу разница, каков порядок его вершин? ), и при переходе по ссылке начинаю поиск дальнейшего пути с последних номеров. Проверял работу, вроде все четко, но нет все же какого-то обоснования жесткого...


Текст:

Код

Текст файла lab3.cpp #include "Matrix.h" #include <iostream> #include <stdio.h> #include <conio.h> #include <stdlib.h> using namespace std; int main() {    CLabirint Labirint; // создание объекта "лабиринт"    int numEntrance, // количество входов        numExit; // количество выходов    do{ //введение количества входов        fflush(stdin);        cout<<"Input number of entrances (from 1 to "<<matrSize<<") :"; cin>>numEntrance;    } while(numEntrance>=matrSize);    do{ //введение количества выходов        fflush(stdin);        cout<<"Input number of exits (from 1 to "<<matrSize-numEntrance<<") :"; cin>>numExit;    } while(numExit>matrSize-numEntrance);    Labirint.setEntrances( numEntrance ); // маркировка узлов-входов    Labirint.setExits( numExit ); // маркировка узлов-выходов    cout<<"\n\rThe matrix:\n\n";    Labirint.printMatr(); // вывод созданной матрицы на екран    int num=Labirint.searchMaxPathNum(); // поиск количества путей    cout<<"\n\nNumber of paths is "<<num<<"\nPress any key to exit.";    getch();  return 0; } Matrix.h — интерфейс класса #ifndef Matrix_h #define Matrix_h enum matrItemType { ENTRANCE, EXIT, VISITED, NOTLINK, LINK }; //тип данных элементов матрицы: // есть путь на вход, есть путь на выход, на посещенный узел, нет связи, есть связь с обычным узлом const int matrSize = 23; //размерность матрицы class CLabirint { public:    CLabirint( void ); // конструктор    void printMatr( void ); // метод вывода матрицы на екран.    void setEntrances( int ); // метод маркировки входов    void setExits( int ); // метод маркировки выходов      int searchMaxPathNum( void ); // метод поиска независимых путей private:    bool spider( int, int ); // метод поиска выхода. Аргументы: номер узла, на который переходит бот и номер входа, с которого начался  поиск    int searchShortPath( void ); // метод поиска прямых путей между входами и выходами    int maxPathNum; // искомое количество независимых путей    int longWays; // количество непрямых путей    int shortWays; // количество прямых путей    bool arrEntrance[matrSize]; // масив для запоминания входов. Узел номер i является входом, если элемент этого массива под тем же номером имеет значение true    bool arrExit[matrSize]; // аналогично для выходов    matrItemType matr[matrSize][matrSize]; // собственно сама матрица смежностей }; #endif Matrix.cpp — реализация класса #include "Matrix.h" #include <iostream> #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <time.h> //Условные обозначения элементов матрицы при выводе на екран #define entranseSymbol  "! " #define exitSymbol          "+ " #define notlinkSymbol     "0 " #define linkSymbol           "1 " #define visitedSymbol      "x " using namespace std; /////////////////// Конструктор класса //////////////////////////// CLabirint::CLabirint() {   maxPathNum = 0; // количество найденых путей   longWays = 0; // количество непрямых путей   shortWays = 0; //  количество прямых путей   srand( time(NULL) );    for( int i=0; i<matrSize; i++ ) {       for( int j=0; j<matrSize; j++ ) {          if( i==j ) matr[i][j] = NOTLINK; //на главной диагонали нули, граф не имеет петель          if( i<j ) matr[i][j] = rand()%2==0?NOTLINK:LINK; // случайным образом устанавливаем связь //Кстати, здесь двойку стоит заменить на какую-то переменную. Тогда пользователь сам сможет задавать степень разреженности матрицы, сделовательно количество ребер графа. Чем больше степень, тем дольше будут пути.       }    }    for( int i=0; i<matrSize; i++ ) {       for( int j=0; j<matrSize; j++ )          if( i>j ) matr[i][j] = matr[j][i]; // делаем матрицу симметричной    }    for( int i=0; i<matrSize; i++ ) { // инициализируем массивы входов и выходов       arrEntrance[i] = false;       arrExit[i] = false;    } } /////////////////// метод маркировки входов////////////////////////// void CLabirint::setEntrances( int num ) {    for ( int i=0; i<num; i++ ) {        for ( int j=0; j<matrSize; j++ ){ //просмотр связей            if ( matr[i][j]==LINK || matr[i][j]==ENTRANCE || matr[i][j]==EXIT ) { //если есть связь               matr[j][i] = ENTRANCE; //соответственно меняем обратную связь               arrEntrance[i] = true; //запоминаем номер узла            }        }    } } ///////////////// метод маркировки выходов///////////////////// void CLabirint::setExits( int num ) {   for ( int i=matrSize-1; i>=matrSize-num; i-- ) {       for ( int j=0; j<=matrSize; j++ ) {           if ( matr[i][j]==LINK||matr[i][j]==EXIT || matr[i][j]==ENTRANCE) {              matr[j][i] = EXIT;              arrExit[i] = true;           }       }   } } ///////////////// метод вывода матрицы на екран//////////////////// void CLabirint::printMatr() { cout<<" ";   for( int i=0; i<matrSize; i++ ) cout<<(i<9?" 0":" ")<<i+1; //выводим номера столбцов      for( int i=0; i<matrSize; i++ ) {         cout<<( i<9?"\n\r#0":"\n\r#" )<<i+1<<" |"; //номера строк         for( int j=0; j<matrSize; j++ ) {            switch( matr[i][j] ) { // выбираем элемент и выводим соответствующий символ               case ENTRANCE :cout<<entranseSymbol; break;               case EXIT :cout<<exitSymbol; break;               case VISITED :cout<<visitedSymbol; break;               case NOTLINK :cout<<notlinkSymbol; break;               case LINK :cout<<linkSymbol; break;            }         }       if( arrEntrance[i]==true ) cout<<" in";       if( arrExit[i]==true ) cout<<" out";     } } // метод поиска прямых путей, все просто// int CLabirint::searchShortPath() {  int num=0; //початкова кількість   for ( int i=0; i<matrSize; i++ ) {       if ( arrEntrance[i]==true ) {          for( int j=0; j<matrSize; j++ )             if( matr[i][j]==EXIT ) {                num++;                cout<<"\n#"<<num<<": "<<i+1<<"-"<<j+1;             }       }   } return num; } // метод поиска общего кол-ва независимых путей // int CLabirint::searchMaxPathNum() {  cout<<"\n\rLong ways:\n";    for ( int i=0; i<matrSize; i++ ) {        if ( arrEntrance[i]==true ) { // перебираем узлы, если текущий является входом, запускаем функцию поиска выхода           cout<<"\n";           spider(i,i);        }    } cout<<"\n\nShort ways: \n"; shortWays = searchShortPath(); cout<<"\n\rNumber of long ways: "<<longWays; cout<<"\n\rNumber of short ways: "<<shortWays; maxPathNum=shortWays+longWays; return maxPathNum; } ////////// рекурсивная функция, которая ищет ближайший выход. Аргументы: номер узла, с которого начинается поиск и номер входа, с которого она была запущена////////// bool CLabirint::spider( int start, int parent ) {  cout<<start+1<<"-"; // выводим номер текущего узла    for ( int i=matrSize-1; i>=0; i-- ) {        switch( matr[start][i] ) { // определяем тип элемента           case LINK: { // есть связь с і-тым узлом             matr[i][start]=VISITED; // отмечаем обратный узел               for( int j=0; j<matrSize; j++ ) { //отмечаем текущий узел                  if( matr[j][i]==LINK ) matr[j][i] = VISITED;               }             if( spider(i,parent)) break; // и переходим по линку на следующий узел            }            case EXIT: { // если попали на выход               if( start!=parent ) { // и если это не короткий путь                 longWays++; // увеличиваем количество найденых путей                 cout<<i+1<<"-exit\n"; // номер узла и уведомление о выходе                 return spider( parent,parent ); // запускаем функцию опять с того же входа               }            }            default:break; // если другой элемент, он нам нафиг не нужен        }    } }

Это сообщение отредактировал(а) kometa_triatlon - 15.1.2005, 20:49

Цитата(kometa_triatlon @ 9.1.2005, 00:04)

Лабіринт задано матрицею суміжності n*n, де Сij = 1, якщо вузол i зв'язаний з вузлом j дорогою. Одну частину вузлів призначено входами, а іншу - виходами. Знайти максимальну кількість осіб, яку можна провести від входів до виходів таким чином, щоб їх шляхи не перетиналися по дорогах та вузлах.

А по-русски нельзя?

Можно, но это надо переписывать...
А ты так не понимаешь?

Посмотри внимательно, какова география участников.
Наверное, только с Африки, Австралии и Антарктиды нет никого.

Тема перемещена из раздела "Алгоритмы".

Цитата(kometa_triatlon @ 9.1.2005, 01:04)

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

Неверно. Известная нерешаемая задача - соединить дорогами 3 дома и 3 колодца, каждый с каждым...

Переводить же с украинского (белорусского, церковнославянского и прочих) нет никакого желания - посему даже не читал.

Цитата

Неверно. Известная нерешаемая задача - соединить дорогами 3 дома и 3 колодца, каждый с каждым...

Планарность графа? Да ну, это не моя задача.

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

Возможен такой вариант: сделать из нашего графа сеть. Добавляем еще два узла - вход и выход. Все входы соединяем с истоком, все выходы со стоком. Все ребра между собой равнозначны. При этом условии ищем максимальный поток. Алгоритм не помню как называется, Новикова уже нет. Если кто знает, подскажите.
Но все-таки в таком виде решение очень громоздко...

Все, смотрим перевод...
Блин, посмотрите внимательней! Алгоритм чисто эвристический, но работает на ура.

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