Определение k-максимальных элементов

Для каждого БО определим 1-, 2-, 3-, 4-максимальные элементы.

При этом рассматриваются множества подчиненных, эквивалентных и несравнимых элементов. Специфика для определенных выше бинарных отношений заключается в том, что эквивалентным для каждого элемента является только он сам, а несравнимые с ним элементы как правило равнозначны. Поэтому 2- и 3-максимальных элементов получаем не 1, а множество, так как имеем несколько элементов, S-множества которых одной размерности, но разные по составу, то есть все эти элементы удовлетворяют определению k-максимальности. Этой же причиной объясняется отсутствие 1- и 4- максимальных элемента для тех БО, где несколько лидеров (они имеют одинаковые S-множества, то есть ни один не удовлетворяет определению k-максимальности).

Для каждого БО имеем k-максимальные элементы:

№	Бинарное отношение	1-max	2-max	3-max	4-max
	Общая площадь	G	G	G	G
	Цена	C	C	C	C
	Удаленность от метро	-	D F	D F	-
	Район	F	F	F	F
	Дом	G	G	G	G
	Состояние квартиры	-	E G	E G	-
	Размер кухни	G	G	G	G
	Этаж	-	A B D F G I J	A B D F G I J	-
	Наличие балкона	A	A	A	A
	Экология	G	G	G	G

Аналогично вышеописанным действиям, можно выбрать наилучший элемент с учетом весов признаков. Лучшим является вариант решения G.

Вывод

Таким образом, по всем рассматриваемым критериям оптимальным является вариант G:

	Sкварт	Цена, у.е.	До метро	Район	Дом	Состояние квартиры	Sкухни	Этаж	Балкон	Экология
G, ул. Фрунзе, 6			5 мин пешком	Московский	Кирпич после кап. ремонта	Отличное			Лоджия	Рядом Парк Победы, отличная

Программа

#include "stdio.h"

#include "math.h"

#include "conio.h"

//число критериев (бинарных отношений)

#define DIM 10

//число вариантов решения

#define ITEM_NUMBER 10

float weight[] = {0.15f, 0.3f, 0.1f, 0.05f, 0.1f, 0.15f, 0.05f, 0.03f, 0.02f, 0.05f};

//класс для матрицы, задающей каждое из бинарных отношений

class Matrix

{

int data[ITEM_NUMBER][ITEM_NUMBER];

public:

Matrix(){}

void SetElement(int i, int j, int value)

{

if ((i>ITEM_NUMBER) || (j>ITEM_NUMBER)) return;

data[i][j] = value;

}

int H_Enum(int *vector, int i)

{

int n = 0;

for (int j = 0; j < ITEM_NUMBER; j++)

{

if (i==j) continue;

//xRy and yNotRx

if ((data[i][j] == 1) && (data[j][i] == 0))

{

vector[n] = j;

n++;

}

}

return n;

}

int E_Enum(int *vector, int i)

{

int n = 0;

for (int j = 0; j < ITEM_NUMBER; j++)

{

//xRy and yRx

if (((data[i][j] == 1) && (data[j][i] == 1)) || (i == j))

{

vector[n] = j;

n++;

}

}

return n;

}

int N_Enum(int *vector, int i)

{

int n = 0;

for (int j = 0; j < ITEM_NUMBER; j++)

{

if (i==j) continue;

//xNotRy and yNotRx

if ((data[i][j] == 0) && (data[j][i] == 0))

{

vector[n] = j;

n++;

}

}

return n;

}

//считается, что множества упорядочены (это получается по построению,

//и объединение не нарушает порядка)

int UnionEnums(int *vector1, int *vector2, int n1, int n2, int *result)

{

int i,j,k;

i = 0; j = 0; k = 0;

bool ready = false;

while (!ready)

{

if ((i < n1) && (j < n2))

{

if (vector1[i] < vector2[j])

{

result[k] = vector1[i];

i++;

k++;

}

else

{

result[k] = vector2[j];

j++;

k++;

}

}

else if ((i < n1) || (j < n2))

{

if (i < n1)

{

while(i < n1)

{

result[k] = vector1[i];

i++;

k++;

}

ready = true;

}

if (j < n2)

{

while(j < n2)

{

result[k] = vector2[j];

j++;

k++;

}

ready = true;

}

}

else

{

ready = true;

}

}

return k;

}

//если равны или если vector1 содержится в vector2, то 1, в остальных случаях 0.

//Мн-ва д.б. упорядочены

int CompareEnums(int *vector1, int *vector2, int n1, int n2)

{

int i,j;

if (n1 > n2) return 0;//т.к. 1 должен сожердаться в 2, его размер д.б. меньше

if (n1 == n2)//проверить на равенство

{

for (i = 0; i < n1; i++)

{

if (vector1[i] != vector2[i])

{

return 0;

}

}

return 1;//раз досюда дошли, точно равенство

}

else//n1<n2

{

j = 0;

for(i = 0; i < n1; i++)

{

while ((vector1[i] != vector2[j]) && (j < n2)) j++;

if (j == n2) return 0;//не нашли подходящего элемента

//в противном случае нашли и все ок, идем дальше

}

}

return 1;

}

//Получить варианты решения по механизму доминирования

int Dominate(int *vector)

{

int i,j;

int n = 0;

for (i = 0; i < ITEM_NUMBER; i++)

{

bool dominate = true;

for (j = 0; j < ITEM_NUMBER; j++)

{

if (i==j)

continue;//диагональные элементы не проверяем

//если от него ко всем есть стрелки, то 1 д.б. во всей строчке (кроме i,i)

if (data[i][j] == 0)

{

dominate = false;

break;

}

}

if(dominate)

{

vector[n] = i;

n++;

}

}

return n;

}

//Получить варианты решения по механизму блокировки

int Block(int *vector)

{

int i,j;

int n = 0;

for (j = 0; j < ITEM_NUMBER; j++)

{

bool block = true;

for (i = 0; i < ITEM_NUMBER; i++)

{

if (i==j)

continue;//диагональные элементы не проверяем

//если к нему ни от кого нет стрелок, то 0 д.б. во всем столбце(кроме i,i)

if (data[i][j] == 1)

{

block = false;

break;

}

}

if(block)

{

vector[n] = j;

n++;

}

}

return n;

}

//получить варианты по турнирному механизму (fR(x) для каждого варианта)

void Tournament(float *vector)

{

int i,j;

for (i = 0; i < ITEM_NUMBER; i++)

{

vector[i] = 0;

for(j = 0; j < ITEM_NUMBER; j++)

{

if (i == j)

continue;

if ((data[i][j] == 1) && (data[j][i] == 0))

{

vector[i] += 1;

}

else if ((data[i][j] == 0) && (data[j][i] == 1))

{

vector[i] += 0;//ну типа для порядка

}

else

{

vector[i] += 0.5f;

}

}

}

}

void Print()

{

printf("\n");

for(int i = 0; i < ITEM_NUMBER; i++)

{

for(int j=0; j < ITEM_NUMBER; j++)

{

printf("%2d ",data[i][j]);

}

printf("\n");

}

}

};

void main()

{

int i,j,k;

Matrix System[DIM];

/***************************************************************************************/

FILE * inFile;

inFile = fopen("data.txt", "r");

for(k = 0; k < DIM; k++)

{

fscanf(inFile, "\n");//заголовок матрицы

for (i = 0; i < ITEM_NUMBER; i++)

{

for(j = 0; j < ITEM_NUMBER; j++)

{

int d;

fscanf(inFile, "%d",&d);

System[k].SetElement(i,j,d);

}

}

//printf("\nMatrix #%1d",k+1);

//System[k].Print();

}

fclose(inFile);

/**********************************************************************************/

printf("Dominating\n========================================================");

for(k = 0; k < DIM; k++)

{

int dominatingElement[ITEM_NUMBER];

int count = System[k].Dominate(dominatingElement);

printf("\nR #%d: ", k);

for(i = 0; i < count; i++)

{

printf("%c ", 65+dominatingElement[i]);

}

}

/*************************************************************************************/

printf("\n\nBlocking\n=========================================================");

for(k = 0; k < DIM; k++)

{

int blockingElement[ITEM_NUMBER];

int count = System[k].Block(blockingElement);

printf("\nR #%d: ", k);

for(i = 0; i < count; i++)

{

printf("%c ", 65+blockingElement[i]);

}

}

/***************************************************************************************/

printf("\n\nTournament\n========================================================");

float placesSum[ITEM_NUMBER];

for(k = 0; k < ITEM_NUMBER; k++)

{

placesSum[k] = 0;

}

for(k = 0; k < DIM; k++)

{

float tournamentRes[ITEM_NUMBER];

int systems[ITEM_NUMBER];

for (i = 0; i < ITEM_NUMBER; i++)

systems[i] = i;

System[k].Tournament(tournamentRes);

//sort

bool sorted = false;

while (!sorted)

{

sorted = true;

for(i = 0; i < ITEM_NUMBER-1; i++)

{

if (tournamentRes[i] < tournamentRes[i+1])

{

sorted = false;

float tr = tournamentRes[i];

tournamentRes[i] = tournamentRes[i+1];

tournamentRes[i+1] = tr;

int pl = systems[i];

systems[i] = systems[i+1];

systems[i+1] = pl;

}

}

}

//(места считаются с 1-ого, а не с нулевого)

int curPlace = 0;

int deltaPlace = 1;

float lastValue = -1;

//printf("\n\n-----------------\nR #%d\n", k);

for(i = 0; i < ITEM_NUMBER; i++)

{

//printf("%c %4.2f\n", systems[i]+65, tournamentRes[i]);

if (tournamentRes[i] == lastValue)

{

deltaPlace++;

}

else

{

lastValue = tournamentRes[i];

curPlace += deltaPlace;

deltaPlace = 1;

}

placesSum[systems[i]] += weight[k] * curPlace;

}

}

//sort Summary list and print it

int systems[ITEM_NUMBER];

for (i = 0; i < ITEM_NUMBER; i++)

systems[i] = i;

bool sorted = false;

while (!sorted)

{

sorted = true;

for(i = 0; i < ITEM_NUMBER-1; i++)

{

if (placesSum[i] > placesSum[i+1])

{

sorted = false;

float ps = placesSum[i];

placesSum[i] = placesSum[i+1];

placesSum[i+1] = ps;

int pl = systems[i];

systems[i] = systems[i+1];

systems[i+1] = pl;

}

}

}

//printf("\n\n-----------------\nTournament Summary");

printf("\n");

for(i = 0; i < ITEM_NUMBER; i++)

{

printf("%c %4.2f\n", systems[i]+65, placesSum[i]);

}

/**************************************************************************************/

printf("\n\n1 MAXIMUM\n========================================================");

for(k = 0; k < DIM; k++)

{

int kMax = 0;

int Max[ITEM_NUMBER];

//printf("\n\n-----------------");

printf("\nR #%d: ", k);

//каждый проверяем на возможность быть k-максимальным

for (i = 0; i < ITEM_NUMBER; i++)

{

int maxHNE[ITEM_NUMBER];

int maxHNEcount;

int H[ITEM_NUMBER];

int E[ITEM_NUMBER];

int N[ITEM_NUMBER];

int HN[ITEM_NUMBER];

int HNE[ITEM_NUMBER];

int countH, countE, countN, countHN, countHNE;

//получим нужную характеристику для рассматриваемого элемента

countH = System[k].H_Enum(H, i);

countN = System[k].N_Enum(N, i);

countE = System[k].E_Enum(E, i);

countHN = System[k].UnionEnums(N, H, countN, countH, HN);

maxHNEcount = System[k].UnionEnums(E, HN, countE, countHN, maxHNE);

bool valid = true;

//проверяем по остальным элементам

for (j = 0; j < ITEM_NUMBER; j++)

{

if (i == j) continue;

countH = System[k].H_Enum(H, j);

countN = System[k].N_Enum(N, j);

countE = System[k].E_Enum(E, j);

countHN = System[k].UnionEnums(N, H, countN, countH, HN);

countHNE = System[k].UnionEnums(E, HN, countE, countHN, HNE);

//если есть такой элемент, что maxS в его S, то i - не k-max

if(System[k].CompareEnums(maxHNE, HNE, maxHNEcount, countHNE))

{

valid = false;

break;

}

}

if (valid)

{

Max[kMax] = i;

kMax++;

}

}

if (kMax)

{

for(i = 0; i < kMax; i++)

{

printf(" %c", Max[i]+65);

}

}

else

{

printf(" No 1 MAX");

}

}

/***************************************************************************************/

printf("\n\n2 MAXIMUM\n=======================================================");

for(k = 0; k < DIM; k++)

{

int kMax = 0;

int Max[ITEM_NUMBER];

//printf("\n\n-----------------");

printf("\nR #%d: ", k);

int l = -1;

//каждый проверяем на возможность быть k-максимальным

for (i = 0; i < ITEM_NUMBER; i++)

{

int maxHN[ITEM_NUMBER];

int maxHNcount;

int H[ITEM_NUMBER];

int N[ITEM_NUMBER];

int HN[ITEM_NUMBER];

int countH, countN, countHN;

//получим нужную характеристику для рассматриваемого элемента

countH = System[k].H_Enum(H, i);

countN = System[k].N_Enum(N, i);

maxHNcount = System[k].UnionEnums(N, H, countN, countH, maxHN);

bool valid = true;

//проверяем по остальным элементам

for (j = 0; j < ITEM_NUMBER; j++)

{

if (i == j) continue;

countH = System[k].H_Enum(H, j);

countN = System[k].N_Enum(N, j);

countHN = System[k].UnionEnums(N, H, countN, countH, HN);

//если есть такой элемент, что maxS в его S, то i - не k-max

if(System[k].CompareEnums(maxHN, HN, maxHNcount, countHN))

{

valid = false;

break;

}

}

if (valid)

{

Max[kMax] = i;

kMax++;

}

}

if (kMax)

{

for(i = 0; i < kMax; i++)

{

printf(" %c", Max[i]+65);

}

}

else

{

printf(" No 2 MAX");

}

}

/***************************************************************************************/

printf("\n\n3 MAXIMUM\n====================================================");

for(k = 0; k < DIM; k++)

{

int kMax = 0;

int Max[ITEM_NUMBER];

//printf("\n\n-----------------");

printf("\nR #%d: ", k);

//каждый проверяем на возможность быть k-максимальным

for (i = 0; i < ITEM_NUMBER; i++)

{

int maxHE[ITEM_NUMBER];

int maxHEcount;

int H[ITEM_NUMBER];

int E[ITEM_NUMBER];

int HE[ITEM_NUMBER];

int countH, countE, countHE;

//получим нужную характеристику для рассматриваемого элемента

countH = System[k].H_Enum(H, i);

countE = System[k].E_Enum(E, i);

maxHEcount = System[k].UnionEnums(E, H, countE, countH, maxHE);

bool valid = true;

//проверяем по остальным элементам

for (j = 0; j < ITEM_NUMBER; j++)

{

if (i == j) continue;

countH = System[k].H_Enum(H, j);

countE = System[k].E_Enum(E, j);

countHE = System[k].UnionEnums(E, H, countE, countH, HE);

//если есть такой элемент, что maxS в его S, то i - не k-max

if(System[k].CompareEnums(maxHE, HE, maxHEcount, countHE))

{

valid = false;

break;

}

}

if (valid)

{

Max[kMax] = i;

kMax++;

}

}

if (kMax)

{

for(i = 0; i < kMax; i++)

{

printf(" %c", Max[i]+65);

}

}

else

{

printf(" No 3 MAX");

}

}

/***************************************************************************************/

printf("\n\n4 MAXIMUM\n==================================================");

for(k = 0; k < DIM; k++)

{

int kMax = 0;

int Max[ITEM_NUMBER];

//printf("\n\n-----------------");

printf("\nR #%d: ", k);

//каждый проверяем на возможность быть k-максимальным

for (i = 0; i < ITEM_NUMBER; i++)

{

int maxH[ITEM_NUMBER];

int maxHcount;

int H[ITEM_NUMBER];

int countH;

//получим нужную характеристику для рассматриваемого элемента

maxHcount = System[k].H_Enum(maxH, i);

bool valid = true;

//проверяем по остальным элементам

for (j = 0; j < ITEM_NUMBER; j++)

{

if (i == j) continue;

countH = System[k].H_Enum(H, j);

//если есть такой элемент, что maxS в его S, то i - не k-max

if(System[k].CompareEnums(maxH, H, maxHcount, countH))

{

valid = false;

break;

}

}

if (valid)

{

Max[kMax] = i;

kMax++;

}

}

if (kMax)

{

for(i = 0; i < kMax; i++)

{

printf(" %c", Max[i]+65);

}

}

else

{

printf(" No 4 MAX");

}

}

getch();

}