WedX - журнал о программировании и компьютерных науках

Как назначить N чисел в M пакет, который минимизирует некоторую целевую функцию?

У меня есть N (например, 30) целых чисел V[i] и M (например, 8) пакетов, каждый пакет имеет ожидаемое значение P[j].

Я хочу присвоить каждое целое число одному пакету, следующее выражение вычисляет разницу между суммой V[k] в пакете j и ожидаемым значением пакета j.

diff[j] = abs(P[j] - sum(V[k] that in pack j))

Цель состоит в том, чтобы найти лучшее решение, которое минимизирует sum(diff[j]).

Я не знаю, что это за проблема такого рода. Можно ли это решить с помощью линейного программирования или это NP-полная задача?

algorithm mathematical-optimization integer-programming np-complete
27.06.2014

  • Я сомневаюсь, что вы имели в виду именно это, но я должен указать, что линейное программирование и NP-Complete не приближаются к разделению проблемного пространства. 28.06.2014

Ответы:


1

Независимо от того, является ли это NP-трудным или нет, вы можете эффективно решить свою проблему для необходимых вам экземпляров проблемы, используя легкодоступное программное обеспечение для целочисленного программирования. Для вашей проблемы вы можете определить x_{ij}, чтобы определить, назначен ли X[i] группе j. Затем вы также должны определить переменные d_j, которые являются diff[j] в вашей формулировке. Тогда ваша модель:

min_{x, d} \sum_{j=1}^M d_j
s.t.       d_j >= P[j] - \sum_{i=1}^N X[i]x_{ij} \forall j
           d_j >= \sum_{i=1}^N X[i]x_{ij} - P[j] \forall j
           \sum_{j=1}^M x_ij = 1 \forall i
           x_{ij}\in \{0, 1\}

Это модель смешанной целочисленной оптимизации, которую можно решить, например, с помощью пакетов lpsolve или lpSolveAPI в R или функции intlinprog в MATLAB.

29.06.2014
  • GLPK тоже не так уж плох. 29.06.2014

    • 2

    Я могу доказать, что ваша проблема является NP, сведя другую NP-задачу к этой. Другими словами, я покажу, что, если я могу решить эту задачу, я могу немедленно решить другую задачу NP.

    Конкретная проблема, которую я буду сокращать, — это проблема с суммой подмножеств:

    Пусть V будет набором чисел. Мы хотим знать, если sum(V)==0. Пусть P={0} (массив длины один, содержащий только 0). В этой ситуации оптимальное решение вашей задачи имеет sum(diff[j])==0 тогда и только тогда, когда сумма подмножества равна 0. Другими словами, задача о сумме подмножеств — это частный случай вашей задачи, поэтому ваша задача не менее сложна, чем задача о сумме подмножеств.

    Следовательно, ваша проблема - НП. Я до сих пор не уверен, что это NP-Complete.

    28.06.2014
  • Мне нужно присвоить все номера одной пачке, если пачка только одна, то sum(diff[j]) это sum(V) - P[0]. 28.06.2014
  • Я не уверен, что вы пытаетесь сказать, но я добавил предложение, чтобы лучше объяснить свой ответ. 28.06.2014
  • У конкретной проблемы есть только один пакет? Например есть пять номеров [1,2,3,4,5] и одна пачка [12], выбор только один, другой 1+2+3+4+5 - 12 = 3. 28.06.2014

    • 3

    Это NP-сложно путем сокращения от 2-partition (2P). Измените текущую проблему на проблему решения, спрашивающую, если сумма (diff [j]) = 0. Учитывая экземпляр 2P, пусть P[0] = P[1] = sum(V)/2. Если существует разбиение на два раздела, то явно существует какое-то присваивание с sum(diff[j])=0.

    Существует псевдополитаймовый алгоритм для 2-разделов, но он вряд ли сработает для этой проблемы, поскольку не применяется к >=3-разделам.

    Похоже, что это аналогично упаковке в корзину, но я не уверен на 100%, потому что вы можете переполнить «пакет», но не «корзину».

    28.06.2014
    Новые материалы
    Объяснение документов 02: BERT
    BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..
    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..
    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..
    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..
    Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
    Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..
    Учебные заметки: создание моего первого пакета Node.js
    Это мои обучающие заметки, когда я научился создавать свой самый первый пакет Node.js, распространяемый через npm. Оглавление Глоссарий I. Новый пакет 1.1 советы по инициализации..
    Забудьте о Matplotlib: улучшите визуализацию данных с помощью умопомрачительных функций Seaborn!
    Примечание. Эта запись в блоге предполагает базовое знакомство с Python и концепциями анализа данных. Привет, энтузиасты данных! Добро пожаловать в мой блог, где я расскажу о невероятных..
    Для любых предложений по сайту: wedx@cp9.ru