ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » 2分木の応用(意思決定木と演算子)

2分木の応用(意思決定木と演算子)

投稿者: in 情報構造論, 斉藤徹, 講義録 投稿日:

2分探索木はO(log N)で検索するためのデータ構造だけど、それ以外にも枝構造のデータ構造は活用される。ここで2分探索木以外の木のデータ構造について解説を行う。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

   ((意思決定木の例:小さい子供が発熱した時))
　　　　　　　38.5℃以上の発熱がある？
　　　　　　no／　　　　　　　　　＼yes
　　　元気がある？　　　　　　　　むねがひいひい？
　yes／　　　　＼no　　　　　　no／　　　　　＼yes
様子をみる　　　　　　氷枕で病院　　　　　　　　　解熱剤で病院　　　　　　　　速攻で病院

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じである。左右に枝のあるものは質問であり、yesの枝もnoの枝もない末端は最終決断を表す。このようなデータ構造は意思決定木と呼ばれ、質問と決断の処理は以下のように記述ができる。枝があれば質問として表示し、枝がなければ結果として表示する…という処理を yes/no に応じて枝を進んでいけばいい。

import java.util.* ;
import java.util.Scanner ;

class TreeNode {
    String qa ;
    TreeNode    yes ;
    TreeNode    no ;
    
    TreeNode( String s , TreeNode y , TreeNode n ) {
        this.qa  = s ;
        this.yes = y ;
        this.no  = n ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner( System.in ) ;
        // 意思決定木を生成
        TreeNode top =
            new TreeNode( "38.5℃以上の発熱がある?" ,
                          new TreeNode( "胸がひぃひぃ?" ,
                                        new TreeNode( "速攻で病院" ,   null , null ) ,
                                        new TreeNode( "解熱剤で病院" , null , null ) ) ,
                          new TreeNode( "元気がある?" ,
                                        new TreeNode( "様子をみる",    null , null ) ,
                                        new TreeNode( "氷枕で病院",    null , null ) ) ) ;
        // 判断を進める処理
        TreeNode p = top ;
        while( p.yes != null || p.no != null ) {
            System.out.println( "Question:" + p.qa ) ;
            if ( sc.nextInt() == 1 ) {
                System.out.println( "yes" ) ;
                p = p.yes ;
            } else {
                System.out.println( "no" ) ;
                p = p.no ;
            }
        }
        // 枝がなければ結論として表示して終了
        System.out.println( "Answer:" + p.qa ) ;
    }
}

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
                    struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ?" ,
                    dtree( "速攻で病院",  NULL,NULL ) ,
                    dtree( "解熱剤で病院",NULL,NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる",  NULL,NULL ) ,
                    dtree( "氷枕で病院",  NULL,NULL ) ) ) ;
   // 決定木をたどる
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scanf( "%d" , &ans ) ;
      // 回答に応じてyes/noの枝に進む。
      if ( ans == 1 )      // yesを選択
         d = d->yes ;
      else if ( ans == 0 ) // noを選択
         d = d->no ;
   }
   // 最終決定を表示
   printf( "%s¥n" , d->qa ) ;
}

2分木の応用として式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。

逆ポーランド記法

一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。

演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+　　# 1と「2と3をかけた値」をたす。

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式をコンピュータで実行する際の処理と似ている。(RPN電卓のおはなし)

演算子の右結合・左結合

例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？ (演算子の優先順位と結合規則)

一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。

ただしC言語やJavaでは、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

以下の式を指定された書き方で表現せよ。

逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。
中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

逆ポーランド記法とスタックマシン

逆ポーランド記法(RPN)は、(1+2)*3 であれば “1 2 + 3 *” のように表すことができ、この書き方は「1と2を加える、(それに)3を掛ける」というように、日本語で表現するのに向いている。また、計算のデータを準備してから計算するという流れにも沿っていて、計算手順を表すのに向いている。

プログラミング言語でコンパイラでは、計算式に応じて機械語命令を生成するが、この計算手順にそって機械語を生成すればいい。

      ;; (1+2)*3 をレジスタマシンの機械語っぽく書いてみる
      LD   GR0 , 1
      LD   GR1 , 2
      ADD  GR0 , GR1
      LD   GR1 , 3
      MUL  GR0 , GR1

RPNで書かれた式は、スタックを使うと、そのまま計算式を計算することができる。
逆ポーランド記法の式を先頭から処理するとして、以下の処理を繰り返せばいい。

  1. 数値データの場合は stack に push する。
  2. 演算子の場合は stack から2つ値を pop で取り出して、計算結果を stack に push する。
import java.util.*;

public class Main {
    public static int[] stack = new int[ 10 ] ;
    public static int sp = 0 ;
    public static void push( int x ) {
        stack[ sp++ ] = x ;
    }
    public static int pop() {
        return stack[ --sp ] ;
    }
    public static int rpn( String s ) {
        for( int i = 0 ; i < s.length() ; i++ ) {
            char c = s.charAt( i ) ;
            if ( c >= '0' && c <= '9' ) { // 1桁の数字
                push( c - '0' ) ;
            } else if ( c == '+' ) {
                int r = pop() ;
                int l = pop() ;
                push( l + r ) ;  // push( pop() + pop() ) と書かないのはなぜ?
            } else if ( c == '*' ) {
                int r = pop() ;
                int l = pop() ;
                push( l * r ) ;
            }
        }
        return pop() ;
    }
    public static void main(String[] args) throws Exception {
        System.out.println( rpn( "12+3*" ) ) ; // (1+2)*3
        System.out.println( rpn( "123*+" ) ) ; // 1+2*3
    }
}
// スタック上の変化
1,2,3,*,+     1,2,+,3,*
    3
  2 2 6         2   3
1 1 1 1 7     1 1 3 3 9

スタックに計算結果を保存し,スタック上の値に対する計算で処理が行われるシステムは、スタックマシンと呼ぶ。(Java のバイトコードや WebAssembly の機械語)

これに対し、一般的な CPU ではレジスタを基本とした演算命令であり、レジスタマシンと呼ばれる。