多分木の通りがけ順探索

Question

多分木を、通りがけ順で探索した際、その探索順序はどのようになるでしょうか？

定義から考えると、２分木以外の場合が全くわからず困っています

上の図の場合において、探索順序とその説明をお願いします

そもそも２分木以上の場合通りがけ順は定義されないとしているサイト（wiki）まで

あったので愚問かもしれませんがよろしくお願いいたします

Answer 1

こんにちは。

Wikipediaによると、「行きがけ順、通りがけ順、帰りがけ順探索はすべて深さ優先探索の特殊な例である。」ということですので、深さ優先探索で考えます。(なお、同じ分岐にぶら下がる各枝の探索順序は実装依存です。)

0→1→3→1→0→2→4→2→5→2→6→7→6→2→0

同じノードを複数回アクセスします。先に訪れた時に主な処理を行うのか、後に訪れた方で主な処理を行うのかにより、行きがけ順と帰りがけ順が異なるようです。
Wikipediaの記述を見る限り、通りかけ順は子から子への通りかかりの時に主な処理を行うようですね。

しかし、３分岐以上あったら、子から子への通りかかりが2回以上あるので、通りかけ順の定義は難しそうです。
上記ケースで4→2→5の時に主な処理を行うのか5→2→6の時に行うのかの話です。
2分岐(2分木)なら、子から子への通りかかりは1回だけなので定義不要ですね。

---

【余談ですが】
深さ優先探索(Depth First Search)はチェス的なゲームのAIプログラムでよく用いられます。私も昔オセロで使いました。
昔は、行きかけとか帰りかけとか特に気にせず、α-β枝刈りとかやってましたね。これは帰りかけ順になりそうです。

Answer 2

「一意に定まらず定義されない」というのも、それが答えだと思いますよ。まあ、考えうるパターンを例示しても良いですね。

この手の「解釈の余地」がある課題は早急に議題に挙げたほうがいいですよ。私の出身大学の研究室は「答えが一意に定まらない課題」をテーマとしているところがありました。まあ、これ自体は問題はないのですが、「学外の民間企業からお金を貰う際に『解釈の意味を切り替え、自己の主張の優位性を示す』」ということをやっているように見えました。

自分も携わりましたが、この手続きの過程を先方に相談したら教官や企業担当者を踏まえての会議となり、担当者は怒って去っていきました。要するに「後だしジャンケン」とか「消せるボールペン」と同一原理です。結果を見てから都合の良いものを選択し、「これを最初から計画していた」と主張するようなものです。

ちなみに、上記の研究テーマについて述べますと、「メタヒューリスティクスの悪用」といった感じのものでした。（ここでは「アルゴリズム」のタグがあるので、閲覧者には馴染みがあると思います。）