Добрый вечер! На работе возникла следующая задача: имеется набор тиглей и крышек с разными массами. Для выполнения анализа необходимо из этих наборов найти 2 пары "тигель-крышка", такие что суммарная масса пар отличается не более чем на величину допуска (скажем 0,2 мг). Точнее для более эффективной работы требуется найти максимальное количество таких пар, которое можно образовать из предоставленного набора тиглей и крышек. Как я попытался решить задачу: 1. складываю массы тигля и крышки для всех сочетаний "тигель-крышка" 2. формирую массив с данными о номерах тигля и крышки, их массах и суммарной массе 3. пробегаюсь по массиву и сравниваю разницу между суммарными массами "тигель-крышка" с допуском, при этом ввожу условие, что в найденных парах должны быть разные тигли и крышки 4. получаю итоговый массив из всех возможных комбинаций. Но остается проблема выбора максимального числа строк из этого массива, таких, что они не содержат одинаковых номеров тиглей и крышек. Попытался решить данную проблему путем рекурсивной функции, но Excel зависает по причине переполнения стека - либо не хватает памяти либо я что-то коряво написал (VBA только начал изучать, сам я не программист). Помогите, пожалуйста, решить данную проблему или предложите другой метод решения.
Добрый вечер! На работе возникла следующая задача: имеется набор тиглей и крышек с разными массами. Для выполнения анализа необходимо из этих наборов найти 2 пары "тигель-крышка", такие что суммарная масса пар отличается не более чем на величину допуска (скажем 0,2 мг). Точнее для более эффективной работы требуется найти максимальное количество таких пар, которое можно образовать из предоставленного набора тиглей и крышек. Как я попытался решить задачу: 1. складываю массы тигля и крышки для всех сочетаний "тигель-крышка" 2. формирую массив с данными о номерах тигля и крышки, их массах и суммарной массе 3. пробегаюсь по массиву и сравниваю разницу между суммарными массами "тигель-крышка" с допуском, при этом ввожу условие, что в найденных парах должны быть разные тигли и крышки 4. получаю итоговый массив из всех возможных комбинаций. Но остается проблема выбора максимального числа строк из этого массива, таких, что они не содержат одинаковых номеров тиглей и крышек. Попытался решить данную проблему путем рекурсивной функции, но Excel зависает по причине переполнения стека - либо не хватает памяти либо я что-то коряво написал (VBA только начал изучать, сам я не программист). Помогите, пожалуйста, решить данную проблему или предложите другой метод решения.Rakhot
Можно, например, так, как в примере. Там, по идее, именно ваш алгоритм (п. 1-3 (берем полный набор пар, сортируем по массе, проверяем каждую массу, сравнивая со всеми соседними массами в дельта-окрестности, пишем нужные наборы в результат)), только в массив-результат сразу пишутся именно разные наборы пар (вернее, их номера-ссылки), причем сразу же исключается дублирование наборов (н1~=н2 <=> н2~=н1). Ну и затем ещё дополнительно выполняется сортировка результата уже по номерам самих вещей... Также, можно было бы в результат aR() писать не ссылки на номера в aM(), а сами наборы пар, - но так сделано в целях экономии ресурсов
Можно, например, так, как в примере. Там, по идее, именно ваш алгоритм (п. 1-3 (берем полный набор пар, сортируем по массе, проверяем каждую массу, сравнивая со всеми соседними массами в дельта-окрестности, пишем нужные наборы в результат)), только в массив-результат сразу пишутся именно разные наборы пар (вернее, их номера-ссылки), причем сразу же исключается дублирование наборов (н1~=н2 <=> н2~=н1). Ну и затем ещё дополнительно выполняется сортировка результата уже по номерам самих вещей... Также, можно было бы в результат aR() писать не ссылки на номера в aM(), а сами наборы пар, - но так сделано в целях экономии ресурсов AndreTM
Спасибо за алгоритм, он компактнее моего, но функционал один и тот же - у меня также стоит исключение дублей крышек и тиглей в наборе. Изменение допуска на дельту (расчет плюс-дельты) в вашем алгоритме действительно полезно, я об этом и не задумывался, исправлю у себя. Но основной вопрос - как из полученного набора всех возможных пар выбрать максимальное количество, такое, что в этом оставшемся наборе каждый из тиглей и крышек будет встречаться не более одного раза. Может я не совсем понятно объясняю, я имею в виду следующее: и ваш и мой код производят некий набор всех подходящих пар. Берем, к примеру, первую пару (1тигель+1крышка и 2тигель+5крышка). Затем мы должны удалить из набора все пары, в которых встречаются 1 и/или 2 тигель и 1 и/или 5 крышка. Затем из оставшегося набора фиксируем опять какую-нибудь пару и удаляем все пары, содержащие тигли и крышки выбранной нами пары. И так до тех пор, пока в оставшемся наборе каждый из тиглей и крышек будет встречаться не более одного раза. Если на каждом этапе проверки набора фиксировать, например, первую пару, не факт, что найденное количество пар будет максимально возможным. Надо видимо как-то либо проверить все возможные варианты либо искать другой путь. В этом, собственно, мое затруднение, не знаю, как даже и подступиться к ней.
Спасибо за алгоритм, он компактнее моего, но функционал один и тот же - у меня также стоит исключение дублей крышек и тиглей в наборе. Изменение допуска на дельту (расчет плюс-дельты) в вашем алгоритме действительно полезно, я об этом и не задумывался, исправлю у себя. Но основной вопрос - как из полученного набора всех возможных пар выбрать максимальное количество, такое, что в этом оставшемся наборе каждый из тиглей и крышек будет встречаться не более одного раза. Может я не совсем понятно объясняю, я имею в виду следующее: и ваш и мой код производят некий набор всех подходящих пар. Берем, к примеру, первую пару (1тигель+1крышка и 2тигель+5крышка). Затем мы должны удалить из набора все пары, в которых встречаются 1 и/или 2 тигель и 1 и/или 5 крышка. Затем из оставшегося набора фиксируем опять какую-нибудь пару и удаляем все пары, содержащие тигли и крышки выбранной нами пары. И так до тех пор, пока в оставшемся наборе каждый из тиглей и крышек будет встречаться не более одного раза. Если на каждом этапе проверки набора фиксировать, например, первую пару, не факт, что найденное количество пар будет максимально возможным. Надо видимо как-то либо проверить все возможные варианты либо искать другой путь. В этом, собственно, мое затруднение, не знаю, как даже и подступиться к ней.Rakhot
Нет, не то. В файле пометил красным те пары, которые из набора надо удалить на первом этапе, т.к. они содержат тигли и крышки из первого найденного набора (первой строки). Желтым - те пары, ктотрые надо удалить на 2 этапе, т.к. они содержат тигли и крышки из второго найденного набора (из тех элементов, которые остались не помеченными красным). Причем это весьма условно, что мы отбираем изначально первую пару, возможно в каких-то случаях (при других количествах тиглей и крышек) таким путем не получим максимальное количество пар. Возникла некоторая путаница - под "парой" подразумевался набор "пара№1"+"пара№2" (в терминах моего файла), я неверно выбрал название.
Нет, не то. В файле пометил красным те пары, которые из набора надо удалить на первом этапе, т.к. они содержат тигли и крышки из первого найденного набора (первой строки). Желтым - те пары, ктотрые надо удалить на 2 этапе, т.к. они содержат тигли и крышки из второго найденного набора (из тех элементов, которые остались не помеченными красным). Причем это весьма условно, что мы отбираем изначально первую пару, возможно в каких-то случаях (при других количествах тиглей и крышек) таким путем не получим максимальное количество пар. Возникла некоторая путаница - под "парой" подразумевался набор "пара№1"+"пара№2" (в терминах моего файла), я неверно выбрал название.Rakhot
А, теперь понял, что вы пытались донести до нас в п.4 Счас подумаем над математикой...
Дополнено... Пример прилагаю. Привираю немного в алгоритме, конечно, - на нетипичных наборах данных может начать глючить. По идее, правильнее было бы второй этап анализа сделать рекурсией - но я снова пожалел ресурсы
По ходу возник вопрос - надо найти хотя бы одно решение (максимальный набор пар), или же все возможные решения?
А, теперь понял, что вы пытались донести до нас в п.4 Счас подумаем над математикой...
Дополнено... Пример прилагаю. Привираю немного в алгоритме, конечно, - на нетипичных наборах данных может начать глючить. По идее, правильнее было бы второй этап анализа сделать рекурсией - но я снова пожалел ресурсы
По ходу возник вопрос - надо найти хотя бы одно решение (максимальный набор пар), или же все возможные решения?AndreTM
Вот и я попробовал сделать рекурсией - не хватило системных ресурсов Необходимо найти хотя бы одно решение - максимально большой набор пар. Проверил - все работает! На работе проверю на другом наборе тиглей и крышек, большего количества. Спасибо огромное за помощь, теперь буду медитировать над кодом, чтобы осознать, как и что он делает
Вот и я попробовал сделать рекурсией - не хватило системных ресурсов Необходимо найти хотя бы одно решение - максимально большой набор пар. Проверил - все работает! На работе проверю на другом наборе тиглей и крышек, большего количества. Спасибо огромное за помощь, теперь буду медитировать над кодом, чтобы осознать, как и что он делает Rakhot
Сообщение отредактировал Rakhot - Пятница, 10.10.2014, 09:39
буду медитировать над кодом, чтобы осознать, как и что он делает
Во второй части анализа тоже ничего особо сложного
Вот смотрите, мы имеем: - список тиглей T (10шт.), - список крышек K (6 шт.), - список всех возможных пар T+K (T*K=60 шт.) - это массив aM(), он, кстати, для контроля нарисован в столбцах Q:S (в столбце P - индекс массива для данной пары), - список возможных решений - наборов пар Ti+Kj<->Tm+Kn, это массив aR(), каждая строка массива хранится в виде (индекстнабора1,индекснабора2,отметка), где индекснабора* - это индекс соответствующей пары N+K в массиве aM(). По идее, можно было бы в решении хранить не два индекснабора, а четыре индекса тиглей-крышек - это непринципиально для алгоритма.
Заметим, что для каждой строки aR(), по алгоритму из решения первой части, Ti<>Tm,Ki<>Km, т.е. это пара из двух различных тиглей и двух различных крышек. Также, решение второй части - максимальное количество наборов (T1+K1,T2+K2) - целое число, не превосходящее INT(MIN(T,K)/2) - в нашем конкретном случае MaxRes = int(min(10,6)/2)) = 3. Их может быть меньше, но больше - никак. Представьте себе, что решение aR() - это граф. Каждая пара T+K - это точка, каждая строка решения aR() - это отрезок, соединяющий две соответствующие точки. Будем искать решение таким образом - нам надо попытаться найти MaxRes независимых (не имеющих одинаковых концов) отрезков этого графа. Что означает - при поиске решения, если мы фиксируем какой-то из отрезков как часть решения - то нам сразу требуется исключить все отрезки, имеющие с зафиксированным общие концы. А затем дейстовать таким же образом далее - выбрать какой-то из оставшихся "свободных" отрезков, зафиксировать, исключить связанные отрезки. Если достигнем MaxRes в количестве зафиксированных отрезков - найдено хотя бы одно решение, выходим; если свободные отрезки кончатся раньше - вернемся в самое начало и будем пытаться искать другое решение, фиксируя в качестве начального другой отрезок. До тех пор, пока не переберем все имеющиеся отрезки в качестве начального. Обратите внимание на выделенное - здесь как раз и кроется отличие от рекурсивного подхода (где мы бы вернулись только на шаг назад для выбора другого отрезка), здесь же и есть небольшая проблема - кажется, что алгоритм может не найти максимальное решение.
Впрочем, посмотрите исправленный пример, - я немного переделал алгоритм, теперь он изображает из себя псевдорекурсию. Заодно заведен параллельный массив, куда сбрасывается последнее найденное решение, для того, чтобы можно было восстановить хотя бы неполное решение задачи... Но все это надо тестировать.
буду медитировать над кодом, чтобы осознать, как и что он делает
Во второй части анализа тоже ничего особо сложного
Вот смотрите, мы имеем: - список тиглей T (10шт.), - список крышек K (6 шт.), - список всех возможных пар T+K (T*K=60 шт.) - это массив aM(), он, кстати, для контроля нарисован в столбцах Q:S (в столбце P - индекс массива для данной пары), - список возможных решений - наборов пар Ti+Kj<->Tm+Kn, это массив aR(), каждая строка массива хранится в виде (индекстнабора1,индекснабора2,отметка), где индекснабора* - это индекс соответствующей пары N+K в массиве aM(). По идее, можно было бы в решении хранить не два индекснабора, а четыре индекса тиглей-крышек - это непринципиально для алгоритма.
Заметим, что для каждой строки aR(), по алгоритму из решения первой части, Ti<>Tm,Ki<>Km, т.е. это пара из двух различных тиглей и двух различных крышек. Также, решение второй части - максимальное количество наборов (T1+K1,T2+K2) - целое число, не превосходящее INT(MIN(T,K)/2) - в нашем конкретном случае MaxRes = int(min(10,6)/2)) = 3. Их может быть меньше, но больше - никак. Представьте себе, что решение aR() - это граф. Каждая пара T+K - это точка, каждая строка решения aR() - это отрезок, соединяющий две соответствующие точки. Будем искать решение таким образом - нам надо попытаться найти MaxRes независимых (не имеющих одинаковых концов) отрезков этого графа. Что означает - при поиске решения, если мы фиксируем какой-то из отрезков как часть решения - то нам сразу требуется исключить все отрезки, имеющие с зафиксированным общие концы. А затем дейстовать таким же образом далее - выбрать какой-то из оставшихся "свободных" отрезков, зафиксировать, исключить связанные отрезки. Если достигнем MaxRes в количестве зафиксированных отрезков - найдено хотя бы одно решение, выходим; если свободные отрезки кончатся раньше - вернемся в самое начало и будем пытаться искать другое решение, фиксируя в качестве начального другой отрезок. До тех пор, пока не переберем все имеющиеся отрезки в качестве начального. Обратите внимание на выделенное - здесь как раз и кроется отличие от рекурсивного подхода (где мы бы вернулись только на шаг назад для выбора другого отрезка), здесь же и есть небольшая проблема - кажется, что алгоритм может не найти максимальное решение.
Впрочем, посмотрите исправленный пример, - я немного переделал алгоритм, теперь он изображает из себя псевдорекурсию. Заодно заведен параллельный массив, куда сбрасывается последнее найденное решение, для того, чтобы можно было восстановить хотя бы неполное решение задачи... Но все это надо тестировать.
Спасибо за пояснения, логика понятна, сижу разбираю синтаксис, ибо я пока что в VBA чайник - только начал изучать, когда решил как-то упростить себе и коллегам жизнь на работе
Спасибо за пояснения, логика понятна, сижу разбираю синтаксис, ибо я пока что в VBA чайник - только начал изучать, когда решил как-то упростить себе и коллегам жизнь на работе Rakhot
Да, примерно то. Только у вас отмечен один набор, соответствующий критерию "разность масс не более дельта", а конечная цель - найти максимальное количество таких наборов, чтобы в них каждый тигель и крышка появлялись не более 1 раза. Т.е. для данного случая с 5 крышками таких наборов максимум 2.
Да, примерно то. Только у вас отмечен один набор, соответствующий критерию "разность масс не более дельта", а конечная цель - найти максимальное количество таких наборов, чтобы в них каждый тигель и крышка появлялись не более 1 раза. Т.е. для данного случая с 5 крышками таких наборов максимум 2.Rakhot