ヨコ型探索

S
AD
DBC
BCEH
CEH
EH
HFG
FGIJ
GIJ
IJ

最良優先探索

候補節点の中から解の可能性が高いものを優先的に選択できるように工夫した探索法のひとつ ヒューリスティック関数h(x)をたとえば街区画距離と定義して、hの値が小さいほうがそれっぽいんじゃねとかやってみる

木構造

• 組織図、系統図のたぐい

• 二次元的な広がりを持つ階層構造

• 階層的かつ再帰的 (つまり、ある節から下をもとの木からもぎ取るとその節を根とする新しい木ができる。これをsubtreeという)

かっこ表記: Lispみたいなかっこだらけのnotation

(A
    (B
        (E)
        (F)
    )
)

度数: 節から下に出ている枝の数 葉: 末端

二分木:

定義: 二分木とは、節の有限集合であって、"空集合" XOR "根と2個の違い素な二分木とからなる" (左右の区別が可能) 二進木とはちがう 二分木は、たとえ部分木の片方が空集合でも、部分木の左右が区別できる (空集合でもとりあえず存在は認知する)

完全二分木

二分木の走査 先順、中順、後順

先順 visit(p→record); trav(p→left); trav(p→right);

chuujun trav(p→left); visit(p→record); r

atojun left right record

ポーランド記法 a*(b+c) は *a+bcと表す 木構造に書いて、横型探索を適用するとわかりやすい

逆ポーランド記法 スタック操作で実現 数字を食わせる→演算子を食わせる→直前の二項について演算が行われる→また演算子を食わせる→演算が行われる→答えが出る

もっと丁寧にノートとりたい