ホーム » スタッフ » 斉藤徹 » 2分木の応用/意思決定木

2012年10月
« 9月   11月 »
 123456
78910111213
14151617181920
21222324252627
28293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2分木の応用/意思決定木

今日は、前回の演習時間も不足だと思われるので、前半に座学・後半演習とした。

意思決定木

雑誌の占いや性格判断みたいなページには、質問に対して"yes","no"の回答をしてもらって、 最終的にあなたの性格は!みたいなのがよく書かれている。こういうようなものは、

       |
      勉強好き?  
     /     \
もっと勉強?     部活好き? 
 / \       / \
大学 技術者 アスリート 心配!

意思決定木と呼ばれる。このデータ構造では、ノードに質問事項が書かれ、 木の末端のノードには、最終的な答えが記載される。 これをプログラムで表すならば、

struct DTree {
char *mess ;
struct DTree* yes ;
struct DTree* no ;
} ;
struct DTree* dtcons( char* s ,
struct DTree* y ,
struct DTree* n )
{
struct DTree* ret ;
ret = (struct DTree*)malloc( sizeof( struct DTree ) ) ;
if ( ret != NULL ) {
ret->mess = s ;
ret->yes  = y ;
ret->no   = n ;
}
return ret ;
}
struct DTree* top =
dtcons( "勉強好き?" ,
dtcons( "もっと勉強?" ,
dtcons( "大学" , NULL , NULL ) ,
dtcons( "技術者" , NULL , NULL ) ) ,
dtcons( "部活好き?" ,
dtcons( "アスリート" , NULL , NULL ) ,
dtcons( "心配..." , NULL , NULL ) ) ) ;
void main() {
char buff[ 100 ] ;
struct DTree* p = top ;
while( p->yes != NULL || p->no != NULL ) {
printf( "%s" , p->mess ) ;
scanf( "%s" , buff ) ;
if ( strcmp( buff , "yes" ) == 0 )
p = p->yes ;
else
p = p->no ;
}
printf( "%s" , p->mess ) ;
}