Комбинаторная оптимизация соответствия в SQL

У меня возникла проблема с разработкой соответствующего алгоритма в SQL. У меня есть одна тема для стола. Каждому из них необходимо сопоставить одно и то же количество строк в controls таблицей (для этого вопроса предположим, что для каждого объекта нужно выбрать две строки или элементы управления). Расположение выбранных элементов управления должно соответствовать точно, и выбранные элементы управления должны иметь значение в match_field , которое максимально приближено к объектам.

Вот несколько примеров данных:

Предметы таблицы:

 id location match_field 1 1 190 2 2 2000 3 1 100 

Элементы управления таблицей:

 id location match_field 17 1 70 11 1 180 12 1 220 13 1 240 14 1 500 15 1 600 16 1 600 10 2 30 78 2 1840 79 2 2250 

Здесь будет оптимальный результат из данных выборки:

 subject_id control_id location match_field_diff 1 12 1 30 1 13 1 50 2 78 2 160 2 79 2 250 3 17 1 30 3 11 1 80 

Это становится сложно, потому что, например, управление 11 является ближайшим совпадением с предметом 1. Однако в оптимальном решении 11 управления соответствует предмет 3.

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

Нет необходимости получать абсолютные оптимальные результаты; довольно хорошее приближение со мной было бы неплохо.

Кажется, должно быть хорошее решение на основе набора для этой проблемы, но я не могу придумать, как это сделать. Вот код, который назначает равное количество элементов управления для каждого объекта только на основе местоположения:

 select * from ( select subject.id, control.id, subject.location, row_number() over ( partition by subject.location order by subject.id, control.id ) as rn, count(distinct control.id) over ( partition by subject.location ) as controls_in_loc from subjects join controls on control.location = subject.location ) where mod(rn,controls_in_loc+1) = 1 

Однако я не могу понять, как добавить компонент нечеткого соответствия. Я использую DB2, но могу преобразовать алгоритм в DB2, если вы используете что-то еще.

Заранее спасибо за вашу помощь!

Обновление: я в основном убежден, что SQL не является подходящим инструментом для этой работы. Однако, чтобы быть уверенным (и потому, что это интересная проблема), я предлагаю щедрость, чтобы увидеть, возможно ли работающее SQL-решение. Это должно быть комплексное решение. Он может использовать итерацию (цикл за один и тот же запрос несколько раз для достижения результата), но количество итераций должно быть намного меньше, чем количество строк для большой таблицы. Он не должен перебирать каждый элемент таблицы или использовать курсоры.

Хотя венгерский алгоритм будет работать, в вашем случае может быть использован гораздо более простой алгоритм. Ваша матрица неявных затрат представляет собой симметричную матрицу специальной формы:

 ABS(SUBJ.match_field-CTRL.match_field) 

Поэтому вы можете относительно легко доказать, что при оптимальном присваивании {SUBJ i , CTRL j }, упорядоченном CTRL.match_field будут также SUBJ.match_field значения CTRL.match_field .

Доказательство. Рассмотрим назначение {SUBJ i , CTRL j }, упорядоченное по SUBJ.match_field , которое не упорядочено по CTRL.match_field . Тогда у вас есть хотя бы одна инверсия , т. Е. Пара назначений {SUBJ i1 , CTRL j1 } и {SUBJ i2 , CTRL j2 } такая, что

SUBJ.match_field i1 < SUBJ.match_field i2 , но

CTRL.match_field j1 > CTRL.match_field j2

Затем вы можете заменить инвертированную пару на неинвертированную

{SUBJ i1 , CTRL j2 } и {SUBJ i2 , CTRL j1 }

стоимости, которая меньше или равна стоимости инвертированного назначения для всех шести относительных мест размещения SUBJ.match_field ( i1 , i2 ) и CTRL.match_field ( j1 , j2 ) ( ссылка на Wolfram Alpha ). : Proof

Имея это наблюдение, легко доказать, что ниже приведен алгоритм динамического программирования с оптимальным присваиванием:

  • Сделайте N дубликатов по каждому предмету; match_field по match_field
  • Элементы управления match_field
  • Подготовьте пустые assignments массива размера N * subject.SIZE
  • Подготовьте пустой массив двумерных массивов размера N * subject.SIZE помощью control.SIZE для memoization ; установить все элементы на -1
  • Вызов Recursive_Assign определенный в псевдокоде ниже
  • Таблица assignments теперь содержит N присвоений для каждого субъекта i в положениях между N*i , включительно и N*(i+1) , исключительные.

 FUNCTION Recursive_Assign // subjects contains each original subj repeated N times PARAM subjects : array of int[subjectLength] PARAM controls: array of int[controlLength] PARAM mem : array of int[subjectLength,controlLength] PARAM sp : int // current subject position PARAM cp : int // current control position PARAM assign : array of int[subjectLength] BEGIN IF sp == subjects.Length THEN RETURN 0 ENDIF IF mem[sp, cp] > 0 THEN RETURN mem[sp, cp] ENDIF int res = ABS(subjects[sp] - controls[cp]) + Recursive_Assign(subjects, controls, mem, sp + 1, cp + 1, assign) assign[sp] = cp IF cp+1+subjects.Length-sp < controls.Length THEN int alt = Recursive_Assign(subjects, controls, mem, sp, cp + 1, assign) IF alt < res THEN res = alt ELSE assign[sp] = cp ENDIF ENDIF RETURN (mem[sp, cp] = res) END 

Ниже приведена реализация вышеупомянутого псевдокода с использованием C # на ideone.

Этот алгоритм готов к повторной записи в виде набора в SQL. Попытка вставить его в исходную проблему (с группировкой по местоположениям и созданием нескольких копий объекта) добавит ненужный уровень сложности к довольно сложной процедуре, поэтому я немного упрощусь, используя таблицу -значные параметры SQL Server. Я не уверен, что DB2 предоставляет аналогичные возможности, но если это не так, вы должны иметь возможность заменять их временными таблицами.

Хранимая процедура ниже представляет собой почти прямую транскрипцию вышеуказанного псевдокода в синтаксис SQL Server для хранимых процедур:

 CREATE TYPE SubjTableType AS TABLE (row int, id int, match_field int) CREATE TYPE ControlTableType AS TABLE (row int, id int, match_field int) CREATE PROCEDURE RecAssign ( @subjects SubjTableType READONLY , @controls ControlTableType READONLY , @sp int , @cp int , @subjCount int , @ctrlCount int ) AS BEGIN IF @sp = @subjCount BEGIN RETURN 0 END IF 1 = (SELECT COUNT(1) FROM #MemoTable WHERE sRow=@sp AND cRow=@cp) BEGIN RETURN (SELECT best FROM #MemoTable WHERE sRow=@sp AND cRow=@cp) END DECLARE @res int, @spNext int, @cpNext int, @prelim int, @alt int, @diff int, @sId int, @cId int SET @spNext = @sp + 1 SET @cpNext = @cp + 1 SET @sId = (SELECT id FROM @subjects WHERE row = @sp) SET @cId = (SELECT id FROM @controls WHERE row = @cp) EXEC @prelim = RecAssign @subjects=@subjects, @controls=@controls, @sp=@spNext, @cp=@cpNext, @subjCount=@subjCount, @ctrlCount=@ctrlCount SET @diff = ABS((SELECT match_field FROM @subjects WHERE row=@sp)-(SELECT match_field FROM @controls WHERE row=@cp)) SET @res = @prelim + @diff IF 1 = (SELECT COUNT(1) FROM #Assignments WHERE sRow=@sp) BEGIN UPDATE #Assignments SET cId=@cId, sId=@sId, diff=@diff WHERE sRow=@sp END ELSE BEGIN INSERT INTO #Assignments(sRow, sId, cId, diff) VALUES (@sp, @sId, @cId, @diff) END IF @cp+1+@subjCount-@sp < @ctrlCount BEGIN EXEC @alt = RecAssign @subjects=@subjects, @controls=@controls, @sp=@sp, @cp=@cpNext, @subjCount=@subjCount, @ctrlCount=@ctrlCount IF @alt < @res BEGIN SET @res = @alt END ELSE BEGIN UPDATE #Assignments SET cId=@cId, sId=@sId, diff=@diff WHERE sRow=@sp END END INSERT INTO #MemoTable (sRow, cRow, best) VALUES (@sp, @cp, @res) RETURN @res END 

Вот как вы называете эту хранимую процедуру:

 -- The procedure uses a temporary table for memoization: CREATE TABLE #MemoTable (sRow int, cRow int, best int) -- The procedure returns a table with assignments: CREATE TABLE #Assignments (sRow int, sId int, cId int, diff int) DECLARE @subj as SubjTableType INSERT INTO @SUBJ (row, id, match_field) SELECT ROW_NUMBER() OVER(ORDER BY match_field ASC)-1 AS row, id, match_field FROM subjects DECLARE @ctrl as ControlTableType INSERT INTO @ctrl (row, id, match_field) SELECT ROW_NUMBER() OVER(ORDER BY match_field ASC)-1 AS row, id, match_field FROM controls DECLARE @subjCount int SET @subjCount = (SELECT COUNT(1) FROM subjects) DECLARE @ctrlCount int SET @ctrlCount = (SELECT COUNT(1) FROM controls) DECLARE @best int EXEC @best = RecAssign @subjects=@subj , @controls=@ctrl , @sp=0 , @cp=0 , @subjCount=@subjCount , @ctrlCount=@ctrlCount SELECT @best SELECT sId, cId, diff FROM #Assignments 

Вышеприведенный вызов предполагает, что как subjects и controls были отфильтрованы по местоположению, и что N экземпляров subjects был вставлен в параметр таблицы (или временную таблицу в случае DB2) перед выполнением вызова.

Вот бегущая демонстрация на sqlfiddle .

Я рекомендую вам взглянуть на проблему и алгоритм максимальных совпадений в двудольном графе . Идея состоит в том, чтобы построить график, где узлы слева – ваши subjects а узлы справа – controls (поэтому их называют двудольными). Построение графа тривиально, вы создаете source узел, который соединяется со всеми предметами, и вы соединяете все узлы управления с узлом sink . Затем вы создаете ребро между subject и узлом control если это применимо. Затем вы запускаете алгоритм максимального соответствия, который даст вам то, что вы ищете, максимально возможное соответствие объектов и элементов управления.

Не забудьте проверить этот пример Boost BGL, как это сделать, вам нужно только построить график и вызвать функцию BGL edmonds_maximum_cardinality_matching .