眠くなくなったから続き

Programming Perl

ちょっとはマトモになったかね。微妙。あんまり良くない。オブジェクト指向が簡単に使いやすいRubyの方が頭がすっきりするんじゃないかという気分になってきた。Ruby使ったことないけど。オブジェクト指向プログラミングしたことないけど。

use strict;
use warnings;
use Data::Dumper;
$Data::Dumper::Indent=1;

my $route = {
  bos => {
    'こんばんは' => 20,
    'こんにちは' => 10,
  },
  'こんにちは' => {
    'こんばんは' => 5,
  },
  'こんばんは' => {
    eos => 5,
},
};
sub dijkstra{
  my ($bos, $eos, $route) = @_;
  $route->{$bos}{cost} = 0;
  $route->{$bos}{route} = '';
  $route->{decision} = [$bos];

  while(!grep/$eos/,@{$route->{decision}}){
    my ($minnode, $mynode, $mycost, $pos);
    for $pos(@{$route->{decision}}){
      for $mynode(keys %{$route->{$pos}}){
        next if($mynode eq 'cost'||$mynode eq 'route'||grep/$mynode/,@{$route->{decision}});
        $mycost = $route->{$pos}{cost} + $route->{$pos}{$mynode};
        if(!defined($route->{$mynode}{cost}) || $route->{$mynode}{cost}>$mycost){
          $route->{$mynode}{cost} = $mycost;
          $route->{$mynode}{route} = $route->{$pos}{route} . (($bos ne $pos)&&$pos);
        }
        $mycost = $route->{$mynode}{cost};
        push @{$route->{decretal}}, $mynode;
        $minnode = $mynode if(!defined$minnode || $route->{$minnode}{cost} > $mycost);
      }
    }
    @{$route->{decretal}} = grep/!$minnode/, @{$route->{decretal}};
    push @{$route->{decision}}, $minnode;
  }
}
dijkstra('bos', 'eos', $route);

print Dumper($route);

$VAR1 = {
  'eos' => {
    'cost' => 20,
    'route' => 'こんにちはこんばんは'
  },
  'こんにちは' => {
    'cost' => 10,
    'route' => '',
    'こんばんは' => 5
  },
  'decretal' => [],
  'decision' => [
    'bos',
    'こんにちは',
    'こんばんは',
    'eos'
  ],
  'こんばんは' => {
    'cost' => 15,
    'eos' => 5,
    'route' => 'こんにちは'
  },
  'bos' => {
    'cost' => 0,
    'こんにちは' => 10,
    'route' => '',
    'こんばんは' => 20
  }
};

decretal orderこと仮決定ノードというものも記録させておいてるけど、別にいらないかな。decisionじゃないのは全部仮決定なんだから。undefは無限大値を示すとする。あとこれ道が全部一方通行に定義してるけど、会話プログラムの場合、特定の単語では両方向通行可能になるな。
そういえば何故か末尾再帰にしていた関数をループにした。終了条件をwhile()の中に入れてブラケットで囲むだけで書き換えれた。

test