5

整数AとB（サイズが）A以下の2つのセットがあり、「どれくらい近いか」Bという質問に答えたいと思います。私がこの質問に答えたい方法は、inを見つけるために与えられたinからどれだけ遠くまで行かなければならないかの尺度を作成することです。 ABaAbB

私が作成したい特定のメジャーは次のことを行います。それぞれaについて、最も近いものを見つけます。b唯一のキャッチは、aをと一致させるbと、それを使用して他のを一致させるaことができなくなることです。（編集：私が実装しようとしているアルゴリズムは、常に短い一致を優先します。したがって、が複数に最も近い場合は、最も近いものを選択してください。複数が同じ距離にある場合はどうすればよいかわかりません。に、今私は前にあるものを選んでいますbabaababab、ただし、これは非常に恣意的であり、必ずしも最適ではありません。）最終製品であるこれらのセットを作成するための測定値は、縦軸にペアの数、x軸にペアの距離を示すヒストグラムです。

したがって、A = {1, 3, 4}との場合、B = {1, 5, 6, 7}次のa,bペアを取得します：1,1、、。これらのデータの場合、ヒストグラムには、距離が0のペア、距離が1のペア、距離が3のペアが表示されます。4,53,6

（これらのセットの実際のサイズには約100,000要素の上限があり、すでに低から高にソートされているディスクから読み込みます。整数の範囲は1から〜20,000,000です。編集：また、との要素AはB一意です。つまり、繰り返される要素。）

私が思いついた解決策は少し不格好に感じます。私はPerlを使用していますが、問題は多かれ少なかれ言語に依存しません。

  1. まず、ハッシュを作成します。との和集合に表示される数値ごとに1つのキーと、各数値が、、、Aまたは両方にB表示されるかどうかを示す値を使用します。たとえば、数値5が両方のデータセットに表示される場合などです。（にのみ表示された場合は、があります。）AB$hash{5} = {a=>1, b=>1}A$hash{5} = {a=>1}

  2. 次に、とにA表示されるすべてのハッシュ要素を繰り返して検索し、メジャーでそれらをマークして、ハッシュから削除します。AB

  3. 次に、すべてのハッシュキーを並べ替えて、ハッシュの各要素がリンクリストのように最近傍を指すようにします。ここで、特定のハッシュ要素はのようになり$hash{6} = {b=>1, previous=>4, next=>8}ます。Aリンクリストは、次の要素と前の要素がにあるか、にあるかを認識していませんB。

  4. 次に、で始まるペアの距離をループしd=1、距離のあるすべてのペアを見つけてdマークを付け、一致する要素がなくなるまでハッシュから削除しますA。

ループは次のようになります。

for ($d=1; @a > 0; $d++) {
    @left = ();
    foreach $a in @a {
        $next = $a;
        # find closest b ahead of $a, stop searching if you pass $d
        while (exists $hash{$next}{next} && $next - $a < $d) {
            $next = $hash{$next}{next};
        }
        if ($next is in B && $next - $a == $d) {
            # found a pair at distance $d
            mark_in_measure($a, $next);
            remove_from_linked_list($next);
            remove_from_linked_list($a);
            next;
        }

        # do same thing looking behind $a
        $prev = $a;
        ...

        # you didn't find a match for $a
        push @left, $a;
    }
    @a = @left;
}

bこのループは明らかに、'sより後に表示される'sに一致するペアを優先しaます。後が前よりも優れているかどうかを判断するための賢明な方法があるかどうかはわかりません（ペアを近づけるという点で優れています）。私が興味を持っている主な最適化は処理時間です。

4

2 に答える 2

2

割り当て問題の特定のケースがあるように聞こえます（重み付けされた2部グラフで最小一致を見つける）。

割り当ての問題を解決するアルゴリズムはO（N ^ 3）では遅すぎますが、特定の重み関数を利用するか、ヒストグラムの代わりにヒストグラムのみが必要な方法を利用することで、この複雑さの一部を取り除くことができると確信しています。完全一致。

于 2011-10-12T16:59:13.210 に答える
1 
#!/usr/bin/perl

use strict;
use warnings FATAL => 'all';
use diagnostics;  

# http://www.hungarianalgorithm.com/solve.php?c=3-2-6-22--7-2-2-18--13-8-4-12--23-18-14-2&random=1
# https://www.topcoder.com/community/data-science/data-science-tutorials/assignment-problem-and-hungarian-algorithm/
# http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf

my @mat;
my @out_mat;

my $spaces    = 6;
my $precision = 0;

my $N = 10;
my $M = 12;
my $r = 100;

my @array1; my @array2;

for my $i (1..$N) {
    push @array1, sprintf( "%.${precision}f",  rand($r)  );
}

for my $i (1..$M) {
    push @array2, sprintf( "%.${precision}f",  rand($r)  );
}

#@array1 = ( 1, 3, 4);      # $mat[i]->[j] = abs( array1[i] - array2[j] )
#@array2 = ( 1, 5, 6, 7);

#                1     5     6     7

#     1     [    0*    4     5     6 ]

#     3     [    2     2*    3     4 ]

#     4     [    3     1     2*    3 ]

my $min_size  = $#array1 < $#array2 ? $#array1 : $#array2;
my $max_size  = $#array1 > $#array2 ? $#array1 : $#array2;

for (my $i = 0; $i < @array1; $i++){
   my @weight_function;
   for (my $j = 0; $j < @array2; $j++){
      my $dif = sprintf( "%.${precision}f", abs ($array1[$i] - $array2[$j])  );
      #my $dif = sprintf( "%.${precision}f", ($array1[$i] - $array2[$j])**2  ); 
      push @weight_function, $dif;
   }
   push @mat, \@weight_function;
}


# http://cpansearch.perl.org/src/TPEDERSE/Algorithm-Munkres-0.08/lib/Algorithm/Munkres.pm

Algorithm::Munkres::assign(\@mat,\@out_mat);


print "\n\@out_mat index  = [";
for my $index (@out_mat) {
   printf("%${spaces}d", $index);
}
print " ]\n";

print "\@out_mat values = [";

my %hash;
for my $i (0 .. $max_size){
   my $j = $out_mat[$i];
   last if ( $i > $min_size and $#array1 < $#array2 );
   next if ( $j > $min_size and $#array1 > $#array2 );
   my $dif = $mat[$i]->[$j];
   printf( "%${spaces}.${precision}f", $dif );
   $hash{ $dif } { $i } { 'index_array1' } = $i;
   $hash{ $dif } { $i } { 'index_array2' } = $j;
   $hash{ $dif } { $i } { 'value_array1' } = $array1[$i];
   $hash{ $dif } { $i } { 'value_array2' } = $array2[$j]; 
}

print " ]\n\n";


my $soma_da_dif = 0;

foreach my $min_diferenca ( sort { $a <=> $b } keys %hash ){
   foreach my $k ( sort { $a <=> $b } keys %{$hash{$min_diferenca}} ){
      $soma_da_dif += $min_diferenca;
      my $index_array1 = $hash{ $min_diferenca } { $k } { 'index_array1' };
      my $index_array2 = $hash{ $min_diferenca } { $k } { 'index_array2' };
      my $value_array1 = $hash{ $min_diferenca } { $k } { 'value_array1' };
      my $value_array2 = $hash{ $min_diferenca } { $k } { 'value_array2' };
      printf( "   index (%${spaces}.0f,%${spaces}.0f), values (%${spaces}.${precision}f,%${spaces}.${precision}f), dif = %${spaces}.${precision}f\n", 
              $index_array1, $index_array2, $value_array1, $value_array2, $min_diferenca );

   }
}
print "\n\nSum = $soma_da_dif\n";





#-------------------------------------------------#
#------------------ New-Package ------------------# 

{ # start scope block

package Algorithm::Munkres;

use 5.006;
use strict;
use warnings;

require Exporter;
our @ISA = qw(Exporter);
our @EXPORT = qw( assign );
our $VERSION = '0.08';

...
... <---- copy all the 'package Algorithm::Munkres' here
...

return $minval;
}

1;  # don't forget to return a true value from the file

} # end scope block
于 2016-10-14T02:47:06.123 に答える