Решение с минимальными затратами для подключения всех элементов в наборе A к хотя бы одному элементу в наборе B - PullRequest
Новая
       18

Решение с минимальными затратами для подключения всех элементов в наборе A к хотя бы одному элементу в наборе B

1 голос
/ 27 апреля 2020

Мне нужно найти кратчайший набор путей, чтобы соединить каждый элемент набора A хотя бы с одним элементом набора B. Повторения в A или B разрешены (но не в обоих), и ни один элемент не может быть оставлен неподключенным. Примерно так:

enter image description here

Я представляю элементы как целые числа, поэтому «стоимость» соединения - это просто абсолютная величина разницы , У меня также есть стоимость пересечения путей, поэтому, если набор A = [60, 64] и набор B = [63, 67], то (60 -> 67) влечет за собой дополнительные расходы. В любом наборе может быть любое количество элементов.

Я рассчитал таблицу переходов и затрат (расстояния и пересечения), но не могу найти алгоритм, чтобы найти самое дешевое решение. Я продолжаю заканчивать либо слишком большим количеством соединений (то есть повторениями в и A и B), либо жадными решениями, которые пропускают элементы (например, когда A и B не перекрываются). Мне не удалось найти примеры именно такой проблемы в Интернете, поэтому я надеялся, что кто-то здесь сможет помочь или, по крайней мере, направить меня в правильном направлении. Я не теоретик графиков (очевидно!), И я пишу на Swift, поэтому примеры кода на Swift (или псевдокоде) будут высоко оценены.

ОБНОВЛЕНИЕ: Решение, предлагаемое @Daniel, почти работает, но иногда добавляет ненужные дубликаты. Я думаю это может быть связано с сортировкой очереди приоритетов - дубликаты всегда включают в себя идентичные элементы с одинаковыми затратами. Моей первой мыслью было добавить некое «позиционное кодирование» (да, на языке Transformer) к затратам, чтобы затраты компенсировались их позициями (хотя, конечно, это не гарантирует уникальных затрат). Я думал, что выложу свою версию Swift здесь, на случай, если у кого-нибудь возникнут какие-либо идеи: 

public static func voiceLeading(from chA: [Int], to chB: [Int]) -> Set<[Int]> {
        var result: Set<[Int]> = Set()
        let im = intervalMatrix(chA, chB: chB)
        if im.count == 0 { return [[0]] }
        let vc = voiceCrossingCostsMatrix(chA, chB: chB, cost: 4)
        let cm = VectorUtils.absoluteAddMatrix(im, toMatrix: vc)

        var A_links: [Int:Int] = [:]
        var B_links: [Int:Int] = [:]
        var priorityQueue: [Entry] = []
        for (i, a) in chA.enumerated() {
            for (j, b) in chB.enumerated() {
                priorityQueue.append(Entry(a: a, b: b, cost: cm[i][j]))
                if A_links[a] != nil {
                    A_links[a]! += 1
                } else {
                    A_links[a] = 1
                }
                if B_links[b] != nil {
                    B_links[b]! += 1
                } else {
                    B_links[b] = 1
                }
            }
        }
        priorityQueue.sort { $0.cost > $1.cost }
        while priorityQueue.count > 0 {
            let entry = priorityQueue[0]
            if A_links[entry.a]! > 1 && B_links[entry.b]! > 1 {
                A_links[entry.a]! -= 1
                B_links[entry.b]! -= 1
            } else {
                result.insert([entry.a, (entry.b - entry.a)])
            }
            priorityQueue.remove(at: 0)
        }

        return result
    }

Конечно, поскольку дубликаты имеют одинаковые оценки, не должно быть проблемой просто удалить дополнения, но это кажется немного хаки sh ...

ОБНОВЛЕНИЕ 2: немного меньше хаки sh (но все же немного!); так как требование состоит в том, что мой результат должен иметь равное количество элементов max(|A|, |B|), я могу просто прекратить добавлять записи в свой result, когда достигну целевого количества элементов. Кажется, хорошо ...

Ответы [ 2 ]

2 голосов
/ 28 апреля 2020

Это простая задача:

  • Добавьте все ребра графа в priority_queue, где самый большой приоритет - ребро с наибольшим весом.

  • Посмотрите каждое ребро e = (u, v, w) в priority_queue, где u в A , v в B и w в вес.

  • Если удаление e из графика не оставляет u или v изолированным, удалите его.

  • В противном случае e является частью ответа.

Этого должно быть достаточно для вашего случая: 

#include <bits/stdc++.h>
using namespace std;

struct edge {
    int u, v, w;
    edge(){}
    edge(int up, int vp, int wp){u = up; v = vp; w = wp;}
    void print(){ cout<<"("<<u<<", "<<v<<")"<<endl; }
    bool operator<(const edge& rhs) const {return w < rhs.w;}
};

vector<edge> E;             //edge set
priority_queue<edge> pq;
vector<edge> ans;
int grade[5] = {3, 3, 2, 2, 2};

int main(){

    E.push_back(edge(0, 2, 1)); E.push_back(edge(0, 3, 1)); E.push_back(edge(0, 4, 4));
    E.push_back(edge(1, 2, 5)); E.push_back(edge(1, 3, 2)); E.push_back(edge(1, 4, 0));
    for(int i = 0; i < E.size(); i++) pq.push(E[i]);

    while(!pq.empty()){
        edge e = pq.top();
        if(grade[e.u] > 1 && grade[e.v] > 1){
            grade[e.u]--; grade[e.v]--;
        }
        else ans.push_back(e);
        pq.pop();
    }

    for(int i = 0; i < ans.size(); i++) ans[i].print();

    return 0;
}

Сложность: O (E lg (E)) .

2 голосов
/ 28 апреля 2020

Я думаю, что эта проблема заключается в «минимально-взвешенном двухстороннем сопоставлении» (хотя поиск «максимально-взвешенного двудольного сопоставления» также был бы уместен, как раз наоборот)

...