0

我有一个问题，我找不到答案。我正在使用 Perl。我的输入是一个对称的成本矩阵，有点像 TSP。

我想知道位于我的边界（即 10）之下的所有解决方案。

这是我的矩阵：

-   B   E   G   I   K   L   P   S   
B   -   10  10  2   10  10  10  10  
E   10  -   2   10  10  10  1   10  
G   10  2   -   10  2   3   3   3   
I   2   10  10  -   4   10  10  2   
K   10  10  2   4   -   10  10  3   
L   10  10  3   10  10  -   2   2   
P   10  1   3   10  10  2   -   10  
S   10  10  3   2   3   2   10  -

有人知道如何实现分支定界算法来解决这个问题吗？现在，我确实用“-”替换了矩阵中的每 10 个。

到目前为止我做了什么：

 @verwbez = ( ["-", B, E, G, I, K, L, P, S], 
              [B,"-", 10, 10, 2, 10, 10, 10, 10], 
              [E, 10, "-", 2, 10, 10, 10, 1, 10], 
              [G, 10, 2, "-", 10, 2, 3, 3, 3], 
              [I, 2, 10, 10, "-", 4, 10, 10, 2], 
              [K, 10, 10, 2, 4, "-", 10, 10, 3], 
              [L, 10, 10, 3, 10, 10, "-", 2, 2], 
              [P, 10, 1, 3, 10, 10, 2, "-", 10], 
              [S, 10, 10, 3, 2, 3, 2, 10, "-"]);
for ($i=0;$i<=$#verwbez;$i++) {
    for ($j=0; $j<=$#{$verwbez[$i]};$j++) {
        while ($verwbez[$i][$j] >=7) { 
            $verwbez[$i][$j] = "-";
        }
    }
}

基本上只是改变矩阵，每10个被替换为“-”。现在我想找到所有低于 10 的解决方案，并且包含 4 个总是两个城市连接在一起的地区。但不幸的是，我不知道如何继续/开始......

4

1 回答 1

1

您不太可能让某人Branch and Bound为您实施该算法。但是，下面的 stackoverflow 帖子TSP - branch and bound有一些指向一些有用资源的链接：

  1. Optimal Solution for TSP using Branch and Bound
  2. B&B Implementations for the TSP- 第 1 部分：一个解决方案，其节点包含带约束的部分游览
  3. B&B Implementations for the TSP- 第 2 部分：具有许多廉价节点的单线程解决方案

由于您似乎是 perl 新手，我们可以给您一些快速提示

  1. 始终在每个 perl 脚本的顶部包含use strict;和use warnings
  2. range operator ..在创建递增for循环时使用。
  3. 您的while循环实际上应该是一个if语句。
  4. 为了增加样式，请考虑qw()在初始化混合的单词/数字数组时使用，特别是因为它可以让您轻松对齐多维数组的元素
  5. 对于这样的项目，您的第一个目标应该是创建一种以可读格式输出多维数组的方法，以便您可以观察和验证所做的更改。

所有这些都带来了以下变化：

use strict;
use warnings;

my @verwbez = (
    [qw(-  B  E  G  I  K  L  P  S )],
    [qw(B  -  10 10 2  10 10 10 10)],
    [qw(E  10 -  2  10 10 10 1  10)],
    [qw(G  10 2  -  10 2  3  3  3 )],
    [qw(I  2  10 10 -  4  10 10 2 )],
    [qw(K  10 10 2  4  -  10 10 3 )],
    [qw(L  10 10 3  10 10 -  2  2 )],
    [qw(P  10 1  3  10 10 2  -  10)],
    [qw(S  10 10 3  2  3  2  10 - )],
); 

for my $i (0 .. $#verwbez) {
    for my $j (0 .. $#{$verwbez[$i]}) {
        if ($verwbez[$i][$j] =~ /\d/ && $verwbez[$i][$j] >= 7) {
            $verwbez[$i][$j] = ".";
        }
    }
}

for (@verwbez) {
    for (@$_) {
        printf "%2s ", $_;
    }
    print "\n";
}

输出：

 -  B  E  G  I  K  L  P  S
 B  -  .  .  2  .  .  .  .
 E  .  -  2  .  .  .  1  .
 G  .  2  -  .  2  3  3  3
 I  2  .  .  -  4  .  .  2
 K  .  .  2  4  -  .  .  3
 L  .  .  3  .  .  -  2  2
 P  .  1  3  .  .  2  -  .
 S  .  .  3  2  3  2  .  -

请注意，B 只有 1 个靠近它的城市。因此，如果目标是解决 TSP，那么就没有简单的解决方案。但是，鉴于只有 8 个城市和 (n-1)！循环排列。这给了我们 5,040 个排列，所以使用蛮力完全可以找到成本最低的解决方案。

use strict;
use warnings;

use Algorithm::Combinatorics qw(circular_permutations);

my @verwbez = ( ... already defined ... ); 

# Create a cost between two cities hash:
my %cost;
for my $i (1..$#verwbez) {
    for my $j (1..$#{$verwbez[$i]}) {
        $cost{ $verwbez[$i][0] }{ $verwbez[0][$j] } = $verwbez[$i][$j] if $i != $j;
    }
}

# Determine all Routes and their cost (sorted)
my @cities = keys %cost;
my @perms = circular_permutations(\@cities);
my @cost_with_perm = sort {$a->[0] <=> $b->[0]} map {
    my $perm = $_;
    my $prev = $perm->[-1];
    my $cost = 0;
    for (@$perm) {
        $cost += $cost{$_}{$prev};
        $prev = $_
    }
    [$cost, $perm]
} @perms;

# Print out lowest cost routes:
print "Lowest cost is: " . $cost_with_perm[0][0] . "\n";
for (@cost_with_perm) {
    last if $_->[0] > $cost_with_perm[0][0];
    print join(' ', @{$_->[1]}), "\n";
}

最终，这种设置只有 2 个成本最低的解决方案，它们是彼此的镜像，这是有道理的，因为我们没有在循环排列中按方向过滤。我故意不说明他们在这里是什么。

于 2014-03-26T07:36:10.073 回答