2004年10月28日

リストのツッコミ方と縦型探索・横型探索

bunki.bmp

図は何か分岐があるときの探索をあらわしているもの。
例えばaはホームページ,bもホームページ・・・
aからb,e,jにはリンクがあり、bからはc,dにリンクがある・・・
各ホームページのtitle調べよう!おう!

■「関数の再帰」を使う


「関数の再帰」で書くところのいいところはスッキリかけること。
基本的な流れを把握できること。
「関数の再帰」の悪いところはスタックを消費すること。スタックをいっぱい消費することが、何か、悪しきこと(もうそれ以上は動かないとか、正しい動作しないとか)を誘発します。また、もっと複雑な作業をこなそうとすると、この構造自体が足かせになる場合があります。

■同等の探索を「リストにつっこむ」ことで書く


■リストのつっこみ方と縦型・横型
「関数の再帰」を使った形だとa,b,c,d,e,f,g,h,i,j,k,l,mの順に調べることになる。これは縦型探索と呼ばれているもの。深さ優先探索とも。

上記の「リストを使って探索」もコンパチに作ったのでやはり、a,b,c,d,e,f,g,h,i,j,k,l,mの順で調べる。
リストの内容がどう変化するかを書いてみる。
(a) aを消し、b,e,jを挿入
(b,e,j)  bを消し、頭側にc,dを挿入
(c,d,e,j)
・・・・・ と続きます。

ここで新しくでてきた候補を後ろ側に挿入するように変えると
(a) aを消し、b,e,jを挿入
(b,e,j)  bを消し、後ろ側にc,dを挿入
(e,j,c,d)
・・・・・ と続きます。

結果調べる順番はa,b,d,j,e,d,f,g,k,l,h,i,mとなり横型探索と呼ばれているもの

■小谷発言「後ろに入れると横型探索」
前、小谷善行さんは「リストの前にいれると縦型探索、後ろに入れると横型探索になる。」と言ってました。以上はそれを説明したもの。その発言を聞く前から実際には自分ではそんな風にプログラムを作ってはいたのだが。「こっちは先に調べたほうがいいなぁ、こっちはあとにしようかなぁ」とリストの前後ろに振り分けたりしていた。あらためて聞いて「そうだ。そうだ」と感心した次第。

■自分の実際のプログラミング
 リストとしてはよくVC++のCListを使っている。
 STLの#include "LIST"も使えると知っているが未経験。

以上
posted by いわいまさか at 00:41| Comment(2) | TrackBack(0) | プログラミングもの | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
興味深く拝見いたしました。
私が最初に再帰っぽい処理を書いたのは、連続につながった領域の面積を求めるプログラムでした。縦型と横型の違いがわかって嬉しいです。
LISTと聞くとLISPを思い出しますが今ではLISPとはあmり縁がありません。LISTのデータ構造をSTLが提供しているのですね。
Posted by aret at 2004年11月01日 12:43
「リストにつっこむ」ところのコードをできるだけVC++のCListに合うように書き直しました。HEADにInsertAfterでなく、HEADにInsertBeforeでも縦型探索です。HEADにInsertBeforeの方が真の縦型探索なのかもしれません。
Posted by いわいまさか at 2004年11月01日 17:06
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.seesaa.jp/tb/904381

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。