Javaで「ストリーミングナップサック」問題を効率的に実装したい。
問題は、整数データのストリーム入力が連続して来ることです。たとえば、-1、2、9、5、5、11、1 -3、...
問題は、それらの合計が「n>0」である最初の「k」要素を見つけることです。たとえば、k=3およびn=12の場合、解は...、2、...、5、5になります。
そのための効率的なアルゴリズムは何ですか?
Javaで「ストリーミングナップサック」問題を効率的に実装したい。
問題は、整数データのストリーム入力が連続して来ることです。たとえば、-1、2、9、5、5、11、1 -3、...
問題は、それらの合計が「n>0」である最初の「k」要素を見つけることです。たとえば、k=3およびn=12の場合、解は...、2、...、5、5になります。
そのための効率的なアルゴリズムは何ですか?
これまでに出会った最大値の整数の逆順のPriorityQueueを保持します。k-1
新しい整数が入力されるたびに、その整数と k-1 個の数値の合計が n より大きいかどうかがチェックされます。そうであれば、見つけたセットを返します。それ以外の場合は、この数値が最小の数値よりも大きいかどうかを確認しk-1
ます (そのため、優先キューを逆順にする必要があります)。そうであれば、最小要素を抽出し、新しい要素をキューにプッシュします。そうでない場合は、単にストリーム内の次の番号に移動します。
http://programmingpraxis.com/2012/05/15/streaming-knapsack/2/で答えを見つけました :(主に正の整数値用です)
これは動的計画法の問題です。0 から k−1 までの番号が付けられた k 行と 1 から n までの番号が付けられた n 列からなる行列を作成します。行列のすべてのセルは最初は空ですが、行 0 のセルにはそれぞれ null リスト (空のセルと区別できる必要があります) が含まれています。次に、入力ストリームの項目が順番に読み取られます。各アイテム x について、解が見つかり、セル (k-1,n-x) が空でない場合は処理が停止します。解は、セル (k-1,n-x) とアイテム x 内のアイテムのリストです。それ以外の場合、行列内の空でないセル (r,c) ごとに、r+1 の場合
行列はスパースなので、行列の代わりに (r,c) をキーとするハッシュ テーブルを使用します。デモンストレーションでは、正の整数のストリームを提供するために乱数ジェネレータを使用します。
(define (streaming-knapsack k n)
(define (hash rc) (+ (car rc) (* n (cdr rc))))
(let ((table (make-hash hash equal? #f 997)))
(let loop ((x (+ (randint n) 1)))
(display x) (newline)
(cond ((table 'lookup (cons (- k 1) (- n x))) =>
(lambda (xs) (cons x xs)))
(else (let loop ((xs (table 'enlist)))
(when (pair? xs)
(let* ((rcs (car xs)) (r (caar rcs)) (c (cdar rcs))
(s (cdr rcs)) (r1 (+ r 1)) (cx (+ c x)))
(when (and (< r1 k) (< cx n)
(not (table 'lookup (cons r1 cx))))
(table 'insert (cons r1 cx) (cons x s))))
(loop (cdr xs))))
(when (not (table 'lookup (cons 1 x)))
(table 'insert (cons 1 x) (list x)))
(loop (+ (randint n) 1)))))))
外側のループは、入力ストリーム内の項目ごとに 1 回実行されます。入力ストリームをオンザフライで生成しているため、通過する各ストリーム要素が表示されます。cond の最初の句は、ハッシュ テーブルで (r-1, c-x) 項目を探し、存在する場合は結果を返します。そうでない場合、cond の else 句は、ハッシュ テーブル内のすべての項目をループし、すべてのテストに合格した場合は新しいテーブル項目を追加し、存在しない場合は (1 x) テーブル項目を追加し、次の項目にループします。入力ストリーム内の要素。
実際には、2 回発生する式 (+ (randint n) 1) を、入力ストリームから次の項目を取得する関数に置き換え、その関数をパラメーターとして streaming-knapsack に渡す必要があります。
Standard Prelude のハッシュ テーブルと乱数ジェネレーターを使用しました。プログラムはhttp://programmingpraxis.codepad.org/WHdBXcyrで実行できます。