Слушаем задачу:
Лабиринт задан матрицей смежности 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; // если другой элемент, он нам нафиг не нужен
}
}
}
|
|