Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: 1
RSS
Есть двумерный массив из нулей и единиц., Найти минимальное количество строк, которые бы образовали строку только из единиц.
 
#1
11.10.2013 16:36:57
сравниваю первую строку со всеми строками.
Но скорее это не правильно, т.к. нужно найти минимально количество строк удовлетворяющих условию.
Смысл собрать строку из одних единиц, взяв минимальное число строк из массива.

Накатал такой цикл, может подскажите что-нить побыстрее(поумнее) чем это:

Код
Do
k = k + 1 
max = 0 'введем переменную для учета максимального количества закрытия единицами нулей
For i = 1 To UBound(massiv1, 1)
    Perekritie = 0
        For j = 1 To UBound(massiv1, 1)
                If PoleSovpaden(1, j) = 0And PoleSovpaden(i, j) = 1 Then Perekritie = Perekritie + 1
        Next j
        PerekritieM(i) = Perekritie 'запоминаем сумму перекрытий i-ой строки
        If PerekritieM(i) > max Then
           max = PerekritieM(i)
           n = i ' переменная для номера строки имеющего максимальное совпадение с первой строкой.
        If max = Pred_Max Then Exit For 'если достигнуто предыдущее число совпадений то нет смысла дальше вести цикл
        Else
        End If
Next i
 Pred_Max = max 'запоминание предыдущего максимального числа совпадений
 If max = 0 Then Exit Do ' - сформировалась строка из единиц, либо больше нечем заменять..
 ReDim Preserve NStroki(k)
 NStroki(k) = n

MsgBox "колво совпадений: " & max & "  Номер строки: " & n & "  Строка по счету - " & k
zamena = 0 'количество замен будет равно количеству максимальных перекрытий.....,
For i = 1 To UBound(massiv1, 1)
    If PoleSovpaden(1, i) = 0 And PoleSovpaden(n, i) = 1 Then
    PoleSovpaden(1, i) = 1 ' меняем НУЛИ на ЕДИНИЦЫ в ИСХОДНИКЕ, меняем ИСХОДНИК до тех пор пока он не будет весь из ЕДИНИЦ
    zamena = zamena + 1  ' достигнуто  (число max), то нет смысла дальше продолжать цикл
    End If
    If zamena = max Then Exit For
Next i
Loop

Заранее спасибо.
 
 
 
#2
11.10.2013 17:42:21
Это что, повтор темы?
Там только что выложил вариант.
 
 
 
#3
11.10.2013 18:04:57
Её закрыли а вопросы остались, это не повтор, это продолжение  :)  

з.ы.Слэн помог и выделил её в другю тему. Писали почти в одно время я не заметил создания его темы. Прошу оставить эту, вопрос для меня важный, хочу найти эффективный алгоритм решения задачи, пока только разговоры
Изменено: kugeod - 11.10.2013 18:11:15
 
 
 
#4
11.10.2013 18:10:03
Тему, ссылку на которую дал Михаил никто не закрывал. Вы бы хоть ради интереса по ссылке сходили, а не сходу отвечали.
Даже самый простой вопрос можно превратить в огромную проблему. Достаточно не уметь формулировать вопросы...
 
 
 
#5
11.10.2013 18:17:48
Михаил, матрицу свою я сократил, возможно это не лучший пример, т.к. я её обрезал, чтоб влезть в 100 кб, матрица у меня бывает занимает около 400мб памяти, и очень хочется понять, есть ли алгоритм более эффективный чем я выложил. Можно в принципе накатать по быстрому макрос, который бы делал эту матрицу из нулей и единиц...
 
 
 
#6
11.10.2013 18:27:08
вы мое решение смотрели? оно быстрее или медленнее вашего?

...для примера достаточно было 30-40 строк, 10-15 столбцов и ясного объяснения, что нужно получить и где показать результат..
 
 
 
#7
11.10.2013 18:29:27
Вторую тему наверно надо закрыть, выложу сюда
 
 
 
#8
11.10.2013 18:33:11
Я пока распутываю клубы тем. Закрыли мою, открыл Слэн, я ее увидел уже после вас...Я ваше решение пока смотрю, как только пойму что к чему, отпишусь
Михаил, на самом деле я пока ничего не понял :( Можете прокомментировать?
Изменено: kugeod - 11.10.2013 18:53:38
 
 
 
#9
11.10.2013 20:24:12
Я могу:
Цитата
Писали почти в одно время я не заметил создания его темы.
Смотрим: эта тема - 16:36, тема Слэна - 10:57. Почти одновременно.
Думаю, что в этой ситуации нужно ВООБЩЕ ВСЕ темы удалить и создать абсолютно новую.
 
 
 
#10
12.10.2013 07:01:06
Вариант преобразовать строку 1/0 в битовое представление типа Long. Соответственно, по алгоритму Слэна подсчитать и упорядочить по числу единиц в строке. Это позволит:
1. Воспользоваться бинарным поиском для вычисления начала возможных дополнений для элементов число единиц > число столбцов \ 2
2. Проверка на наличие совпадения хотя бы одной 1
testingItem.bitValue And FBitArray(k).bitValue = 0
2. получение битового дополнения
tesitngItem.bitValue Or FBitArray(k).bitValue
testingItem.bitCount = testingItem.bitCount + FBitArray(k).bitCount
3. Для нахождения возможного следущющего дополнения также можно воспользоваться бинарным поиском.
Скрытый текст

P. S. Естественно, сортировку вставками можно заменить на QuikSort
 
 
 
#11
12.10.2013 11:58:16
Код
   If curBit > 0 Then toBit.bitCount = toBit.bitCount + 1
        toBit.bitValue = toBit.bitValue + curBit * vMult


можно чуть ускорить:

       
Код
If curBit > 0 Then
   toBit.bitCount = toBit.bitCount + 1
           toBit.bitValue = toBit.bitValue + curBit * vMult
       endif


и
   toBit.bitCount = 0: toBit.bitCount = 0: toBit.idRow = idRow

должно быть

   toBit.bitValue = 0: toBit.bitCount = 0: toBit.idRow = idRow
Живи и дай жить..
 
 
 
#12
12.10.2013 12:07:43
да, и если количество стодбцов действительно  влазит в лонг, то это отличная идея
Живи и дай жить..
 
 
 
#13
12.10.2013 14:53:05
Слэн
Если смотреть тестовый пример, то достаточно двух строк для полной строки из единиц и тогда макрос Михаила самый оптимальный.
Цитата
да, и если количество стодбцов действительно влазит в лонг
По первому посту столбцов 50, но можно добавить второе поле в запись для увеличения разрядности (всё равно будет меньше операций чем над 50).
Для приближения к алгоритму Михаила, можно искать инвертированное значение от bitValue (для бинарного поиска во втором упорядоченном по bitValue массиве или Dictionary по bitValue/idRow).
(Not bitValue) And vMask
где vMask содержит число единиц по количеству столбцов.
 
 
 
#14
12.10.2013 15:18:11
Т.к. я пытаюсь понять смысл сказанного в десять раз дольше уважаемых гуру, я пока возьму паузу, но от темы не отказываюсь. Столбцов бывает максимум около 30000, соответственно как и строк. В большинстве случаев это квадратная матрица.
 
 
 
#15
12.10.2013 15:59:19
Цитата
Столбцов бывает максимум около 30000
30 тыс? не ошиблись? за раз мало какой компьютер это осилит. Да и по моему алгоритму, excel максимум 49 разрядов за раз обработать может, а это значит более 60 циклов только по одной строке.

за. ради интереса - какое практическое применение у такой задачи?
 
 
 
#16
12.10.2013 16:44:31
ваш алгоритм я к сожаоению не осилил..т.к. познания мои в VBA не велики, а комментов минимум
Нет не ошибся, моим алгоритмом 26000 делает минут за 45 (правда скомпилированным на VB в екзешник) Теории вероятностей, мысли моего товарища по работе в бумаге так сказать..
 
 
 
#17
12.10.2013 17:41:11
anvg
В силу своей тупости не понимаю работу алгоритма. И у меня на 31ом цикле i идет переполнение переменной vMult. То есть работать с большими матрицами никак?
Слэн
Объясните смысл считать колво единиц в строке? Потом добирать не получиться, т.к. строки могут содержать единицы в тех же столбцах, которые уже заполнены единицами.
Изменено: kugeod - 12.10.2013 17:43:56
 
 
 
#18
13.10.2013 16:57:07
Массив 30000Х30000 не поместится в памяти компа. Во всяком случае, в моем (2 гига) не помещается. Если у вас более мощный комп (8 гигов) и 64-разрядный офис - может и поместится. В противном случае такой массив в Excel не обработать.

Комментариев минимум потому, что я не уверен, правильно ли я понял задачу.

Зы. для проверки возможности вашего компа запустите такой макрос:
Код
Sub t()
Dim a(30000, 30000)
End Sub
если ошибки не будет - можно думать об алгоритме.
 
 
 
#19
14.10.2013 03:20:37
kugeod
Учитывая эту строку вашего кода
Цитата

Код
If PoleSovpaden(1, j) = 0 And PoleSovpaden(i, j) = 1 Then Perekritie = Perekritie + 1
Получается для строки
11110
дополнениями являются (с количеством единиц)
11101 (4)
11011 (4)
10111 (4)
01111 (4)
11001 (3) - и так далее для меньшего числа единиц.
По вашему же выложенному примеру находится несколько дополнений, просто посчитайте число 1 в строке и отсортируйте по убыванию, и посмотрите, что получается.
Цитата
Смысл собрать строку из одних единиц, взяв минимальное число строк из массива.
Достаточно двух строк (меньше быть не может, если, конечно же, у вас нет полностью единичной строки, но и это решабельно).
Следовательно как раз вариант Слэна с подсчётом количества единиц вкупе с последующей сортировкой QuickSort для вас наиболее подходящий:
1. Выбираем строку, к которой ищем дополнения, имеющую максимальное количество единиц,
2. число разделитель = (MaxCount1 + CurrentMinCount1) \ 2 на каждом этапе,
3. идти сначала нужно по правой (большей ветке)
4. На каждом этапе рекурсии Perekritie определяете на первом шаге со строками MaxCount1, на втором MaxCount1 - 1, на третьем MaxCount1 - 2 и так далее.
5.  Выход по Perekritie = Число столбцов - MaxCount1.
Если 5 не выполняется, то в любом случае запоминаем максимальное перекрытие на 4. и начинаем искать среди больших по числу единиц (см. пример выше).
Михаил, Слэн и я предполагали, что дополнением к 11110 является только 00001, так что можете над алгоритмом постом выше голову не ломать.
 
 
 
#20
14.10.2013 06:46:41
Я не совсем понял задачу
Является ли решением, если к строке 11110 мы добавим строку 01111, в данном случае соберется ли строка?

Если да, то можно использовать следующий алгоритм:
преобразуем каждую строку в число типа Long (если хватает разрядов), как уже предлагалось, (если не хватает, то в массив Long)
Задача сводится к решению "задачи о рюкзаке", где искомым числом будет число состоящее из одних единиц, а вместо суммирования необходимо использовать логическое или (Or), при этом нужно минимизировать кол-во "слагаемых".
Решение можно проводить перебором или динамикой, но учитывая очень большое количество исходных данных, не знаю как применить динамику.
Но если сходимость большая, нужный результат получается при "сложении" нескольких строк (по исходным данным это так), то перебором можно реализовать
 
 
 
#21
14.10.2013 16:10:26
Цитата
Я не совсем понял задачу
Является ли решением, если к строке 11110 мы добавим строку 01111, в данном случае соберется ли строка?
Да, конечно!
Почитал на Вики про задачу о ранце, впечатлён, даже не знал о существовании оной.
Изменено: kugeod - 14.10.2013 16:17:45
 
 
 
#22
14.10.2013 16:52:51
Ну вот и выяснилось, что я решал не ту задачу.  :D
 
 
 
Страницы: 1
Наверх