SQL中的组合优化匹配

熊本

我在用SQL开发匹配算法时遇到了麻烦。我有一张桌子subjects。这些中的每一个都需要与表中的相同行数匹配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
}中，_按SUBJ.match_field的值CTRL.match_field排序也将是有序的。
证明： 考虑一个由 { }_排序的赋值 {SUBJ_ i ，CTRL j
}SUBJ.match_field而不是CTRL.match_field。然后，您至少会有一个反转，即一对赋值 {SUBJ
i1，CTRL j1 }_和 _这样，
SUBJ.match_fieldi1
CTRL.match_fieldj1 > CTRL.match_fieldj2
然后，您可以将反相对替换为非反相对
{SUBJ i1，CTRL j2 }_和 _
小于或等于SUBJ.match_field（i1，i2）和CTRL.match_field（j1，j2）的所有六个相对位置的反向分配的成本（链接到Wolfram
Alpha）。
：证明
有了这个观察，就很容易证明以下动态编程
算法具有最佳分配：
让N每个主题的复印件; 排序match_field
订单控制依据 match_field
准备一个assignments大小为空的数组N * subject.SIZE
准备一个空的2D阵列mem尺寸的N * subject.SIZE由control.SIZE用于记忆化 ; 将所有元素设置为-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
这是在ideone上使用C＃的上述伪代码的实现。
该算法已准备好在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 这是调用此存储过程的方式：
-- 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上运行的演示。

SQL中的组合优化匹配

熊本 LV1