Есть табличка 10*10. Заполняется случайным образом. Три состояния: 0, 1, и галочка
. Требуется отобрать строчки таким образом, чтобы в каждом столбце была бы по крайней мере одна галочка, а число строк было минимальным.
Предположительно "6-ой пункт метода Квайна-Мак Класски"
Здравствуйте Nikulina, Вы писали:
N>Есть табличка 10*10. Заполняется случайным образом. Три состояния: 0, 1, и галочка . Требуется отобрать строчки таким образом, чтобы в каждом столбце была бы по крайней мере одна галочка, а число строк было минимальным.
N>Предположительно "6-ой пункт метода Квайна-Мак Класски"
Кроме рекурсии
Добавлять строки по одной до тех пор пока не заполнятся все 10 столбцов или не кончатся строки.
если строка не добавляет стобцов с галочками не добавлять её.
если нашли решение сравнить с предыдушим если строк меньше запомнить.
потребуется (в худшем случае) 10! = 3628800 попыток что ещё более или менее приемлемо
для динамических и волновых методов потребуется судя по всему памяти порядка 10!^2 = 13168189440000 что уже НЕ приемлемо
Можно составить граф из 3628800 вершин соеденить рёбрами переходы (добавление той или инной строки) и искать кратчайший путь от состояния где чалочек нет к состоянию где галочки есть памяти порядка 13168189440000 операций столько же
Так что старая добрая рекурсия, впрочем если больше 10x10 тогда и ей туговато
Здравствуйте Nikulina, Вы писали:
N>Есть табличка 10*10. Заполняется случайным образом. Три состояния: 0, 1, и галочка :) . Требуется отобрать строчки таким образом, чтобы в каждом столбце была бы по крайней мере одна галочка, а число строк было минимальным.
N>Предположительно "6-ой пункт метода Квайна-Мак Класски" ;)
Первое что пришло в голову:
В общем легко обопщить до NxM.
тк интересуют только галочки то упростим 1-галочка 0-что угодно.
Матрица A[NxM]
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 1 0 0 1
0 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 1 0 1 0 0
0 0 1 0 0 0 0 0 0 0
Вектор V[M]
1 3 2 2 1 2 1 3 1 2
решаем рекурсией
инициализация: суммируем столбци и помещаем результат в V если есть хотябы один ноль то нет решения иначе A лущшее решение(на данный момент)
пробуем удалить каждую строку из V вычетаем M[i] если получаем хотябы один ноль то удалить не возможно пробуем следующею иначе переходим на еследующий уровень рекурсии
если ни одну строку удалить не удалось и колличество строк меньше чем у лучшей то текущею запоминаем как лучшею
возвращаемся из рекурсии если вернуться не куда то решение найдено.
Best regards,
WolfHound
Здравствуйте Nikulina, Вы писали:
N>Есть табличка 10*10. Заполняется случайным образом. Три состояния: 0, 1, и галочка . Требуется отобрать строчки таким образом, чтобы в каждом столбце была бы по крайней мере одна галочка, а число строк было минимальным.
N>Предположительно "6-ой пункт метода Квайна-Мак Класски"
Предлагаю вариант
, находящий решение за 2^10-1 сравнений
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
const int Size=10;
const int Full = (1<<Size) - 1;
int T[Size];
void Check(int *A, int maxLevel)
{
for(int i=0, x=0; i<=maxLevel; i++){
x = x | T[A[i]];
}
if(x == Full){
printf("Yes, Yes, Yesss !!!\n");
for(int i=0; i<=maxLevel; i++)
printf("%4d", A[i]);
printf("\n");
exit(0);
}
}
void Permute(int *A, int Val, int Level, int maxVal, int maxLevel)
{
for(; Val<maxVal-maxLevel+Level; Val++){
A[Level] = Val;
if(Level == maxLevel)
Check(A, maxLevel);
else
Permute(A, Val+1, Level+1, maxVal, maxLevel);
}
}
void main()
{
int A[Size];
// Fill table
srand(time(NULL));
for(int i=0; i<Size; i++){
T[i] = rand()*rand() % (Full+1);
}
// Output table
for(i=0; i<Size; i++){
printf("%2d: ", i);
for(int j=0; j<Size; j++){
if(T[i] & (1<<j)) printf("V");
else printf(".");
}
printf("\n");
}
// Go !
for(i=0; i<=Size; i++)
Permute(A, 0, 0, Size, i);
}
Имеем:
0123456789
----------
0: VV.V...VV.
1: ....V.VV..
2: ..VV.VVV.V
3: .V...V...V
4: .V.VVV...V
5: ...VV.VVVV
6: VVVVV.VV..
7: ...V.V....
8: ..V.V..V..
9: VVV..VV..V
----------
Yes, Yes, Yesss !!!
5 9
