Мне нужно найти кратчайший набор путей, чтобы соединить каждый элемент набора A хотя бы с одним элементом набора B. Повторения в A или B разрешены (но не в обоих), и ни один элемент не может быть оставлен неподключенным. Примерно так:
Я представляю элементы как целые числа, поэтому «стоимость» соединения - это просто абсолютная величина разницы , У меня также есть стоимость пересечения путей, поэтому, если набор 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
, когда достигну целевого количества элементов. Кажется, хорошо ...