Найти оптимальный порядок

9

Я столкнулся с этой проблемой и изо всех сил пытаюсь найти способ приблизиться к ней. Любые мысли будут с благодарностью!

Предположим, нам дана матрица {1,0,1}n × k , например,

[1010110001011011101110001]

Не пробуя каждую перестановку, найдите порядок столбцов ci который максимизирует количество строк, для которых первый ненулевой элемент равен 1 .

Для приведенного выше примера один такой порядок (он не уникален!) Является (c3,c4,c1,c2,c5) , т.е.

[1010100101100110111100101]

Здесь для 4 из 5 строк первый ненулевой элемент равен 1 .

haijo
источник
Какие алгоритмические подходы вы пробовали? Где вы столкнулись с этой проблемой? Можете ли вы указать источник? Можете ли вы поделиться что-нибудь о контексте или мотивации? Вы можете найти эту страницу полезной для улучшения вашего вопроса.
DW
1
Я хочу предложить шаг предварительной обработки: пусть полуположительный столбец (соответственно строка) будет столбцом (соответственно строка) только с 0 и 1. Предлагается удалить все полуположительные столбцы, а также строки с 1 в полуположительном столбце. В вашем примере это удалит строки 1, 3 и 4. Теперь у вас останутся строки и столбцы, которые содержат -1. Может не помочь, но это может быть проще рассуждать.
Пол Г.Д.
Можем ли мы предположить, что количество строк намного меньше, чем количество столбцов? Это может облегчить проблему.
Анжела Преториус
1
@ Пол, подобная предварительная обработка возможна со строками и столбцами, которые не содержат 1. Тем не менее, я не думаю, что так легче рассуждать: просто меньше.
Питер Тейлор
1
FWIW это кросс-пост . haijo, если вы не получили ответ по одному стеку и думаете, что другой может быть лучше, вы можете пометить его и запросить миграцию. Кросс-постинг не очень хороший этикет, потому что ответчики не знают ответов, которые вы могли получить на другом сайте, и могут тратить свое время на их повторение.
Питер Тейлор

Ответы:

4

Эта проблема, которую я буду называть CO для упорядочивания столбцов, является NP-сложной . Вот сокращение от NP-трудной проблемы Vertex Cover (VC) к нему:

Решение проблемных форм ВК и СО

Пусть входной экземпляр VC будет (V,E,k) . Он представляет собой вопрос: «Учитывая граф (V,E) , можно ли выбрать набор из не более чем k вершин из V , чтобы каждое ребро в E падало хотя бы на одну выбранную вершину?» Мы построим экземпляр (A,k) CO, который представляет вопрос: «Учитывая матрицу A с элементами в {1,0,1}, возможно ли переставить столбцы A , чтобы 1 появлялся перед -1 по крайней мере на k строках? "Эти две проблемы изложены в форме решения проблемы , при этом ответом на каждый является либо ДА, либо НЕТ: формально говоря , именно эта форма проблемы является NP-полной (или нет). Нетрудно понять, что более естественная проблема оптимизации форма изложенная в вопросе OP, примерно эквивалентна с точки зрения сложности: бинарный поиск на пороге Параметр может быть использован для решения задачи оптимизации с использованием решателя задачи решения, в то время как для решения проблемы решения достаточно одного вызова решателя задачи оптимизации, а затем одного сравнения.

Построение экземпляра CO из экземпляра VC

Пусть n=|V|и m=|E|, Мы построим матрицу A с (n+1)m+n строками и n+1 столбцами. Верхние (n+1)m строк будут состоять из m блоков по n+1 строк в каждом, причем каждый блок представляет ребро, которое необходимо покрыть . Нижний n строки содержат "флаги" вершин, которые приведут к тому, что столбец (соответствующий вершине) будет нести фиксированную стоимость, если он будет включен в левую часть решения CO (что соответствует вершине, включенной в покрытие вершин ВК решение).

Для каждой вершины vi создайте столбец, в котором:

  • среди верхних (n+1)m строк j блок из n+1 строк содержит +1, когда ребро ej падает на vi , и 0 в противном случае, и
  • все нижние n строк равны 0, за исключением i , который равен -1.

Создайте еще один столбец «забор», который состоит из (n+1)m копий -1, а затем n копий +1.

И, наконец, установить порог k для построенного экземпляра СО: (n+1)m+nk . Другими словами, мы допускаем не более k строк, в которых -1 стоит перед +1. Давайте назовем это число нарушающих рядов «стоимостью» решения СО.

доказательство

Соответствие между решением экземпляра CO и набором вершин в исходном экземпляре VC: каждый столбец слева от ограждения соответствует вершине в наборе, а каждый столбец справа от ограждения соответствует вершина, которой нет.

n

kk

kk

k(n+1)m(n+1)uvAn+1n+1kn<n+1 : противоречие.

m(n+1)m(n+1)mnkkk

Наконец, ясно, что экземпляр CO может быть построен за полиномиальное время из экземпляра VC, что означает, что если бы существовал алгоритм полиномиального времени для решения CO, любой экземпляр VC также мог бы быть решен за полиномиальное время, сначала создав экземпляр CO, как описано выше, а затем решить его. Так как VC NP-жесткий, CO тоже.

j_random_hacker
источник
Всякий раз, когда есть такой хороший ответ, я задаюсь вопросом, следует ли заменить «Горячие сетевые вопросы» на что-то вроде «Ценные сетевые ответы».
Джон Л.
Не могли бы вы пролить свет на то, как вы найдете ответ? Это должно быть даже более поучительным, чем сам ответ.
Джон Л.
1
@ Apass.Jack: Спасибо! :) У меня нет особой стратегии, и я могу долго бродить в неправильном направлении. Например, здесь я потратил много времени на размышления о том, что могу сократить цикл Гамильтона (который аналогичен порядку элементов), прежде чем понять, что моя конструкция допускает конфигурации, соответствующие субтурам, и, следовательно, не будет работать. Как правило, я всегда пробую сокращение от Vertex Cover или Partition, затем, возможно, Clique. «Ценные сетевые ответы» звучат как отличная идея :)
j_random_hacker
1
rkr
1
n+1
2

S

function simplification:
while(true)
    if any row i$ has no 1 or no -1 left, remove it
    if any column j has no -1 then,
       remove it and put j on the leftmost available position in S,
       remove all rows where column j has 1.
    if any column j has no 1 then, 
       remove it and put j on the rightmost available position in S.
    if no modification has been done on this loop, break

Затем вы должны выполнить полное исследование комбинаторики, используя итеративный выбор функции:

function pick(k):
    put column k on the leftmost available position in S
    remove any row where column k is -1 or 1

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

На приведенном примере первое упрощение дает (как пояснил в комментарии Пол Г.Д.)

  • S[0]=c3
  • S[1]=c4
  • S[2]=c2
    [1111]

Я думаю, что матрица, делающая этот метод довольно неэффективным, будет иметь ровно один 1 и один -1 на строку / столбец, что-то вроде

[110000110000001100001100000011000011]

Тем не менее, упрощение все еще экономит около половины этапов разведки. И этот тип матрицы может быть разбит на несколько независимых субматриц.

Optidad
источник
1
@ Apass.Jack Я отредактировал, чтобы быть более точным. Да, я имел в виду положение столбца в выходной последовательности.
Optidad
Голосование как этап упрощения может быть достаточно для практических целей (таких как онлайн-программирование?).
Джон Л.
Спасибо, на самом деле мне было интересно оценить амортизированную стоимость времени, но я не знаю, как это сделать. Это возможно ? Или это сильно зависит от проблемы?
Optidad
2
ijijjij
1
Другое правило доминирования: всякий раз, когда у вас есть два столбца, иijijijijikk