Location : Home > Languages > Perl > Package
Title : AI::Menu
 		Toolbox Logo

名称

　AI::Menu

概要

use AI::Menu;

my $factory = new AI::Menu::Factory;

my $menu = $factory->generate($hash_of_functions);
my $menu = $factory->generate($hash_of_functions, $hash_of_categories);
my $menu = $factory->generate($graph);

説明

　AI::Menu::Factory オブジェクトは Tree::Nary objects from 有向グラフ（Graph::Directed|Graph::Directed または同様のメソッド）から Tree::Nary オブジェクトまたは関数の集合の記述を生成する。
　アルゴリズムは大して効率的ではない。F を関数の数としておよそ O(F^6) の計算量である。十分にインテリジェントなものでもない。繰り返し計算するのではなく、結果をキャッシュすべきである。
　アルゴリズムが最適化されるか、より効率的なアルゴリズムが発見されれば実装される。ツリーを生成するインタフェースは頻繁に変更されるべきではない。結果のオブジェクトは AI::Menu|AI::Menu オブジェクトに含まれた Tree::Nary|Tree::Nary オブジェクトになる。

メソッド

　（generateを除く）以下の全てのメソッドは AI::Menu::Factory オブジェクトを生成する際に new 関数内で利用可能である。

generate

　この関数はツリーを生成する設定可能なモジュールを予備だs前に準備を行う。
　単一のハッシュ参照と呼び出された場合、そのハッシュはカテゴリーのリストを含む配列参照への関数マッピングのリストと見なされる。さらに関数名とカテゴリー名の集合は互い共通部分を持たないものとする。閉包は引数がハッシュ参照内のキーであれば ture を返す関数 leaf_q のために生成される。完全グラフはこの単一ハッシュ参照から生成される。カテゴリーがある関数を通じて他のカテゴリーに到達可能なら２つのカテゴリーの間に端（edge）が挿入される。この端は双方向である。
　２つのハッシュ参照と呼び出された場合、最初のハッシュは先と同様に扱われるが、２つめのハッシュ参照はカテゴリーに対するカテゴリーのマッピングと見なされる。この２つめのハッシュは自動的に最初のハッシュから情報を取得する替わりに使用される。
　ハッシュ参照でない単一オブジェクトと呼び出された場合、引数はグラフオブジェクト（たいていは Graph::Directed|Graph::Directed）と見なされる。leaf_q 関数が定義のために必要である。

leaf_q

　この関数は引数が関数（グラフの中の葉 leaf）であれば ture を返す。引数がカテゴリーであれば false を返す。AI::Menu::Factory オブジェクトが生成されたときまたはメソッドが呼び出されたときに設定される。引数がなければ現在の関数を返す。

maker

　グラフからメニューを生成するために用いる。以下のように使う。

my $menu = $self -> {maker} -> new(
    width => $self->{width},
    weight_f => $self -> {weight_f},
    leaf_q => $leafq,
);

return $menu -> generate_tree($g, $optscore);

　$optscore の値は最適ツリーのスコアである。ツリーがこの値に行き着けば探索は終了する。

new

　AI::Menu::Factory オブジェクトを生成する。generate 及び new を除くメソッドのリストからなるキー／値の組をオプションの引数としてとる。

weight_f

　この関数はグラフ中の端の重みを計算する際に用いられる。次の４つの引数をとる：ツリーを生成するオブジェクト・グラフオブジェクト・始点となる頂点・終点となる頂点。この関数は無限の重みをとると undef を返す。

width

　これは結節点ごとの子結節点の数を指定する。最適（かつデフォルト）値は 3 である。

使用例

　以下の例は関数のリストからメニューを生成し、LaTeX を用いて結果のツリーを出力する例を示す。

my $factory = AI::Menu::Factory;

my $functions = {
   a => [qw: A B D :],
   b => [qw: C D E :],
   c => [qw: A B C :],
   d => [qw: E G H :],
   e => [qw: A C E :],
   f => [qw: A D F :],
};

$menu = $factory -> generate($functions);

# 以下は Tree::Nary の test.pl から拝借
sub node_build_string() {
   my ($node, $ref_of_arg) = (shift, shift);
   my $p = $ref_of_arg;
   my $string;
   my $c = $node->{data};

   if(defined($p)) {
      $string = $$p;
   } else {
      $string = "";
   }
   
   if($node -> is_leaf($node)) {
      $c = "\\leaf{\\mbox{ $c }}\n";
   } else {
      $c = "\\branch{" . $node -> n_children( $node ) . "}{$c}\n";
   }
   
   $string .= $c;
   $$p = $string;
   
   return($Tree::Nary::FALSE);
}
 
my $string;

$menu -> traverse( $menu,  
                   $Tree::Nary::POST_ORDER,
                   $Tree::Nary::TRAVERSE_ALL, -1,
                   \&node_build_string, \$string);

print "$string\n";

　上記のコードは以下の結果を出力する。


 \leaf{\mbox{ a }}
 \leaf{\mbox{ c }}
 \branch{2}{B}
 \leaf{\mbox{ b }}
 \leaf{\mbox{ d }}
 \leaf{\mbox{ e }}
 \branch{3}{C}
 \leaf{\mbox{ f }}
 \branch{3}{A}

　これは以下のツリーを意味している。

    A
 /  |  \
f   C   B
   /|\  |\
  b d e c a

バグ

　最適スコアが１つに固定されている。これは全ての可能性を時間を追って計算していることを示す。任意の $width パラメータをもつツリーに対する最適スコアへ関数の数をマッピングするアルゴリズムが必要である。
　アルゴリズムは非効率的に見えるが、どれくらい高速になれば効率的と言えるのかは分からない。この分野でやるべきことがいくつか残っている。
　ツリーは少し奇妙かも知れない。実際、そうだ。結果は学術的なものであるべきだし、この点で示唆が必要である。もし興味深い関数とカテゴリーの集合があれば知らせて欲しい。
　アルゴリズムは他のものよりも重要なカテゴリーを作成する方法を必要としている。

参考資料

　Graph::Directed, Tree::Nary

著者

　James Smith, <jgsmith@jamesmith.com>

著作権

　Copyright (C) 2001 Texas A&M University. All Rights Reserved.

　本ライブラリはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。

Toolbox Logo
 Updated : 2006/12/22