最短経路問題

Programming Perl

人工無脳の発言生成を最短経路問題と見なして、ほうほうこれはなかなかいけそうなモデルじゃねーかなと思った。しかしどーもそこから次の段階へと思考が至らない。そうだ。そもそも最短経路問題をうまく解けねえよ俺。
参考ページ

眠い。

ねむい。

一番上のページは参考になる。超簡単なコードでも書いてみようと試みた。まったく途中までしかやってないけど眠いから書いておく。

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

my $route = {
  bos => {
    'こんばんは' => 20,
    'こんにちは' => 10,
    cost => 0,
    route => '',
    decision => 1,
  },
  'こんにちは' => {
    'こんばんは' => 5,
  },
  'こんばんは' => {
    eos => 5,
},
};
sub dijkstra{
  my($pos, $route) = @_;
  return if($pos eq 'eos');
  my ($minnode, $mynode, $mycost);
  for $mynode(keys %{$route->{$pos}}){
    next if($mynode eq 'cost'||$mynode eq 'route'||$mynode eq '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' eq $pos)&&' '||$pos);
    }
    $mycost = $route->{$mynode}{cost};
    $minnode = $mynode if(!defined$minnode || $route->{$minnode}{cost} > $mycost);
  }
  $route->{$minnode}{decision} = 1;
  dijkstra($minnode, $route);
}
dijkstra('bos', $route);

print Dumper($route);

出力

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

これはたまたま求める結果になってるけど、本当にたまたまだろうな。まだダイクストラ法の解説最後まで読んでねえし。漠然とした理解はしてるけどたぶん適当。

つーか今気付いたが、なんかループで書ける関数は末尾再帰で書く癖が付いてるなあ。まったく意識せずに書いてた。CとかPerlなんかの場合はむしろループで書くのがスタンダードだったりするんじゃなかろか。あと、なんかなんとなくすげー読みにくいコードな気がする。冗長ぽい。あと眠い。

俺がいつか普通程度にまともなプログラミング能力を身につけたなら、きっとこういういいかげんなコードは恥ずかしくて人に見せられなくなるだろうな。まあしかしずっとこの辺あたりをウロウロしつづけるんじゃねーかなという気もしている。

test