2種類の探索方法

Breadth-First Search or Depth-First Search

---

以前の投稿でMinimal Searchについて見た. これはミニマリストプログラムで提唱されるラベリングを行う際のラベルの探索操作である. この探索はシンプルに表現すれば, 発生しうる木構造を順次探索していき, そのラベルを決定するものと言える. しかし, 冷静に考えてみると, この木構造の探索ルートは1種類ではないことに気づく.

代表的なものとして, 幅優先探索(Breadth-First Search)と深さ優先探索(Depth-First Search)という2つがある (これはコンピュータサイエンスと関連がある発想である).

幅優先探索(Breadth-First Search)はその名前の通り, 幅を優先するためより深い探索を行う前に, 開始時点の階層のすべてのノードを探索する. 他方で深さ優先探索(Depth-First Search)はその名前の通り, 深さを優先するため, 同じ階層に別のノードがあったとしても, それは一旦無視し, さらに深い階層へ探索を進めていく.

これらはそれぞれ一長一短があり, 人間の言語が仮にこのMinimal Searchを採用している場合, どちらの方法でアルゴリズムを決定しているかは, さらに検討の余地があるだろう.

参考文献

• Ke, A. H. (2024). Can Agree and Labeling Be Reduced to Minimal Search?. Linguistic Inquiry, 55(4), 849-870.