Matlab: удаление избыточных «сдвинутых» записей матрицы - PullRequest
Новая
       14

Matlab: удаление избыточных «сдвинутых» записей матрицы

0 голосов
/ 11 декабря 2011

У меня есть проблема, которую мне нужно решить, но я не могу придумать ничего более простого и быстрого: быстрое решение. Это немного похоже на проблему с несколькими коммивояжерами.

Сначала у меня есть матрица с X строками и N столбцами, N является статической переменной моего алгоритма и X может варьироваться. Давайте предположим, что это выглядит (здесь N = 5): 

matrix = [1 2 4 3 5; 4 3 1 2 5; 1 2 4 3 5; ]
matrix =
 1     2     4     3     5
 4     3     1     2     5
 1     2     4     3     5

каждая строка рассматривается как «маршрут» и содержит все уникальные числа от 1 до N Каждый маршрут (= строка) будет разделен на частичные маршруты. Это означает, что у меня есть матрица точек останова, которая содержит X строк и M (M < N) столбцов. E.g.:

breakpoints = [2 3 4; 1 2 4; 1 3 4]
breakpoints =
 2     3     4
 1     2     4
 1     3     4

Индексы каждой строки breakpoints дают элементы соответствующей строки matrix ПОСЛЕ того, какой маршрут будет разбит на частичные маршруты. Просто чтобы прояснить ситуацию, давайте рассмотрим первый ряд в качестве примера: breakpoints(1, :) = 2 3 4, что означает, что маршрут matrix(1, :) = 1 2 4 3 5 будет разбит на частичные маршруты [1 2], [4], [3] and [5]. Во втором ряду есть точки останова breakpoints(2, :) = 1 2 4, которые разбивают второй маршрут matrix(2, :) = 4 3 1 2 5 на частичные маршруты [4], [3], [1 2] and [5].

Теперь моя цель - удалить все строки из matrix, тогда как частичные маршруты являются избыточными дубликатами, только в другом порядке. В этом примере строка 2 является дубликатом строки 1. Строка 3 НЕ является дубликатом, даже если она имеет тот же маршрут, что и строка 1, поскольку существуют разные точки останова, которые ведут к частичным маршрутам [1], [2 4], [3] and [5].

Как я мог сделать это чисто и быстро? Матрица может содержать много элементов, таких как X = 5e4 строки и N = 10, M = 6.

1 Ответ

1 голос
/ 11 декабря 2011

Для константы M, N это можно решить за время O (X log X), отсортировав составные записи по порядку, а затем проверив на равенство смежных записей.

Под «составной записью» я подразумеваю запись, которая объединяет функцию строки и ее точек останова в одну запись. Функция получается для данной строки следующим образом:

  1. Применение точек останова к строке, получение списка частичных маршрутов.
  2. Сортировка частичных маршрутов в порядке возрастания по первому элементу каждого маршрута. Например, sort {[4], [3], [1 2], [5]} как {[1 2], [3], [4], [5]}.
  3. Формирование новой составной записи путем объединения отсортированных-частичных маршрутов; эффективные точки останов; и строка индекса к источнику. Например, , если примером строки на предыдущем шаге является строка 2 = (4 3 1 2 5), сохранить (1 2 3 4 5; 2 3 4; 2), то есть (отсортированные частичные маршруты; эффективные контрольные точки; индекс).

После сортировки составных записей, просматривайте их в поисках равенства смежных записей, вплоть до исходного индекса. Например, (1 2 3 4 5; 2 3 4; 2) и (1 2 3 4 5; 2 3 4; 7) указывают, что частичные маршруты из строки 7 дублируют маршруты из строки 2. Каждый раз, когда обнаруживается дубликат, установите для соответствующей исходной записи первой строки недопустимый номер точки, скажем, N + 1.

Таким образом, после сортировки, которая стоит O (X log X), используйте O (X) время для обнаружения дубликатов. Затем используйте время O (X), чтобы выжать дубликаты, просматривая исходные строки, отбрасывая те, у которых недопустимый первый элемент.

Несколько более точная общая стоимость равна O ((M + N) * X * log X), что превышает теоретический минимум O ((M + N) * X) на коэффициент log X. Вы можете избавиться от X-фактора журнала, если вы сохраните составные записи в хеш-таблице вместо их сортировки и пометите записи для удаления при появлении дублированных хеш-записей.

...