2015年6月30日火曜日

Boost libraryのBuild (Windows8) (64bit版対応修正)

今度コンパイルしようと思っているライブラリ(GTSAM)にBoostが必要なので、準備した。

1.Boostライブラリのダウンロード&展開
公式ページにいって、ダウンロードする。この記事の時点では、1.58.0だったので、最新版をダウンロード。展開は、c:/dev/boost に展開とする。まぁ、どこでもいい。

2.コマンドプロンプトを立ち上げる。
Windows Keyをおして、commandと打ち込むとコマンドプロンプトのアイコンが出てくるので起動。

3.展開したフォルダに移動。
command prompt では cd コマンドを使って移動しましょう。

4.bootstrap.batを起動
bootstrap.bat
と入力します。結構待ちます。

5.コンパイル&インストール
./b2 install -j2 --prefix=(インストールしたいディレクトリ)
上のコマンドでは32bit版が出来上がり、後で苦労します。そのため、64bit用のコマンドに変更します。
b2 toolset=msvc threading=multi variant=debug,release link=shared runtime-link=shared address-model=64 --stagedir=stage/x64 -j 8
この後には、インストールしたいディレクトリの元のstageにLibファイルが出来上がっています。

ちなみに、j2はマルチスレッドでコンパイルするという意味なのでCPUのコア数にしましょう。

6.環境変数に追加
5でできたStageのフォルダにパスを通しましょう。

終わりです。

参考:
http://qiita.com/softgate/items/75f123f01ccdee6d36d0

Boost libraryのBuild (Windows8)

今度コンパイルしようと思っているライブラリ(GTSAM)にBoostが必要なので、準備した。

1.Boostライブラリのダウンロード&展開
公式ページにいって、ダウンロードする。この記事の時点では、1.58.0だったので、最新版をダウンロード。展開は、c:/dev/boost に展開とする。まぁ、どこでもいい。

2.コマンドプロンプトを立ち上げる。
Windows Keyをおして、commandと打ち込むとコマンドプロンプトのアイコンが出てくるので起動。

3.展開したフォルダに移動。
command prompt では cd コマンドを使って移動しましょう。

4.bootstrap.batを起動
bootstrap.bat
と入力します。結構待ちます。

5.コンパイル&インストール
./b2 install -j2 --prefix=(インストールしたいディレクトリ)
この後には、インストールしたいディレクトリの元のstageにLibファイルが出来上がっています。

6.環境変数に追加
5でできたStageのフォルダにパスを通しましょう。

終わりです。

OpenGL 取得した画像をOpenCVで処理してOpenGLで表示する。

内部でSimulationをするために、OpenGLでレンダリングし、その画像を取得しOpenCVで処理することを考えた。まぁ、一般的だと思う。そのためには、

1.OpenGLから画像情報の取得
画像情報の取得には3つ方法がある。
・OpenGLで画像を表示させ、glReadPixels を使って画像情報を取得
・ビデオメモリからWindowの画像情報を取得
・オフスクリーンレンダリング
・ダブルバッファから画像情報の取得
下の3つはまだ試していないので今後にやったらご紹介するとして、1つ目が一番簡単なのでその手法を採用した。

仮のコード(double bufferを使うコードから取得)
cv::Mat ReadDisplay;

glutSwapBuffers();
glReadPixels(0, 0, WIDTH, HEIGHT, GL_BGR_EXT, GL_UNSIGNED_BYTE, ReadDisplay.data);

2.画像を上下反転
OpenGLの座標系のY軸は上向きが正。OpenCVの座標系のY軸は下向きが正(左上が原点)。これを変換する必要がある。

cv::flip(ReadDisplay, ReadDisplay, 0);

3.なんか処理する。
特徴点抽出でもやりましょう。でも、本題でないため細かくは略します。ほしかったら連絡ください。
detector = new ORB(80, 1.25f, 4, 7, 0, 2, 0, 7);
detector->detect(img1, keypoints);
cv::drawKeypoints(img1, keypoints, output);

4.OpenCV 色の変更
なぜだかわからないけど、OpenCVはBGR らしい。そのため、BGRから RGB変更しましょう。

cv::cvtColor(output, output, CV_BGR2RGB);

これをやらないとセピア色になります。

5. 画像を上下反転
OpenGLで表示するために、また画像を上下反転します。

cv::flip(output, output, 0);

6.OpenGLのテクスチャに張り付けて、GLのWindowに画像を表示する。
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glOrtho(0.0, WIDTH, HEIGHT, 0.0, -1.0, 1.0);

glEnable(GL_TEXTURE_2D);//テクスチャ有効
//glBindTexture(GL_TEXTURE_2D, img.data);

/* テクスチャ画像はバイト単位に詰め込まれている */
glPixelStorei(GL_UNPACK_ALIGNMENT, 1);
/* テクスチャの割り当て */
glTexImage2D(GL_TEXTURE_2D, 0, 3, img.cols, img.rows, 0, GL_RGB, GL_UNSIGNED_BYTE, img.data);
/* テクスチャを拡大・縮小する方法の指定 */
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);

glEnable(GL_ALPHA_TEST);//アルファテスト開始
glBegin(GL_POLYGON);
glTexCoord2f(0.0f, 0.0f); glVertex2d(0, HEIGHT);//左下
glTexCoord2f(0.0f, 1.0f); glVertex2d(0, 0);//左上
glTexCoord2f(1.0f, 1.0f); glVertex2d(WIDTH, 0);//右上
glTexCoord2f(1.0f, 0.0f); glVertex2d(WIDTH, HEIGHT);//右下
glEnd();
glDisable(GL_ALPHA_TEST);//アルファテスト終了
glDisable(GL_TEXTURE_2D);//テクスチャ無効

glutSwapBuffers();

参考:
OpenGL描画→OpenCV処理→ピクチャボックス描画
http://ameblo.jp/morimoridiary/theme-10081830227.html
C++/CLI フォームアプリとOpenCVの連携(cv::Mat)
http://ameblo.jp/morimoridiary/entry-11879119909.html
【1. OpenGL画像をOpenCV画像(cv::Mat)に変換】
http://ameblo.jp/morimoridiary/entry-11879119909.html
Kinect for Windows SDKによる3次元ポイントクラウド
http://kassymemo.blogspot.com/2012/04/kinect-for-windows-sdk3.html
http://whoopsidaisies.hatenablog.com/entry/2014/08/20/200215

3Dファイルフォーマットの種類

以下のリンクからの頂き物です。



OBJ 

Wavefront OBJ形式.
  • 多くの3Dモデリング,レンダリングソフトが対応している.
  • 拡張子 : obj
  • ASCII
  • OBJ形式

3DS 

Autodesk 3D Studio(現在は3ds Max)用の形式.
  • シーン,モデリング,アニメーションなど多くのデータを扱える.
  • 多くの3Dモデリング,レンダリングソフトが対応している.
  • 拡張子 : 3ds, max
  • バイナリ
  • ID(2バイト),サイズ(4バイト),データで構成されるチャンクと呼ばれるデータ単位で記述される.チャンクは入れ子構造にできて,子チャンク,孫チャンクなどが存在する.
  • 読込/書込用のライブラリとして,lib3ds (オープンソースソフトウェア (LGPL)) がある.
  • The Labs.com - The Unofficial 3DStudio 3DS File Format
  • Wikipedia - .3ds

VRML 

Web上で使用することを前提に設計された形式
  • Virtual Reality Modeling Language
  • シーン,モデリング,アニメーションなどに加えて他のVRMLファイルへのリンクURLも記述できる.
  • 拡張子 : wrl
  • ASCII
  • Web3Dコンソーシアム

X3D 

VRMLの後継ファイル形式
  • XMLを用いて3Dシーンやオブジェクトを表現できるオープンな形式
  • 拡張子 : x3dv, x3d, x3db
  • ASCII
  • 対応ソフト : Blender
  • Web3Dコンソーシアム

DXF 

Autodesk AutoCAD用のファイル形式.
  • CGソフトだけでなくCAD系ソフトにも対応が多い形式(CAD図面の事実上の標準形式)
  • 拡張子 : dxf
  • ASCII & バイナリ
  • 仕様書
  • CAD用でもあり年々様々なデータに対応していっている.全てに対応した入出力ライブラリを作るのは大変だが, 3Dモデルだけで良いならば,ENTITIESセクションの3DFACEエンティティのみに対応していればOK.
  • 3DFACEだけに対応したDXFファイル入力ライブラリは3Dモデルファイルの入出力を参照.

STL 

3D System社の3D CADソフト用のファイル形式.
  • Standard Triangulated Language
  • 三次元形状を三角形ポリゴン(facet)の集合で表す.
  • 標準ではfacetのみの単純な構造なので,コーディングは楽.
  • 拡張子 : stl
  • ASCII,バイナリ
  • Wikipedia - STL

POV 

POV-Ray(Persistence Of Vision Raytracer)用のファイル形式
  • POV-Rayでレンダリングするシーンを記述する.
  • 拡張子 : pov, inc
  • ASCII
  • POV-Ray

COLLADA 

CGソフト間でデータをやり取りするための交換用ファイル形式
  • COLLAborative Design Activity
  • 元々はSonyがPS3,PSP用に作成した形式
  • Ver1.4よりPhysicsサポートが追加された(Bullet, ODE, PhysXなどが対応)
  • 拡張子 : dae
  • KHRONOSのCOLLADAのぺージ

FBX 

Alias社(Autodeskが買収)がオープンソースとして策定したファイル形式
  • SDKが公開されている.
  • 拡張子 : fbx
  • バイナリ
  • Autodesk FBX

LWO 

NetTek LightWave3D用のファイル形式

PLY 

Stanford Universityが公開しているレンジデータを元にしたメッシュを格納したフォーマット.
  • 拡張子 : ply
  • ASCII
  • The Stanford 3D Scanning Repository
  • 上記URLから,CG分野で有名なモデルをダウンロードできる(Stanford Bunny, Happy Buddha,
  • 対応ソフト : Blender

OFF 

Object File Format.Princeton shape benchmark で使われている.

XSI 

SoftImage XSI(現Autodesk SoftImage)社のモデリングソフトウェアSoftImage用のファイル形式

AC3D 

Inivis社の3D CG モデリング,デザインソフトウェアAC3D用のファイル形式.

C3D 

主にモーションキャプチャデータの格納,配布に用いられているフォーマット

BVH 

C3Dと同様に主にモーションキャプチャデータの格納,配布に用いられているフォーマット

2015年6月28日日曜日

OpenCVのインストール (Windows 8 & Visual Studio 2013)

OpenCVはVersionが3.0系が出ている。2系との違いは下記HPがわかりやすかったので、そちらを参照。
OpenCV3.0.0-alphaの特徴抽出・マッチングまとめ

結果、大きな違いの一つは特徴点抽出のインターフェースが違うことみたいだ。私の場合、基本からやりたかったので、最初から(追加をいれなくても)SIFTやSURFが使える2.4.10にした。以降、2.4.9を前提にインストールの手順を進める。

1.OpenCV公式パッケージの入手とインストール
公式ページからダウンロード。今回は、2.4.10。
展開する。展開場所はどこでもよいが、参考したページに従い、C:\dev\ にした。
パスにスペースが入ると動かいソフトもあるので、これがよいだろう。

2.環境変数に追加
C:\dev\opencv-2.4.10\opencv\build\x64\vc12\bin
ちゃんと追加されているか確認するために、commandを立ち上げて、「opencv_traincascade.exe」とでも打ち込み、エラーが表示されなければよいだろう。上手くいけば、引数が足りないといわれヘルプがでるだけ。

3.Visual Studio Project ファイルの設定
・インクルードパス
ソリューションエクスプローラーのプロジェクト名を右クリックし、プロパティを立ち上げる。
構成プロパティ->C/C++
 追加のインクルードディレクトリに下記を追加
 C:\dev\opencv-2.4.10\opencv\build\include

・ライブラリパス
ソリューションエクスプローラーのプロジェクト名を右クリックし、プロパティを立ち上げる。
構成プロパティ->リンカー
 追加のライブラリディレクトリに下記を追加
 C:\dev\opencv-2.4.10\opencv\build\x64\vc12\lib

・使用ライブラリの指定
ソリューションエクスプローラーのプロジェクト名を右クリックし、プロパティを立ち上げる。
構成をDebug若しくはReleaseにして、構成プロパティ->リンカー->入力
 追加の依存に下記を追加(下はDebugの時)
opencv_core2410d.lib
opencv_highgui2410d.lib
何のライブラリが必要かは、下の表見てね。(OpenCV入門(1)より)
(まぁ、cmakeを使えば勝手に集めてくれるが、執筆時点Cmakeが上手く動いてくれないので、直接入れている。)

モジュール名ライブラリ名(OpenCV 3.0)概要
coreopencv_core300.lib画像・行列データ構造の提供、配列操作、図形描画、XMLおよびYAML入出力、コマンドラインパーサー、ユーティリティ機能など
imgprocopencv_imgproc300.libフィルター処理、アフィン変換、エッジ検出、ハフ検出、色変換、ヒストグラム計算、ラベリングなど
calib3dopencv_calib3d300.libカメラキャリブレーション、ステレオ対応点探索
features2dopencv_features2d300.lib特徴点抽出(ORB、BRISK、FREAKなど)
highguiopencv_highgui2d300.libGUI(ウィンドウ表示、画像ファイル、動画ファイルの入出力、カメラキャプチャなど)
mlopencv_ml300.libSVM、決定木、ブースティング、ニューラルネットワークなど
cudaopencv_cuda300.lib画像処理のCUDA(GPGPU)実装
objdetectopencv_objdetect300.libオブジェクト検出(顔検出、人体検出など)
photoopencv_photo300.lib画像修復、ノイズ除去処理、HDR(High Dynamic Range)合成、画像合成など
shapeopencv_shape300.lib形状マッチング
stitchingopencv_stitching300.libパノラマ合成
superresopencv_superres300.lib超解像処理
videoopencv_video300.libオプティカルフロー、カルマンフィルタ、背景差分など
vizopencv_viz300.lib3Dデータの可視化(内部的にVTKを使用)
nonfreeopencv_nonfree300.lib一部の国で特許が取得されている、もしくは使用に制限がある可能性があるアルゴリズム(SIFT、SURF)
                                   主要モジュールとその機能概要

注意:Debugでやっているときは *d.libが必要となるので注意。Releaseのときはdがつかないやつを追加。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
教訓
最初は最新版が使いたくてVisual Studio 2015で挑戦していたが、どうしてもうまくいかない。どこが上手くいかないかというと、コンパイルは通るのだが、実際に動かす段階でDLLの参照(特徴点抽出)でエラーがでる。どうやら、原因は2つ。
1.Visual Studio 2013 と 2015のc++のコンパイラは異なる。
2.OpenCVは異なるコンパイラから生成されたDLLを用いると、使う関数(これ重要)によってはエラーがでる。最低限動かすだけならでないこともある。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
参考:
OpenCVのインストール
http://www.buildinsider.net/small/opencv/02

2015年6月24日水曜日

新たな戦闘教義「群(Swarm)」の実現に向けた実験

この分野は、Vijayさんのところのニュースが多いなー
http://hiah.minibird.jp/?p=1790

同じく無人機関係のニュースですが、こちらは別枠で紹介したいと思います。自動運転する無人ボート13隻を「群」としてコントロールした実験です。実験は8月に行われたとのこと。
なぜこのニュースに注目したかというと、無人機の群制御は新たな戦争の「教義」となる可能性があるためです。戦闘教義とは、作戦や戦闘における軍部隊の運用思想を言います。例えばヒトラーの「電撃戦」や、第二次大戦での「艦船に対する航空攻撃」は、その時代の新たな戦闘教義として威力を誇りました。
無人機の最先端動向をレポートした『ロボット兵士の戦争』(2010)では、ドローンの普及に伴い研究されている新たな戦闘教義として、「母艦」と「群」を挙げています。このうち「群(Swarm)」は、低コストな無人機を大量に準備し、群れとして強大な攻撃力を持たせるという思想です。
無人ボートの実験は、米軍の「群」教義の進捗を知るうえで気になるニュースでした。無人機の群行動については次の記事も参考になります。

頻発するドローンの異常接近と、法規制

面白い記事があったので、一部抜粋
http://hiah.minibird.jp/?p=1790

ドローンが注目を集めており、この3ヶ月でもドローンに関するニュースがたくさんありました。ちょっと3ヶ月のニュースをまとめてみたいと思います。
まずこの3ヶ月で目立っていたのが、ドローンによる事故や、ドローンを利用した事件です。ドローンの空中衝突等は以前から問題視されていますが、この3ヶ月はとくに目立っていたように思います。まだ大事件には至っていないようですが‥。
ドローンに対する法整備は進められているようですが、まだ時間がかかりそう。
規則作りに関しては、ドローンによる配送を計画するAmazonもアプローチを行っています。ドローンを利用したサービスは以前まとめて紹介しました。どこまでのサービスや利用が実現するのか、引き続き注目です。

シルクドゥ・ソレイユのドローンを使ったパフォーマンスは必見
その他のドローン用途にまつわるニュースもタイトルを列挙。色々提案されていますね。

2015年6月23日火曜日

米海軍がテストしている「無人ボート」の群行動:(動画あり)

http://wired.jp/2014/10/21/navy-self-driving-swarmboats/

米海軍は、自律運転で群行動するボートの技術をテストしている。無人ボート13隻で行われたテストの動画を紹介。


ヴァージニア州ニューポートニューズのジェームズ川で8月に行われたテストで公開された、全長8.5mの「無人ボート」。
軍艦は、港で補給しているときや、狭い海峡や川を移動しているときに危険な状態になる。狭い場所は操舵が難しく、攻撃にさらされやすいからだ。
2000年にイエメンのアデン港で起きた米艦「コール」襲撃事件は、ミサイル駆逐艦コールが停泊・補給しているときに起きた。小型ボートが艦の左舷に接近し自爆攻撃を行ったこの襲撃では、米国の水兵17人が死亡。全長約154mのコールは左舷に12m四方の亀裂が生じ、港にいる軍艦を保護する必要性が再確認された。
こうした攻撃に対抗するため、米海軍では、小型警備艇で接近戦からの防御を行っている。しかしこれは、水兵が危険な場所にたつということだ。
そこで米海軍研究局(ONR)は、人に代わってその危険な任務に当たることができる小型「群ボート」の技術を開発することになった。
技術名はCARACaS(Control Architecture for Robotic Agent Command and Sensing)。要するに、ほぼあらゆるボートに追加設置が可能な自動操船の技術だ。
ヴァージニア州ニューポートニューズのジェームズ川で8月に行われたテストでは、CARACaS技術を搭載した複合艇(複合型ゴムボート)13隻が「重要な」船を護送し、「敵船」を包囲した。
CARACaS技術を搭載した群ボートシステムでは、人間のオペレーターが、攻撃から保護するのはどの船かをノートパソコンから群ボートに指示すると、行き先や、舵とスロットルのタイミングなどを自ら判断する。人間からの指示は、ほかの船やヘリコプター、さらには現場から遠く離れた場所からでも可能だ。
地球の裏側にいるかもしれない人間の船長と通信ができなくなったボートは、そのまま水上で停止する。
8月のテストでは、群ボートからの発砲は行われなかったが、海軍はそれを可能にする方向で進めている。もっとも、攻撃対象やタイミングの判断を群ボートのロボットに任せることはしないという。


競争優位性の維持

なかなかいい記事を見つけた。
http://gendai.ismedia.jp/articles/-/43775


AIを使った工場の最適化とかあまりやってない(日本で1社知ってけど)ので、MachineLearningの応用の手段の一つとしてよさそうだ。

工場でなくても、工業系の何かの最適化をMachineLearningでやると、他社が追いつくのに学習に時間がかかる。機械学習で最適化した事業は、もし最適化し続けられるなら、先行の優位性を保てるだろう。

たしかに、Googleが最近 GooglePhotoを無料にしたが、バックグラウンドではMachine Learningをさせ続けているとのことだ。これを続けられると、他の企業は絶対に真似できないだろうな。

競争優位性の維持に面白いアプローチがでてきたもんだ。

PCL FLANN include時のwindows7, Visula stuidoでの書き換え必要なエラー(fopen etc...)の解消法

PCLのTriangulationを使いたくて、必要なヘッダファイルをインクルードしたら、それだけでコンパイルが通らない。

原因は、使っている3rd partyソフトウェアのFLANNの中にfopenとかを使っているかららしい。VC++8.0(VisualStudio2005)以降では、セキュリティのために、CRT(Cランタイムライブラリ)のセキュリティ強化版("_s"が付いたやつ)があるからそっち使え、ってことらしい。めんどくさい・・・

その解消のための手順を記します。

1.Program files\PCL 1.7.2\3rdParty\ のアクセス権を変える。
Windows Vista/7/8/8.1では、セキュリティ強化機能として、User Account Control(略称:UAC) がサポートされているので、管理者権限が与えられているユーザーでも、一般ユーザーと同じく、フォルダに対してファイルの書き込み や更新ができません。

と、いくことでファイルを書き換える前にアクセス権を変更する必要があります。

Program files\PCL 1.7.2\3rdParty\ で右クリック プロパティを開く
セキュリティのタブを押す
「Grope or Username」で「User」を選択し、PermissionにFull Controlを与える。

参考:http://www.trycut.com/uac.htm

2.書き換える
それでは、書きかえれるようになったので書き換えていきましょう。

C:\Program Files\PCL 1.7.2\3rdParty\FLANN\include\flann\util\serialization.h
 362行
 変更前:stream_ = fopen(filename, "w");
 変更後:fopen_s(&stream_,filename, "w");
 406行
 変更前:stream_ = fopen(filename, "w");
 変更後:fopen_s(&stream_,filename, "w");
C:\Program Files\PCL 1.7.2\3rdParty\FLANN\include\flann\util\saving.h
 65行
 変更前:strcpy(signature, FLANN_SIGNATURE_);
 変更後:strcpy_s(signature, FLANN_SIGNATURE_);
 67行
 変更前:strcpy(version, FLANN_VERSION_);
 変更後:strcpy_s(signature, FLANN_SIGNATURE_);
C:\Program Files\PCL 1.7.2\3rdParty\FLANN\include\flann\util\logger.h
 66行
 変更前:stream = fopen(name,"w");
 変更後:fopen_s(&stream, name, "w");

PS:多分大丈夫だと思いますが、使用する機能を使ったわけではないので、動作は保障しません。

参考:http://blog.livedoor.jp/mrcom511/archives/51270788.html


2015年6月21日日曜日

探索アルゴリズムを視覚的に比較

非常に面白い。ためになるので掲載

http://gigazine.net/news/20150619-search-algorithm-visualize/




出発点(問題)とゴール(解)が用意された時にどのような道順で進めばいいか調べるアルゴリズムが「探索アルゴリズム」です。この探索アルゴリズムには複数の種類が存在するのですが、中でも基本的なもの8つ+ゲームデベロッパーの@shohei909さん自作のアルゴリズム2つを合わせた全10種のアルゴリズムで迷路をクリアしようとすると、どのような探索が行われることになるのかを目で見て楽しめるようにしたのが「迷路で眺める探索アルゴリズム」です。

迷路で眺める探索アルゴリズム(Search algorithm visualize) - wonderfl build flash online
http://wonderfl.net/c/hq8p

迷路で眺める探索アルゴリズム | 机上のにゅーろん
http://spheresofa.net/blog/?p=1044

これが「迷路で眺める探索アルゴリズム」。


画面上部にはこんな感じの操作メニューが敷き詰められており……


赤枠部分から探索アルゴリズムを変更可能。使用可能なアルゴリズムは深さ優先・幅優先・反復深化深さ優先・山登り優先・最良優先・間違い制限・幅優先ビーム・最良優先ビーム・優良優先・二重制限の10種類あり、画面上部からいつでも選択できます。


「new」をクリックすればいつでも迷路の形を変更可能で、「speed」を調整してアルゴリズムが迷路を探索するスピードを調整することもできます。


「start」をクリックで探索がスタート。「<<」で探索のスタート時点に戻る、「<」でひとつ前の段階に戻る、「>」でひとつあとの段階に進む、「>>」で探索の終了時点に移動。


「S」と書かれた青色のマスがスタート地点


「G」と書かれた青色のマスがゴール地点


迷路自体はこんな感じ。薄いグレーが未探索部分で、濃いグレーが探索済の部分。


赤色マスは探索で発見した分岐点あるいは行き止まり


オレンジのマスは「不要な探索」と見なされ打ち切られた「枝刈り」の分岐点・行き止まりで、赤色マスに書かれた数字はゴールに近い順番に順位を付けたもの。


探索が終了すると迷路上に白色の線でゴールまでの道のりが記されます。濃いグレー色の部分は探索済みの箇所になるので、ゴールにたどり着くためにかなり無駄な探索を行ったことが分かります。


そして、迷路下部には「分岐数」や「探索回数」が書かれており、探索回数は迷路内で移動した回数、つまりは計算時間(CPU Time)に直結。そして、分岐数は探索中に発見した赤マスの数で、メモリの使用量に直結します。


実際に「深さ優先探索」で迷路をクリアするまでの探索の様子は以下のムービーで見られます。

「迷路で眺める探索アルゴリズム」を使ってみた - YouTube


というわけで、同一の迷路を各アルゴリズムがクリアすると、クリアまでの時間や分岐数、探索範囲などがどれくらい異なってくるのか調べてみました。

深さ優先探索(Depth-first search)


分岐数:8、探索回数:803、最大分岐数:15

10個のアルゴリズムの中で最大分岐数が最大。

幅優先探索(Breadth-first search)


分岐数:7、探索回数:820、最大分岐数:9

迷路をクリアしたアルゴリズムの中で最も多くの探索回数を要した。

反復深化深さ優先探索(Iterative deeping depth-first search)


分岐数:8、探索回数:775、最大分岐数:12、深さ制限:316

山登り法(Hill climbing)


分岐数:0、探索回数:19、最大分岐数:2

唯一迷路をクリアできない探索アルゴリズム

最良優先探索(Best-first search)


分岐数:10、探索回数:411、最大分岐数:10

10種類の中でも特に探索回数が少なくて済むアルゴリズム。

間違い制限探索(Limited discrepancy search)


分岐数:11、探索回数:600、最大分岐数:12、間違い制限:10

こちらも比較的探索回数が少なめ。ただし、分岐数は迷路をクリアしたアルゴリズムの中で最大。

◆幅優先ビームサーチ(Breadth-first beam search)


分岐数:5、探索回数:682、最大分岐数:7

分岐数のみ最小。

最良優先ビームサーチ(Best-first beam search)


分岐数:5、探索回数:394、最大分岐数:6

迷路をクリアした中では探索回数・分岐数共に最小。

◆優良優先探索(good-first search)


分岐数:7、探索回数:814、最大分岐数:8

◆二重制限探索(Double limit search, Good-first beam search)


分岐数:7、探索回数:809、最大分岐数:8

探索アルゴリズムによって迷路を探索するルートはかなり異なってくるようで、迷路の形次第では探索済ゾーンの形は大きく変わってきます。なお、「迷路で眺める探索アルゴリズム」で使用されている探索アルゴリズムは迷路だけでなくパズルやソリティアなどのゲームの探索に利用可能で、手を加えればチェスやオセロのような対戦ゲームに応用することもできるそうです。