Определение k-максимальных элементов
Для каждого БО определим 1-, 2-, 3-, 4-максимальные элементы. При этом рассматриваются множества подчиненных, эквивалентных и несравнимых элементов. Специфика для определенных выше бинарных отношений заключается в том, что эквивалентным для каждого элемента является только он сам, а несравнимые с ним элементы как правило равнозначны. Поэтому 2- и 3-максимальных элементов получаем не 1, а множество, так как имеем несколько элементов, S-множества которых одной размерности, но разные по составу, то есть все эти элементы удовлетворяют определению k-максимальности. Этой же причиной объясняется отсутствие 1- и 4- максимальных элемента для тех БО, где несколько лидеров (они имеют одинаковые S-множества, то есть ни один не удовлетворяет определению k-максимальности).
Для каждого БО имеем k-максимальные элементы:
Аналогично вышеописанным действиям, можно выбрать наилучший элемент с учетом весов признаков. Лучшим является вариант решения G. Вывод Таким образом, по всем рассматриваемым критериям оптимальным является вариант G:
Программа #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(); }
Популярное: Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (796)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |