Найдите подпоследовательность размера k такую, что минимальное расстояние между значениями максимально

Предположим, у меня есть случайная последовательность (упорядоченный массив), которая содержит n положительное число с плавающей запятой. Как найти подпоследовательность размера k так, чтобы минимальное расстояние между всеми парами поплавков в подпоследовательности было максимальным, я имею в виду, что они находятся на самом дальнем расстоянии.

Примечание. Подпоследовательность последовательности – это упорядоченное подмножество элементов последовательности, имеющих тот же порядок следования, что и исходная последовательность.

ОГРАНИЧЕНИЯ

  1. n>10^5
  2. n>k>2

пример :

последовательность a[]={1.1,2.34,6.71,7.01,10.71} и k=3 , подпоследовательность = {1.1,6.71,10.71} , минимальное расстояние равно 4 между 10.71 и 6.71 .

Неверная подпоследовательность :

{1.1,7.01,10.71}, минимальное расстояние 3,7

{1.1,2.34,6.71}, минимальное расстояние 1,24

Я придумал решение:

1) сортировать массив

2) выберите a[0] , теперь найдите ceil(a[0]+ x) = Y в массиве .... а затем ceil(Y+ x) и так далее k-1 раз, также kth элемент будет a[n -1]

Чтобы найти х:

dp[i,j] будет x для выбора j элементов из первых i элементов.

Наконец, нам нужно dp[n][k], что равно x

Но я столкнулся с проблемой поиска x и переупорядочения индексов.

dp[i,j] = max(min( dp[k,j-1], dp[i]-A[k]))

от k=1 до i-1, от i=2 до n, от j=2 до i

dp[i][1] = 0 от i = 1 до n

Я хочу исправить решение динамического программирования, хотя я знаю, что x можно найти с помощью двоичного поиска по x , но при сортировке я теряю порядок последовательности и отнимаю много времени (O (n^2)). Как решить эту проблему?


optimization algorithm approximation dynamic-programming np-hard
person Iraj Shokouhi Bahar    schedule 26.05.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Если есть решение, включающее сортировку, вы сначала хотите сопоставить массив с массивом кортежей, которые содержат значение и позицию элемента. Теперь, когда вы сортируете массив, вы также знаете исходные позиции.

Однако я не верю, что сортировка действительно поможет вам в конце.

Подход, который я вижу, который работает, заключается в том, чтобы для каждого 0 <= i < n, для каждого 1 < j <= min(k, i+1) сохранять минимальное расстояние и предыдущую запись для лучшей подпоследовательности длины j, заканчивающейся на i.

Затем вы ищете наилучшую подпоследовательность длины k. А затем расшифровать подпоследовательность.

Используя нотацию JSON (для ясности, а не потому, что это правильная структура данных) и ваш пример, вы можете получить такую ​​структуру данных:

[
    {"index": 0, "value": 1.1},
    {"index": 1, "value": 2.34,
        "seq": {2: {"dist": 1.34, "prev": 0}},
    {"index": 2, "value": 6.71,
        "seq": {2: {"dist": 5.61, "prev": 0},
                3: {"dist": 1.34, "prev": 1}},
    {"index": 3, "value": 7.01,
        "seq": {2: {"dist": 5.91, "prev": 0},
                3: {"dist": 1.34, "prev": 1}},
    {"index": 4, "value": 10.71,
        "seq": {2: {"dist": 9.61, "prev": 0},
                3: {"dist": 4, "prev": 2}}
]

И теперь мы обнаруживаем, что самое большое dist для длины 3 равно 3.7 по индексу 4. Идя назад, нам нужны индексы 4, 2 и 0. Вытащите их и переверните, чтобы получить решение [1.1, 6.71, 10.71].

person btilly    schedule 26.05.2020
comment
ОК... это хорошее предложение.... но оно отнимает много времени... Мне бы хотелось жадный алгоритм ранга O(n) - person Iraj Shokouhi Bahar; 26.05.2020
comment
Это решение O(k n^2). Приложив много усилий, можно сократить это число до O(k n log(n)). Но я бы рекомендовал не пытаться оптимизировать его до тех пор, пока у вас не будет рабочего решения. - person btilly; 26.05.2020
comment
@IrajShokouhiBahar Убедитесь, что вы действительно видели комментарий. Для протокола: я начал пытаться объяснить, как это ускорить, но быстро обнаружил, что это сложно объяснить. Кодировать будет еще сложнее. Я рекомендую против этого. - person btilly; 26.05.2020
comment
Хорошо... что посоветуете? - person Iraj Shokouhi Bahar; 26.05.2020
comment
@IrajShokouhiBahar Попробуйте найти решение, работающее в соответствии с тем, что я описал. Очевидно, использование более C-подобных структур данных (например, массивов структур), а не JSON. - person btilly; 27.05.2020