Алгоритм поиска подходящих пар в списке

Question

Я сформулирую проблему в точной форме, которую я хочу ниже:

С учетом : Два списка с плавающей запятой N и D одинаковой длины k (k кратно 2). Известно, что для всех i=0,...,k-1 существует j != i такое, что D[j]*D[i] == N[i]*N[j]. (Я использую индексацию с нуля)

Возвращение : (Длина k/2) список пар (i,j) такой, что D[j]*D[i] == N[i]*N[j]. Возвращаемые пары могут быть не уникальными (допустим любой допустимый список пар)

Применение этого алгоритма заключается в нахождении обратных пар собственных значений обобщенной задачи о собственных значениях палиндромов. Условие равенства эквивалентно N[i]/D[i] == D[j]/N[j], но также работает, когда знаменатели равны нулю (что является определенной возможностью). Вырождения в задаче на собственные значения приводят к тому, что пары не являются уникальными.

В более общем смысле алгоритм эквивалентен:

С учетом : Список X длиной k (k кратен 2). Известно, что для всех i=0,...,k-1 существует j != i, такое, что IsMatch(X[i],X[j]) возвращает true, где IsMatch - логическая функция сопоставления, которая гарантированно возвращает true по крайней мере для одного j != i для всех i. .

Возвращение : (Длина k/2) список пар (i,j) такой, что IsMatch(i,j) == true для всех пар в списке. Возвращаемые пары могут не быть уникальными (допустим любой допустимый список пар)

Очевидно, моя первая проблема может быть сформулирована в терминах второй с IsMatch(u,v) := { (u - 1/v) == 0 }. Теперь из-за ограничений точности с плавающей точкой никогда не будет точного равенства, поэтому я хочу решение, которое минимизирует ошибку соответствия. Другими словами, предположим, что IsMatch(u,v) возвращает значение u - 1/v, и я хочу, чтобы алгоритм возвращал список, для которого IsMatch возвращает минимальный набор ошибок. Это комбинаторная задача оптимизации. Я думал, что смогу сначала наивно вычислить ошибку совпадения между всеми возможными парами индексов i и j, но затем мне нужно будет выбрать набор минимальных ошибок, и я не знаю, как я это сделаю.

Разъяснение

Функция IsMatch является рефлексивной (IsMatch(a,b) подразумевает IsMatch(b,a)), но не транзитивной. Это, однако, 3-транзитивный: IsMatch(a,b) && IsMatch(b,c) && IsMatch(c,d) подразумевает IsMatch(a,d).

Добавление

Эта проблема, по-видимому, идентична проблеме идеального соответствия минимального веса в теории графов. Однако в моем случае я знаю, что должно быть «хорошее» идеальное соответствие, поэтому распределение весов ребер не является полностью случайным. Я чувствую, что эту информацию нужно как-то использовать. Теперь вопрос в том, есть ли хорошая реализация проблемы соответствия минимального веса, которая использует мои предыдущие знания, чтобы найти решение на ранних этапах поиска. Я также открыт для указаний на простую реализацию любого такого алгоритма.

Answer 1

Надеюсь, у меня твоя проблема.

Ну, если IsMatch(i, j) and IsMatch(j, l), то IsMatch(i, l). В более общем смысле отношение IsMatch является транзитивным, коммутативным и рефлексивным, т.е. это отношение эквивалентности. Алгоритм определяет, какой элемент появляется в списке чаще всего (используйте IsMatch вместо =).

Answer 2

Вы сможете сортировать пары (D [i], N [i]). Вам не нужно делить на ноль - вы можете просто умножить это следующим образом:

bool order(i,j) {
  float ni= N[i]; float di= D[i];
  if(di<0) { di*=-1; ni*=-1; }

  float nj= N[j]; float dj= D[j];
  if(dj<0) { dj*=-1; nj*=-1; }

  return ni*dj < nj*di;
}

Затем отсканируйте отсортированный список, чтобы найти две точки разделения: (N == D) и (N == -D); оттуда вы можете начать сопоставлять взаимные пары, используя:

abs(D[i]*D[j]-N[i]*N[j])<epsilon

как проверка достоверности. Оставьте точки (N == 0) и (D == 0) для последней; не имеет значения, считаете ли вы их негативными или позитивными, поскольку все они будут совпадать друг с другом.

edit: поочередно вы можете просто обрабатывать (N == 0) и (D == 0) случаи отдельно, удаляя их из списка Затем вы можете использовать (N [i] / D [i]) для сортировки остальных индексов. Вы все еще можете начать с 1,0 и -1,0, чтобы убедиться, что вы можете сопоставить почти нулевые наблюдения с точно нулевыми.

Answer 3

Хорошо, в итоге я использовал этот перенесенный код Фортрана , где я просто определяю плотную верхнюю треугольную матрицу расстояний, используя:

complex_t num = N[i]*N[j] - D[i]*D[j];
complex_t den1 = N[j]*D[i];
complex_t den2 = N[i]*D[j];
if(std::abs(den1) < std::abs(den2)){
    costs[j*(j-1)/2+i] = std::abs(-num/den2);
}else if(std::abs(den1) == 0){
    costs[j*(j-1)/2+i] = std::sqrt(std::numeric_limits<double>::max());
}else{
    costs[j*(j-1)/2+i] = std::abs(num/den1);
}

Это прекрасно работает и достаточно быстро для моих целей.

Answer 4

Вы хотите найти j такой, что D (i) * D (j) = N (i) * N (j) {я предположил *, это обычное вещественное умножение}

при условии, что все N (i) отличны от нуля, пусть

Z (i) = D (i) / N (i).

Задача: найти j, для которого Z (i) = 1 / Z (j).

Разбить на позитивы и негативы и обработать отдельно.

возьмите логи для ясности. z (i) = log Z (i).

Сортировка косвенно. Тогда в отсортированном виде у вас должно быть что-то вроде -5 -3 -1 +1 +3 +5, например. Считайте +/- пары, и это должно дать вам исходные индексы.

Я что-то упустил или проблема проста?

Answer 5

Я только что спросил моего друга по CS, и он придумал алгоритм, приведенный ниже. У него здесь нет аккаунта (и, очевидно, он не хочет его создавать), но я думаю, что его ответ стоит поделиться.

// We will find the best match in the minimax sense; we will minimize
// the maximum matching error among all pairs. Alpha maintains a
// lower bound on the maximum matching error. We will raise Alpha until
// we find a solution. We assume MatchError returns an L_1 error.

// This first part finds the set of all possible alphas (which are
// the pairwise errors between all elements larger than maxi-min
// error.
Alpha = 0
For all i:
    min = Infinity
    For all j > i:
        AlphaSet.Insert(MatchError(i,j))
        if MatchError(i,j) < min
            min = MatchError(i,j)
    If min > Alpha
        Alpha = min

Remove all elements of AlphaSet smaller than Alpha

// This next part increases Alpha until we find a solution
While !AlphaSet.Empty()
    Alpha = AlphaSet.RemoveSmallest()
    sol = GetBoundedErrorSolution(Alpha)
    If sol != nil
        Return sol

// This is the definition of the helper function. It returns
// a solution with maximum matching error <= Alpha or nil if
// no such solution exists.
GetBoundedErrorSolution(Alpha) :=
    MaxAssignments = 0
    For all i:
        ValidAssignments[i] = empty set;
        For all j > i:
            if MatchError <= Alpha
                ValidAssignments[i].Insert(j)
                ValidAssignments[j].Insert(i)

        // ValidAssignments[i].Size() > 0 due to our choice of Alpha
        // in the outer loop

        If ValidAssignments[i].Size() > MaxAssignments
            MaxAssignments = ValidAssignments[i].Size()
    If MaxAssignments = 1
        return ValidAssignments
    Else
        G = graph(ValidAssignments)
        // G is an undirected graph whose vertices are all values of i
        // and edges between vertices if they have match error less
        // than or equal to Alpha
        If G has a perfect matching
            // Note that this part is NP-complete.
            Return the matching
        Else
            Return nil

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

Answer 6

хорошо。。 Умножьте каждую пару D и сохраните ее во втором экземпляре структуры с продуктом и индексами элементов, составляющих продукт.

Answer 7

(если я понимаю проблему ...) Вот один из способов сопоставления каждой пары продуктов в двух списках.

1. Умножьте каждую пару N и сохраните ее в структуре вместе с продуктом и индексами элементов, составляющих продукт.
2. Умножьте каждую пару D и сохраните ее во втором экземпляре структуры с продуктом и индексами элементов, составляющих продукт.
3. Сортировать обе структуры на продукте.
4. Выполнить прохождение типа слияния через оба отсортированных массива структур. Каждый раз, когда вы находите продукт из одного массива, который достаточно близок к другому, вы можете записать две подписки из каждого отсортированного списка на соответствие.
5. Вы также можете использовать один отсортированный список для функции ismatch, выполняя бинарный поиск по продукту.