end0tknr's kipple - web写経開発

太宰府天満宮の狛犬って、妙にカワイイ

javascript の toLocaleString() による 数値(Number)や日付(Date)の文字列書式変換

「数値を3桁毎に",“で区切る」場合や「日付をYY/MM/DD形式に変換する」場合、 正規表現 + jquery.template で対応していましたが、 Number.prototype.toLocaleString() や、Date.prototype.toLocaleString() があるらしいので、写経。

※ただし、safariで未対応だったり、ie / chrome / firefox で出力結果が 異なる等の注意は必要です。

参考url

最初に、developer.mozilla.org にある仕様を読むことをお勧めすます

toLocaleString()の仕様

developer.mozilla.org

developer.mozilla.org

localeや通貨の一覧

end0tknr.hateblo.jp

使用例

JavaScriptのtoLocaleStringメソッドについて調べてみた | while(isプログラマ)

オレオレ使用例

<!DOCTYPE html>
<html lang="ja">
  <head>
    <meta charset="utf-8">
  </head>
  <body>
    <button onClick="num_to_local_string();">Number.toLocaleString()</button>
    <button onClick="date_to_local_string();">Date.toLocaleString()</button>
    <br>
  </body>
  <script>
   function num_to_local_string(){
     //通貨形式
     alert( (1234.56789).toLocaleString("ja-JP",
                      {style: 'currency',
                   currency: 'JPY' }) );
     //数値形式、小数第5位で丸め
     alert( (1234.56789).toLocaleString("ja-JP",
                      {style: 'decimal',
                   minimumFractionDigits:4}) );
     //パーセント形式
     alert( (0.015).toLocaleString("ja-JP",
                  {style: 'percent'}) );
   }

   function date_to_local_string(){
     var date = new Date();

     alert( date.toLocaleString("ja-JP",
               {hour12:true,       //AM/PMを表示
                "year":"numeric",  //2桁で表示
                "month":"2-digit", //曜日を表示
                "day":  "2-digit",
                "weekday":"short",
                "hour":  "2-digit",
                "minute":"2-digit",
                "second":"2-digit",
                }) );
   }

</script>
</html>

最短経路探索アルゴリズムの A* (A-STAR)を perlで試す

「A*」を聞いたことはありますが、実装したことはない為、写経。

今回の写経で、2次元の最短経路探索は理解できた気がするので、次は3次元? 立体? 経路探索に発展させたい。

参考にさせて頂いたurl

A*アルゴリズムは1968年に発表された為、インターネット上に多くの情報がありますが、 私には次のurlが分かりやすかった。

A*の動作を視覚的に理解しやすいGIGAZINE

gigazine.net

しっかり?と定義が記載されているwikipedia

https://ja.wikipedia.org/wiki/A*

pythonのsrcもコメントも分かりやすい pashango_p

d.hatena.ne.jp

今回は、上記 pashango_p の python → perl写経

以下は、perlで記載していますが、申し訳ない程、pashango_p さんのsrcのまんま

#!/usr/local/bin/perl
use strict;
use warnings;
use utf8;
use List::Util;
use Data::Dumper;

my $MAP_DATA =
    ['OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO',
     'OS  O     O     O         O          O',
     'O   O  O  O  O  O         O    OOOO GO',
     'O      O     O  O   OOOO  O    O  OOOO',
     'OO OOOOOOOOOOOOOOO  O     O    O     O',
     'O                O  O     O          O',
     'O        OOO     O  O     OOOOOOOOO  O',
     'O  OO    O    OOOO  O     O      OO  O',
     'O   O    O          O     O  O   O   O',
     'O   OOO  O          O        O   O   O',
     'O        O          O        O       O',
     'OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO'];
my $MAP_WIDTH  = List::Util::max(map { length($_) } @$MAP_DATA);
my $MAP_HEIGHT = scalar(@$MAP_DATA);
my $START_POS = [];
my $GOAL_POS  = [];
my $MAX_SEEK_LOOP = 5000;

main();

sub main {

    #スタート位置とゴール位置を設定
    my $y = 0;
    for my $map_line ( @$MAP_DATA ){
        my $str_index = index($map_line,"S");
        if( $str_index >=0 ){
            $START_POS = [$str_index,$y];
        }
        $str_index = index($map_line,"G");
        if( $str_index >=0 ){
            $GOAL_POS = [$str_index,$y];
        }
        $y++;
    }

    #OpenリストとCloseリストを設定
    my $open_list     = NodeList->new();
    my $close_list    = NodeList->new();

    my $start_node    = Node->new( @$START_POS );
    $start_node->{fs} = $start_node->{hs};
    
    $open_list->append($start_node);

    my $i = 0;
    my $end_node;
    while(1){
        if( $i++ > $MAX_SEEK_LOOP){  #もしもの為のfail safe
            print "You reached MAX_SEEK_LOOP = $MAX_SEEK_LOOP \n";
            return;
        }

        #Openリストが空になったら解なし
        if( scalar(@{$open_list->{node_list}}) == 0 ){
            print "There is no route until reaching a goal.\n";
            return;
        }

        #Openリストからf*が最少のノードnを取得
        my ($n)= sort {$a->{fs}<=>$b->{fs}} @{$open_list->{node_list}};
        $open_list->remove($n);
        $close_list->append($n);

        if( $n->is_goal() ){ #最小ノードがゴールだったら終了
            $end_node = $n;
            last;
        }

        #f*() = g*() + h*() -> g*() = f*() - h*()
        my $n_gs = $n->{fs} - $n->{hs};

        #ノードnの移動可能方向のノードを調べる
        for my $v ([1,0],[-1,0],[0,1],[0,-1]){
            my $x = $n->{pos}->[0] + $v->[0];
            my $y = $n->{pos}->[1] + $v->[1];

            #マップが範囲外または壁(O)の場合はcontinue
            if($y< 0 or $MAP_HEIGHT < $y or
               $x< 0 or $MAP_WIDTH  < $x or
               substr($MAP_DATA->[$y],$x,1) eq 'O'){
                next;
            }

            #移動先のノードがOpen,Closeのどちらのリストに
            #格納されているか、または新規ノードなのかを調べる
            my $m = $open_list->find($x,$y);
            my $dist = ($n->{pos}->[0] - $x)**2 + ($n->{pos}->[1] - $y)**2;

            if ($m){
                #移動先のノードがOpenリストに格納されていた場合、
                #より小さいf*ならばノードmのf*を更新し、親を書き換え
                if( $m->{fs} > ($n_gs + $m->{hs} + $dist)){
                    $m->{fs} = $n_gs + $m->{hs} + $dist;
                    $m->{parent_node} = $n;
                }
            } else {
                $m = $close_list->find($x,$y);
                if($m){
                    #移動先のノードがCloseリストに格納されていた場合、
                    #より小さいf*ならばノードmのf*を更新し、親を書き換え
                    #かつ、Openリストに移動する
                    if($m->{fs} > $n_gs + $m->{hs} + $dist){
                        $m->{fs} = $n_gs + $m->{hs} + $dist;
                        $m->{parent_node} = $n;
                        $open_list->append($m);
                        $close_list->remove($m);
                    }
                } else {
                    #新規ノードならばOpenリストにノードに追加
                    $m = Node->new($x,$y);
                    $m->{fs} = $n_gs + $m->{hs} + $dist;
                    $m->{parent_node} = $n;
                    $open_list->append($m);
                }
            }
        }
    }

    #endノードから親を辿っていくと、最短ルートを示す
    my $m = [];
    for my $line ( @$MAP_DATA ){
        my @cols = split(//, $line);
        push(@$m,\@cols);
    }

    my $n = $end_node->{parent_node};
    
    while(1){
        last if not $n->{parent_node};
        $m->[$n->{pos}->[1]]->[$n->{pos}->[0]] = '+';
        $n = $n->{parent_node};
    }

    for my $cols ( @$m ){
        print join('', @$cols),"\n";
    }
}


package Node;  ########

sub new {
    my ($class, $x, $y) = @_;

    my $self = {};
    $self =  bless $self, $class;
    $self->{pos} = [$x, $y];
    $self->{hs}  = ($x-$GOAL_POS->[0])**2 + ($y-$GOAL_POS->[1])**2;
    $self->{fs}  = 0; ## なんで?

    $self->{owner_list} =  [];
    $self->{parent_node} = '';

    return $self;
}

sub is_goal {
    my ($self) = @_;
    if($self->{pos}->[0] == $GOAL_POS->[0] and
       $self->{pos}->[1] == $GOAL_POS->[1]){
        return $self; # means true
    }
    return; # means false
}


package NodeList; ########
use Data::Dumper;

sub new {
    my ($class) = @_;
    my $self = {};
    $self =  bless $self, $class;
    $self->{node_list} = [];
    return $self;
}

sub append {
    my ($self, $node_obj) = @_;

    if( defined($node_obj) and ref($node_obj) eq "Node" ){
        push( @{$self->{node_list}}, $node_obj);
        return;
    }
}

sub find {
    my ($self, $x, $y) = @_;

    for my $node_obj ( @{$self->{node_list}} ){
        if($node_obj->{pos}->[0] == $x and
           $node_obj->{pos}->[1] == $y ){
            return $node_obj;
        }
    }
    return;
}

sub remove {
    my ($self, $target_node_obj) = @_;

    my $i = 0;
    for my $node_obj ( @{$self->{node_list}} ){
        if($node_obj->{pos}->[0] == $target_node_obj->{pos}->[0] and
           $node_obj->{pos}->[1] == $target_node_obj->{pos}->[1] ){
            splice(@{$self->{node_list}},$i,1);
            return $self;
        }
        $i++;
    }
    return;
}

1;
__END__

↑こう書くと、↓こう動きます

$ ./a_star.pl
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OS+ O     O     O         O   +++++++O
O + O  O  O  O  O  +++++++O   +OOOO GO
O +    O     O  O  +OOOO +O   +O  OOOO
OO+OOOOOOOOOOOOOOO +O    +O   +O     O
O ++++++++++++   O +O    +O   ++++++ O
O        OOO +   O +O    +OOOOOOOOO+ O
O  OO    O   +OOOO +O    +O +++++OO+ O
O   O    O   +++++++O    +O +O  +O++ O
O   OOO  O          O    ++++O  +O+  O
O        O          O        O  +++  O
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

FSM (有限ステートマシン) からの behavior tree

先日の FSM / ステートパターン のエントリで扱った例を behavior tree で実装しようと考えていましたが、 behavior treeで扱うには、その例が簡単すぎたみたい。

end0tknr.hateblo.jp

なので、 behavior tree の簡単なまとめだけを記載しておきます。

決定木( decision tree )と異なり、 Sequence(AND)やSelector(OR)等の多様なノードがある点で、 behavior tree の方が多機能ですね。

unreal engineでは、behavior tree のguiなエディタがあるみたいですけど、 同様の問題はprologでも解けそうですね。

参考url

niconare.nicovideo.jp

www.slideshare.net

代表的なノード

f:id:end0tknr:20170701105532p:plain

サンプル

f:id:end0tknr:20170701114612p:plain

f:id:end0tknr:20170701114614p:plain

behavior tree の長所/短所

  • ◯ 状態管理は複雑になってもFSMより管理が簡単
  • ◯ 全体像を見渡せる
  • × 全てのノードを探索する場合があり、CPU負荷:高

Re: 旋回しながら追いかける動き（操舵行動 / 追跡 = Steering Behaviors / Seek）

操舵行動って、オライリーの「実例で学ぶゲームAIプログラミング」に記載されていたものですね。

p5.js は、利用したことありませんが、分かりやすい!!

qiita.com

ちなみに「実例で学ぶゲームAIプログラミング」では、操舵行動の中で - 探索(Seek) - 逃走(Flee) - 到着(Arrive) - 追跡(Pursuit) - 逃避(Evade) - 徘徊(Wander) - 障害物回避(ObstancleAvoidance) - 壁回避(WallAvoidance) - 介入(Interpose) - 隠身(Hide) - 経路追従(FollowPath) - オフセット追跡(OffsetPursuit) を具体的なコード付で紹介しています

GoFのステートパターンの振り返り ( ≒ FSM ? )

有限ステートマシン(FSM)を実装しようと思ったら、そもそも理解できていなかったようですので、GoFデザインパターンを振り返り

参考にさせて頂いたurl

私が探した範囲では、次のurlが分かりやすいように思えます。 また、このエントリの内容も、このurlの写経です。

labo.mamezou.com

ヒーターをサンプルに利用

f:id:end0tknr:20170626104708p:plain

f:id:end0tknr:20170626104714p:plain

これの GoFステートチャート

以下の通り f:id:end0tknr:20170626104730p:plain

これの クラス図

以下の通り f:id:end0tknr:20170626104746p:plain

historyやサブ状態を有するステートパターンは次回

以下は、気が向いたら… f:id:end0tknr:20170626104757p:plain

DBI for perl でのトランザクション管理は、begin_work, commit, rollback

$dbh->{AutoCommit} と紹介しているところもありますが…

http://search.cpan.org/perldoc?DBI

↑こちらに記載されている通り、基本は、 $dbh->begin_work, $dbh->commit, $dbh->rollback　。

↓gihyo.jpにも同様に記載されています。

gihyo.jp

線形代数 : 行列式とサラスの公式、そしてクラメル式によるn元1次連立方程式の解

「1次連立方程式の解」について「掃き出し法」は知ってましたが、 「クラメル式」は知らなかった(or すっかり忘れてた)のでメモ。

2次行列の行列式

{\bf{A}} = \left( \begin{array}{cc} {a} & {b} \\\ {c} & {d} \end{array} \right)

について、 \displaystyle \left| \bf{A} \right| = ad - bc

3次行列の行列式 (サラスの公式、4次以上もOK)

\displaystyle \left| \bf{A} \right| = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{13}a_{22}a_{31} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33}

f:id:end0tknr:20170617090330p:plain

クラメル式によるn元1次連立方程式の解

\displaystyle \left( \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\\ a_{21} & a_{22} & \cdots & a_{2n} \\\ \vdots & \vdots & \ddots & \vdots \\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array} \right) \left( \begin{array}{c} x_{1} \\\ x_{2} \\\ \vdots \\\ x_{n} \end{array} \right) = \left( \begin{array}{c} b_{1} \\\ b_{2} \\\ \vdots \\\ b_{n} \end{array} \right)

\displaystyle \left| \bf{A} \right| ≠ 0 のとき、上記の解は次のように行列式により算出できる。

\displaystyle \underline{ x_i = \frac { \left| \bf{A_i} \right| }{ \left| \bf{A} \right| } } 　ただし、i = 1～n。 また、Aiは、次のようにi列目をbに置換したもの

\displaystyle \left| \bf{A_i} \right| = \left| \begin{array}{cccccc} a_{11} & a_{12} & \cdots & b_{1} & \cdots & a_{1n} \\\ a_{21} & a_{22} & \cdots & b_{2} & \cdots & a_{2n} \\\ \vdots & \vdots & \ddots & \vdots & & \vdots \\\ a_{n1} & a_{n2} & \cdots & b_{n} & \cdots & a_{nn} \end{array} \right|

線形代数 : 空間座標における直線式と平面式

直線

点A(x1, y1, z1)を通り、方向ベクトル:dの場合

\displaystyle \underline{ \bf{p} = \bf{a} + t \cdot \bf{d} }

ただし、 { \bf{p} = \left( \begin{array}{c} x \\ y \\ z \end{array} \right) } 、 { \bf{a} = \vec{OA} = \left( \begin{array}{c} x_1 \\ y_1 \\ z_1 \end{array} \right) } 、t は媒介変数、 { \bf{d} = \left( \begin{array}{c} l \\ m \\ n \end{array} \right) }

l≠0 m≠0 n≠0 のとき

\displaystyle \frac{x - x_1}{l} = \frac{y - y_1}{m} = \frac{z - z_1}{n}

平面

点A(x1, y1, z1)を通り、ベクトル:d1, d2 を張る場合

\displaystyle \underline{ \bf{p} = \bf{a} + s \cdot \bf{d_1} + t \cdot \bf{d_2} }

ただし、 { \bf{p} = \left( \begin{array}{c} x \\ y \\ z \end{array} \right) } 、 { \bf{a} = \vec{OA} = \left( \begin{array}{c} x_1 \\ y_1 \\ z_1 \end{array} \right) } 、s , t は媒介変数、 { \bf{d_1} = \left( \begin{array}{c} l_1 \\ m_1 \\ n_1 \end{array} \right) } 、 { \bf{d_2} = \left( \begin{array}{c} l_2 \\ m_2 \\ n_2 \end{array} \right) }

また、点Aを通り、法線ベクトル: h =(a b c)の場合

\displaystyle \underline{ a \cdot (x - x_1) + b \cdot (y - y_1) + c \cdot (z - z_1) = 0}

回帰分析における寄与率(=決定係数)と、残差や相関係数との関係

先程のエントリにも記載していますが、 「寄与率」は回帰分析にもあり、それを混同していたので、再整理。

f:id:end0tknr:20170521193847g:plain

寄与率(=決定係数) の定義式

総平方和： S_T = \sum_{i=1}^{n} (y_{i} - \overline{y} )^{2}

ここで、 y_{i} は実測値で、 \overline{y} は実測値の総平均。

残差平方和： S_E = \sum_{i=1}^{n} (y_{i} - \hat{y_{i}} )^{2}

ここで、 \hat{y} はモデル値(予測値)。

これらを用いて、寄与率(=決定係数)は次のように定義されています。

寄与率(決定係数)： R^{2} = \frac{ S_T - S_E }{ S_T }

また、上記の「回帰による平方和」を利用し、次のように表すことが可能です。

回帰による平方和： S_R = \sum_{i=1}^{n} (\hat{y_{i}} - y_{i})^{2}
寄与率(決定係数)： R^{2} = \frac{ S_R }{ S_T } = \frac{ S_T - S_E }{ S_T } = 1 - \frac{S_E}{S_T}

寄与率(=決定係数) は、なぜ Rの2乗で表すか?

相関係数であるRと、寄与率(=決定係数)の間に2乗の関係があることが理由のようです。

更に…自由度修正済み寄与率

先程、記載した寄与率は説明変数が増える程、上昇するらしい。 (実際の説明力の有無に関らず、寄与率が増加…)

そこで「自由度」を考慮し修正した「自由度修正済み寄与率」があるらしい。(以下)

自由度修正済み寄与率( R^{2} ) ： R^{2} = 1 - \frac{ \frac{残差の平方和}{残差の自由度} } { \frac{総平方和}{ n - 1} }

ただし、 n=データ数、残差の自由度 = データ数(n) - 説明変数の数 - 1

寄与度/寄与率 : データ全体(合計)の"変化"に対する各構成要素の貢献度

寄与度の定義

「全体の"変化"に対する」がポイントで、 年度の総売上額に対する部門Aの寄与度/寄与率は次式で算出できます。

部門Aのt年の寄与度 = \frac{ 部門Aのt年売上 - 部門Aの(t-1)年売上 }{ (t-1)年総売上額 } \\\ 　または　 { 部門Aのt年成長率 \cdot 部門Aの(t-1)年構成比率 }
部門Aのt年の寄与率 = \frac{ 部門Aのt年寄与度 }{ 総額のt年成長率 }

例題

例として、年度の総売上額に対する部門A～Cの寄与度/寄与率を算出します。

年度 部門A 部門B 部門C 総額
2011 500 300 200 1000
2012 600 300 400 1300
2013 800 500 300 1600
2014 1000 600 400 2000

年度毎の変化

まず、上記の表から年度毎の変化を整理します

年度<-前年 部門A 部門B 部門C 総額
2012<-2011 100 0 200 300
2013<-2012 200 200 -100 300
2014<-2013 200 100 100 400

寄与度

次に寄与度を算出しますが、 例えば、部門Aの2012年寄与度は「(600-500)/1000 = 0.1」です。 他部門や他年度も同様に寄与度を計算すると次のようになります。

年度<-前年 部門A 部門B 部門C
2012<-2011 0.10 0.0 0.20
2013<-2012 0.15 0.15 -0.08
2014<-2013 0.13 0.06 0.06

寄与率

まず、総額成長率( (t年売上 - (t-1)年売上) / (t-1)年売上 )を算出します。

年度<-前年 総額成長率
2012<-2011 0.30
2013<-2012 0.23
2014<-2013 0.25

寄与率は「部門の寄与度」と「総額の成長率」により算出され、 例えば部門Aの2012年寄与率は、0.1x0.3=0.03となります。 他部門や他年度も同様に寄与率を計算すると次のようになります。

年度<-前年 部門A 部門B 部門C
2012<-2011 0.03 0.0 0.06
2013<-2012 0.03 0.03 -0.02
2014<-2013 0.03 0.02 0.02

固有値、固有ベクトル

主成分分析に利用する為、おさらい。

その他、シュレーディンガー方程式(量子力学)、マルコフ連鎖、グラフ理論 でも利用されるらしいが、対角行列に変換できることに関係するのかな?、まっ、今回は単なるおさらいなので、気にしませんが

定義

n次正方行列Aに対し、 A \textbf{x} = \lambda \textbf{x} が成立するとき、定数:λを「固有値」、 ベクトル \textbf{x} を「固有ベクトル」

固有値、固有ベクトル の算出例

\left( \begin{array}{cc} 8 , 1 \\ 4 , 5 \end{array} \right) の固有値、固有ベクトルを算出する。

まず、 \left| A - \lambda E \right| = 0 の行列式を解き、固有値を求める。

\left| \begin{array}{cc} {8 - \lambda} & {1} \\\ {4} & {5 - \lambda} \end{array} \right| = 0
(8 - \lambda)(5 - \lambda) - 4 = 0
\lambda^{2} - 13 \lambda + 36 = 0
\underline{ \lambda = 4 , 9 }

次に λ = 4 , 9 に対応するそれぞれの固有ベクトルを求める。

まずは「λ = 4」の場合

\left( \begin{array}{cc} {8 - 4} & {1} \\\ {4} & {5 - 4} \end{array} \right) \left( \begin{array}{c} x_1 \\\ x_2 \end{array} \right) = 0
\left( \begin{array}{cc} {4} & {1} \\\ {4} & {1} \end{array} \right) \left( \begin{array}{c} x_1 \\\ x_2 \end{array} \right) = 0
4 x_{1} + x_{2} = 0

よって、「λ = 4」に対応する固有ベクトルは t \left( \begin{array}{c} {1} \\ {-4} \end{array} \right) 　※ただし、tは0以外の任意数。

次に「λ = 9」の場合

\left( \begin{array}{cc} {8 - 9} & {1} \\\ {4} & {5 - 9} \end{array} \right) \left( \begin{array}{c} x_1 \\\ x_2 \end{array} \right) = 0
\left( \begin{array}{cc} {-1} & {1} \\\ {4} & {-4} \end{array} \right) \left( \begin{array}{c} x_1 \\\ x_2 \end{array} \right) = 0
\begin{cases} - x_{1} + x_{2} = 0 \\\ 4 x_{1} -4 x_{2} = 0 \end{cases}

よって、「λ = 9」に対応する固有ベクトルは t \left( \begin{array}{c} {1} \\ {1} \end{array} \right) 　※ただし、tは0以外の任意数。