Hungarian Algorithm は機能しますが、この場合はもっと単純なアルゴリズムを使用できます。暗黙のコスト マトリックスは、特殊な形式の対称マトリックスです。
ABS(SUBJ.match_field-CTRL.match_field)
したがって、最適な割り当てでは、値によって並べ替えられた{SUBJ i , CTRL j }も同様に並べ替えられることを比較的簡単に証明できます。SUBJ.match_fieldCTRL.match_field
証明:によって順序付けられていない代入{SUBJ i , CTRL j }を考えてみましょう。次に、少なくとも 1 つの反転、つまり割り当て{SUBJ i1 , CTRL j1 }と{SUBJ i2 , CTRL j2 }のペアがあり、SUBJ.match_fieldCTRL.match_field
SUBJ.match_fieldi1 < SUBJ.match_fieldi2、しかし
CTRL.match_fieldj1 > CTRL.match_fieldj2
次に、反転ペアを非反転ペアに置き換えることができます
{SUBJ i1 , CTRL j2 }および{SUBJ i2 , CTRL j1 }
SUBJ.match_field( i1 , i2 ) とCTRL.match_field( j1 , j2 )の 6 つの相対配置すべての逆代入のコスト以下のコスト( Wolfram Alpha へのリンク)。：証拠
この観察があれば、以下の動的計画法アルゴリズムが最適な割り当てを導き出すことを証明するのは簡単です。
- 各科目
Nの複製を作成します。注文match_field
- コントロールの順序
match_field
assignmentsサイズの空の配列を準備しますN * subject.SIZE- memoizationのため
memにサイズN * subject.SIZEbyの空の 2D 配列を準備します。すべての要素をcontrol.SIZE-1
Recursive_Assign以下の疑似コードで定義された呼び出しassignments表には、 、包括的、および、排他的の間の位置に各科目の割り当てNが含まれています。iN*iN*(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
以下は、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 < @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
上記の呼び出しは、 と の両方が場所によってフィルター処理され、呼び出しを行う前に のコピーがテーブル値パラメーター (または DB2 の場合は一時テーブル) に挿入されていることを前提としsubjectsてcontrolsいNますsubjects。
これはsqlfiddle で実行中のデモです。