Поиск  Пользователи  Правила 
Закрыть
Логин:
Пароль:
Забыли свой пароль?
Регистрация
Войти
 
Страницы: 1
RSS
Есть двумерный массив из нулей и единиц., Найти минимальное количество строк, которые бы образовали строку только из единиц.
 
сравниваю первую строку со всеми строками.
Но скорее это не правильно, т.к. нужно найти минимально количество строк удовлетворяющих условию.
Смысл собрать строку из одних единиц, взяв минимальное число строк из массива.

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

Код
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

Заранее спасибо.
 
Это что, повтор темы?
Там только что выложил вариант.
 
Её закрыли а вопросы остались, это не повтор, это продолжение  :)  

з.ы.Слэн помог и выделил её в другю тему. Писали почти в одно время я не заметил создания его темы. Прошу оставить эту, вопрос для меня важный, хочу найти эффективный алгоритм решения задачи, пока только разговоры
Изменено: kugeod - 11 Окт 2013 18:11:15
 
Тему, ссылку на которую дал Михаил никто не закрывал. Вы бы хоть ради интереса по ссылке сходили, а не сходу отвечали.
Даже самый простой вопрос можно превратить в огромную проблему. Достаточно не уметь формулировать вопросы...
 
Михаил, матрицу свою я сократил, возможно это не лучший пример, т.к. я её обрезал, чтоб влезть в 100 кб, матрица у меня бывает занимает около 400мб памяти, и очень хочется понять, есть ли алгоритм более эффективный чем я выложил. Можно в принципе накатать по быстрому макрос, который бы делал эту матрицу из нулей и единиц...
 
вы мое решение смотрели? оно быстрее или медленнее вашего?

...для примера достаточно было 30-40 строк, 10-15 столбцов и ясного объяснения, что нужно получить и где показать результат..
 
Вторую тему наверно надо закрыть, выложу сюда
 
Я пока распутываю клубы тем. Закрыли мою, открыл Слэн, я ее увидел уже после вас...Я ваше решение пока смотрю, как только пойму что к чему, отпишусь
Михаил, на самом деле я пока ничего не понял :( Можете прокомментировать?
Изменено: kugeod - 11 Окт 2013 18:53:38
 
Я могу:
Цитата
Писали почти в одно время я не заметил создания его темы.
Смотрим: эта тема - 16:36, тема Слэна - 10:57. Почти одновременно.
Думаю, что в этой ситуации нужно ВООБЩЕ ВСЕ темы удалить и создать абсолютно новую.
 
Вариант преобразовать строку 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
 
Код
   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
Живи и дай жить..
 
да, и если количество стодбцов действительно  влазит в лонг, то это отличная идея
Живи и дай жить..
 
Слэн
Если смотреть тестовый пример, то достаточно двух строк для полной строки из единиц и тогда макрос Михаила самый оптимальный.
Цитата
да, и если количество стодбцов действительно влазит в лонг
По первому посту столбцов 50, но можно добавить второе поле в запись для увеличения разрядности (всё равно будет меньше операций чем над 50).
Для приближения к алгоритму Михаила, можно искать инвертированное значение от bitValue (для бинарного поиска во втором упорядоченном по bitValue массиве или Dictionary по bitValue/idRow).
(Not bitValue) And vMask
где vMask содержит число единиц по количеству столбцов.
 
Т.к. я пытаюсь понять смысл сказанного в десять раз дольше уважаемых гуру, я пока возьму паузу, но от темы не отказываюсь. Столбцов бывает максимум около 30000, соответственно как и строк. В большинстве случаев это квадратная матрица.
 
Цитата
Столбцов бывает максимум около 30000
30 тыс? не ошиблись? за раз мало какой компьютер это осилит. Да и по моему алгоритму, excel максимум 49 разрядов за раз обработать может, а это значит более 60 циклов только по одной строке.

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

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

Зы. для проверки возможности вашего компа запустите такой макрос:
Код
Sub t()
Dim a(30000, 30000)
End Sub
если ошибки не будет - можно думать об алгоритме.
 
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, так что можете над алгоритмом постом выше голову не ломать.
 
Я не совсем понял задачу
Является ли решением, если к строке 11110 мы добавим строку 01111, в данном случае соберется ли строка?

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