2012-08-11 130 views
-2

我想查找節點之間最近的距離。查找節點之間最近的距離

這是我的示例數據:

節點,X,Y

 
1, 3, 5 
2, 6, 9 
3, 13, 15 
4, 16, 20 
5, 30, 50 

作爲一個例子,從節點1到節點2的5最近距離我想找到從最近距離所有節點都作爲節點2,3,4,5。

我該如何在Perl中實現這個功能?

這是我到目前爲止有:

use strict; 
use warnings; 
use Data::Dumper; 

open(IN , "<" , "sample.txt") or die "Can't open this file."; 

my @two_dimentional_array; 
while (my $line=<IN>) 
{ 
    my @arr_line=split (" *, *" , $line); 
     my @one_dimentional_array; 
     push @one_dimentional_array , @arr_line; 
     push @two_dimentional_array, [@arr_line]; 
} 

for(my $i=0 ; $i<=$#two_dimentional_array ; $i++) 
{ 
    my ($n_1 , $X_1 , $y_1)[email protected]{$two_dimentional_array[$i]}; 
    for (my $j=0 ; $j<=$#two_dimentional_array ; $j++) 
    { 
     my ($n_2 , $X_2 , $y_2)[email protected]{$two_dimentional_array[$j]}; 

     chomp($y_1); 
     chomp($y_2); 
     if($n_1 != $n_2) 
     { 
      my $distance=sqrt(($X_2-$X_1)**2 + ($y_2-$y_1)**2); 
      print "Distance ".$distance." from node ".$n_1." to node ".$n_2."\n"; 
     } 
    } 
} 
#print Dumper(\@two_dimentional_array); 

回答

1
#!/usr/bin/perl 

use strict; 
use warnings; 

my (@data, @temp, @result); 

sub calc { 
    my ($a, $b) = @_; 
    my $dat = 0; 
    $dat += ($a->[$_] - $b->[$_]) ** 2 for (1,2); 
    return sqrt $dat; 
} 

while (<DATA>) { 
    push @data, [split /,?\s+/]; 
} 

for my $x (@data) { 
    for my $y (@data) { 
     push @temp, [calc($x, $y), $x, $y] if ($x->[0] > $y->[0]); 
    } 
} 

@result = sort { $a->[0] <=> $b->[0]; } @temp; 
printf "%-18s => [%s], [%s]\n", $_->[0], 
    join(', ', @{$_->[1]}), join(', ', @{$_->[2]}) for @result; 

__DATA__ 
1, 3, 5 
2, 6, 9 
3, 13, 15 
4, 16, 20 
5, 30, 50 

輸出:

5     => [2, 6, 9], [1, 3, 5] 
5.8309518948453 => [4, 16, 20], [3, 13, 15] 
9.21954445729289 => [3, 13, 15], [2, 6, 9] 
14.142135623731 => [3, 13, 15], [1, 3, 5] 
14.8660687473185 => [4, 16, 20], [2, 6, 9] 
19.8494332412792 => [4, 16, 20], [1, 3, 5] 
33.1058907144937 => [5, 30, 50], [4, 16, 20] 
38.9101529166874 => [5, 30, 50], [3, 13, 15] 
47.5078940808788 => [5, 30, 50], [2, 6, 9] 
52.4785670536077 => [5, 30, 50], [1, 3, 5] 
+0

先生,我想使用哈希的話,我怎麼能impliment呢? – 2012-08-11 06:57:47

+0

@FaisalHashmi:你爲什麼要使用散列? – Borodin 2012-08-11 19:38:54

1

該代碼會發現第一對是最小距離分開。

use strict; 
use warnings; 

# @data contains (node number, x, y) from the file 
# 
my @data; 

open my $fh, '<', 'sample.data' or die $!; 

while (<$fh>) { 
    my @node = /\d+/g; 
    push @data, \@node if @node; 
} 

# @min contains (first node number, second node number, distance) 
# for the most recently-found minimum distance 
# 
my @min; 

for my $node1 (0 .. $#data-1) { 
    for my $node2 ($node1+1 .. $#data-1) { 
    my $dist; 
    $dist += ($data[$node2][$_] - $data[$node1][$_]) ** 2 for 1, 2; 
    $dist = sqrt $dist; 
    @min = ($data[$node1][0], $data[$node2][0], $dist) unless @min and $min[2] <= $dist; 
    } 
} 

printf "%d to %d = %f\n", @min; 

輸出

1 to 2 = 5.000000