• R/O
  • SSH
  • HTTPS

meijiro: Commit


Commit MetaInfo

Revision18 (tree)
Time2011-08-05 07:00:01
Authorkaityo

Log Message

Change dir tree

Change Summary

  • delete: help/makefile
  • delete: help/fig/linklist.gif
  • delete: help/fig/mazeex1.gif
  • delete: help/fig/mazeex2.gif
  • delete: help/fig/maze1.gif
  • delete: help/fig/maze2.gif
  • delete: help/fig/maze3.gif
  • delete: help/fig/array1.gif
  • delete: help/fig/clustering.gif
  • delete: help/fig/maze4.gif
  • delete: help/fig/array2.gif
  • delete: help/fig/array3.gif
  • delete: help/fig
  • delete: help/toc.hhc
  • delete: help/style.css
  • delete: help/mazehelp.html
  • delete: help/algorithm.html
  • delete: help/meijiro.hhp
  • delete: help/img/initmaze.gif
  • delete: help/img/open.gif
  • delete: help/img/transparent.gif
  • delete: help/img/ensmallgrid.gif
  • delete: help/img/enlargegrid.gif
  • delete: help/img/help.gif
  • delete: help/img/new.gif
  • delete: help/img/makemaze.gif
  • delete: help/img/drawanswer.gif
  • delete: help/img/save.gif
  • delete: help/img/meijiro.gif
  • delete: help/img/saveasbitmap.gif
  • delete: help/img
  • delete: help
  • added: htdocs/toc.hhc (diff)
  • added: htdocs/meijiro.hhp (diff)
  • added: htdocs/makefile (diff)

Incremental Difference

--- help/style.css (revision 17)
+++ help/style.css (nonexistent)
@@ -1,11 +0,0 @@
1-<STYLE TYPE="text/css">
2-<!--
3-html {background-color:transparent;}
4-body {line-height: 120%; background-color:#ffffd2; color: black}
5-H1 {text-align: center}
6-pre {line-height: 120% ;color: black; background: #a3ffd2;}
7-span.refer {color: gray;}
8-img {border:none;}
9-blockquote {border: solid 1px #AAAAAA;}
10--->
11-</STYLE>
--- help/mazehelp.html (revision 17)
+++ help/mazehelp.html (nonexistent)
@@ -1,152 +0,0 @@
1-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2-<html lang="ja">
3-<head>
4-<title>
5-迷次郎 ヘルプ
6-</title>
7-<style type="text/css">
8-html {background-color:transparent;}
9-body {line-height: 120%; background-color:#ffffd2; color: black}
10-H1 {text-align: center}
11-img {border:none;text-align:middle}
12-</style>
13-</head>
14-<body>
15-<H1>迷次郎 ヘルプ</H1>
16-
17-<div style="text-align:center">
18-<img src = img/meijiro.gif>
19-</div>
20-<hr>
21-<H2>はじめに</H2>
22-<P>
23- 「迷次郎」は解くと絵が浮かび上がる迷路を作ることができるツールです。
24-一筆書きの要領で絵を書くと、その絵を答えとするような迷路を作ることができます。
25-</P>
26-<ul>
27-<li> <a href="#inst">インストール/アンインストール</a>
28-<li> <a href="#howtouse">使い方</a>
29-<li> <a href="#toolbar">ツールバー</a>
30-<li> <a href="#notyet">未実装の機能</a>
31-<li> <a href="#ack">謝辞</a>
32-<li> <a href="#about">著作権/転載条件など</a>
33-<li> <a href="#history">開発履歴</a>
34-</ul>
35-<P>
36- <a href="algorithm.html">迷路作成アルゴリズムの解説</a>
37-</P>
38-
39-<hr>
40-<a name="inst"></a><H2>インストール/アンインストール</H2>
41-<P>
42- フォルダを作って、そこに書庫ファイルを展開してください。
43-レジストリを書き換えたりはしないので、アンインストールをしたいときは
44-フォルダごと消し去ってください。
45-</P>
46-<hr>
47-<H2>使い方</H2>
48-<H3>迷路作成の流れ</H3>
49-<P>
50- 本ソフトでは、以下の手順で迷路を作成します。
51-<ol>
52-<li> 迷路の大きさ、グリッドのサイズを決めます。グリッドの大きさは作成中も自由に拡大、縮小ができます。
53-<li> グレーの領域をクリックして迷路の始点を決めます。
54-<li> カーソルキーで迷路の解答を作成します。
55-<li> グレーの領域まで線を伸ばしたら、迷路作成ボタンを押して迷路を作ります。このとき、
56-最初に作った線が解答となるような迷路が作成されます。
57-<li> 気に入った迷路ができるまで、何度でも迷路を作りなおすことができます。
58-<li> 作成した迷路は独自形式のほか、ビットマップファイルとして保存することができます。
59-解答表示のオン/オフを切り替えて、問題と解答それぞれを保存しましょう。
60-<li> 迷路を作成するまで、ファイルの保存はできません。
61-</ol>
62-</P>
63-<H3>透過モード</H3>
64-<P>
65-<li> 迷路の解答を作るのに、下絵をなぞりたい場合があると思います。
66-そのとき、透過モードを使えばウィンドウが透けて、下が見えるようになります。
67-<li> 透過モードが使えるのはWindows XP以降です。
68-</P>
69-<hr>
70-<a name="toolbar"><H2>ツールバー</H2>
71-<P>
72-<ul>
73-<li> <img src=img/new.gif> 新規作成<BR>
74-サイズを指定して、新しく迷路データを作成します。
75-<li> <img src=img/open.gif> 読み込み<BR>
76-作成済みの迷路データを読み込みます。
77-<li> <img src=img/save.gif> 保存<BR>
78-作成した迷路データをファイルに保存します。
79-解答データが完成し、迷路が作成されるまで保存はできません。
80-<li> <img src=img/saveasbitmap.gif> ビットマップファイルとして保存<BR>
81-現在表示中の画像をビットマップファイルとして保存します。
82-<li> <img src=img/enlargegrid.gif> グリッド拡大<BR>
83-グリッドサイズを拡大します。
84-<li> <img src=img/ensmallgrid.gif> グリッド縮小<BR>
85-グリッドサイズを縮小します。
86-<li> <img src=img/transparent.gif> 透過ウィンドウモード<BR>
87-透過ウィンドウモードを切り替えます。
88-<li> <img src=img/makemaze.gif> 迷路作成<BR>
89-迷路を作成します。解答データが作成されるまで使用できません。
90-<li> <img src=img/initmaze.gif> 迷路の初期化<BR>
91-迷路を初期化します。「新規作成」はサイズを指定して作り直しますが、
92-「迷路の初期化」はサイズはそのままで迷路を初期化します。
93-<li> <img src=img/drawanswer.gif> 解答の表示<BR>
94-解答経路の表示・非表示を切り替えます。作成したデータを
95-ビットマップに保存する際に使用してください。
96-<li> <img src=img/help.gif> ヘルプ<BR>
97-ヘルプファイル(このファイル)を表示します。
98-</ul>
99-</P>
100-<hr>
101-<a name="notyet"><H2>未実装の機能</H2>
102-<P>
103- 以下の機能は将来つけようとは思ってますが、まだ実装されていないものです。
104-<ul>
105-<li> マウス操作による解答作成
106-<li> 始点及び終点を端以外に設定できる迷路作成アルゴリズム
107-<li> 下絵の取り込み
108-<li> 迷路の色のカスタマイズ
109-<li> EPS形式での出力
110-</ul>
111-</P>
112-<hr>
113-<a name="ack"><H2>謝辞</H2>
114-<P>
115-<ul>
116-<li> アイコン作成にたかぼーさんのEDGEというフリーソフトを使用させていただいております。
117-<li> このソフトのアイコン<img src=img/meijiro.gif>はたいやき氏に作ってもらったものです。
118-</ul>
119-<hr>
120-</P>
121-<a name="about"><H2>著作権/転載条件など</H2>
122-<P>
123-<ul>
124-<li> 開発者: H. Watanabe
125-<li> 連絡先:E-mail: <a href="m&#97;&#105;&#108;to&#58;&#107;&#97;&#105;ty&#111;&#64;&#117;sers.so&#117;rc&#101;f&#111;&#114;&#103;&#101;.j&#112;">k&#97;it&#121;o&#64;u&#115;&#101;&#114;s.&#115;&#111;ur&#99;efo&#114;ge&#46;j&#112;</a>
126-<li> このソフトはBorland C++ Builder Pro により開発されました。
127-<li> 最新版は<a href="http://meijiro.sourceforge.jp/" target=new>http://meijiro.sourceforge.jp/</a>にてダウンロードできます。
128-<li> 本ソフトウェアはフリーソフトです。本ソフトウェアを利用するにあたり、いかなる料金も請求いたしません。
129-<li> ソースファイルの利用、改変、再配布は全く自由です。雑誌掲載も自由です。
130-</ul>
131-</P>
132-<hr>
133-<a name="history"><H2>開発履歴</H2>
134-<P>
135-<ul>
136-<li> 2011/07/06 Ver 1.02 公開
137- <ul>
138- <li> 公開先をsourceforge.jpに変更。ドキュメントを修正。
139- </ul>
140-<li> 2006/08/16 Ver 1.01 公開
141- <ul>
142- <li> サンプルデータをつけた
143- <li> 迷路作成アルゴリズムの解説をつけた
144- <li> ファイル読み込み時のツールバーの不具合を修正
145- <li> ヘルプファイルの修正
146- <li> ソースファイルの公開
147- </ul>
148-<li> 2006/08/13 Ver 1.00 公開
149-</ul>
150-<hr>
151-</body>
152-</html>
--- help/algorithm.html (revision 17)
+++ help/algorithm.html (nonexistent)
@@ -1,183 +0,0 @@
1-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2-<html lang="ja">
3-<head>
4-<title>
5-クラスタリングによる迷路作成アルゴリズム
6-</title>
7-<link rel="stylesheet" href="style.css" type="text/css" />
8-</head>
9-<body>
10-
11-<H1>クラスタリングによる迷路作成アルゴリズム</H1>
12-
13-<hr>
14-<H2>はじめに</H2>
15-
16-<P>
17- クラスタリングアルゴリズムにより、解くと絵が浮かび上がる
18-迷路を作成する方法を紹介する。
19-</P>
20-
21-<hr>
22-<H2>クラスタリングとは</H2>
23-
24-<P>
25- ウェブのリンク情報や、mixiの友人関係など、ネットワークの性質を
26-知りたいことがよくある。このとき、ネットワークの性質として
27-<BLOCKQUOTE>
28-<ul>
29-<li>このネットワークにおいて任意に選んだ要素Aと要素Bはつながっているか?
30-<li>このネットワークは全体がつながっているか?
31-<li>つながっていないとしたらいくつのグループに分かれるか?
32-<li>要素数最大のグループはどれか?
33-</ul>
34-</BLOCKQUOTE>
35-などの情報が欲しくなる。このような解析をするときに
36-必要となるのがクラスタリングである。
37-</P>
38-<P>
39- クラスタリングとは、同値関係のリストが与えられたときにグループ分けを
40-することである。たとえば、
41-<BLOCKQUOTE>
42- 友達の友達は友達である
43-</BLOCKQUOTE>
44-と定義すると、友人関係は同値関係を作る。
45-その上で、
46-<ul>
47-<li> A君とB君は友達
48-<li> C君とE君は友達
49-<li> B君とD君は友達
50-</ul>
51-という情報が分かっていると、
52-この情報から、<BR>
53-<img src=fig/clustering.gif><BR>
54-という関係がわかる。このように、
55-何かと何かがつながっているという情報を処理して、
56-全体をグループわけする作業がクラスタリングである。
57-物理面での応用としては、浸透問題などの臨界現象や、
58-粉体のForce Networkなどの解析にも用いられる。
59-</P>
60-<hr>
61-<H2>アルゴリズム</H2>
62-<P>
63- クラスタリングアルゴリズムはいくつか知られているが、
64-そのうち一次元配列を使った簡単な例を紹介する。
65-</P>
66-<ul>
67-<li>すべての要素に通し番号をつける。
68-<li>要素の数だけの大きさを持った配列(A[N])を用意し、通し番号をつけておく。
69-<BR><img src=fig/array1.gif><BR><BR>
70-<li>ある二つの要素、たとえば番号2 と番号5が同じクラスタに属すと分かったら、
71-番号の大きいほうの値を小さい方(この場合は2)にする。
72-<BR><img src=fig/array2.gif><BR><BR>
73-<li>次に、5と7が等しいとしたら、7は2にあわせる。すなわち、5の属すクラスタ番号に合わせる。
74-<BR><img src=fig/array3.gif><BR><BR>
75-<li>一般的に、自分の番号からたどっていき、自分の配列番号と値が同じだったら
76-その番号を自分のクラスタ番号とする。
77-二つの要素が同じクラスタに属すとわかった場合、
78-クラスタ番号が大きいほうを小さい方に合わせる。
79-</ul>
80-<P>
81- この作業はリンクリストの作成である。
82-下図では、6つの要素からなるリンクリストが、
83-クラスタリングにより2つにグループ分けされた様子を示す。
84-最初、すべての要素のリンクは自分を指しているが、
85-クラスタリングにより、必ず番号の低い側(図では左側)にリンクされる。
86-このとき、自分からたどっていったリンクの終点の要素の番号が
87-自分のクラスタ番号となる。
88-</P>
89-<P>
90-<img src=fig/linklist.gif>
91-</P>
92-<P>
93- 以上の作業をコードで書くと以下のようになる。
94-pair1[i]とpair2[i]に同値関係が入っているとして、
95-関数clusteringを呼んでやればクラスタリングができる。
96-あとは int get_cluster_numberに要素番号を入れれば
97-その要素のクラスタ番号が返ってくるので、あとは
98-最大クラスタを探すなり、クラスタの数を数えるなりすることができる。
99-<pre>
100-//---------------------------------------------------------------------------
101-int cluster[N];
102-int pair1[N_PAIR],pair1[N_PAIR];
103-//---------------------------------------------------------------------------
104-int
105-get_cluster_number(int index){
106- int i = index;
107- while(i != cluster[i]){
108- i = cluster[i];
109- }
110- return i;
111-}
112-//---------------------------------------------------------------------------
113-void
114-clustering(void){
115- for(int i=0;i &lt; N;i++){
116- cluster[i] = i;
117- }
118- for(int i=0;i &lt; N_PAIR;i++){
119- int i1 = pair1[i];
120- int i2 = pair2[i];
121- i1 = bpma_getnumber(i1);
122- i2 = bpma_getnumber(i2);
123- if(i1 &lt; i2){
124- cluster[i2] = i1;
125- }else{
126- cluster[i1] = i2;
127- }
128- }
129-}
130-//---------------------------------------------------------------------------
131-</pre>
132-</P>
133-<hr>
134-<H2>迷路作成アルゴリズム</H2>
135-<P>
136- では、クラスタリングを迷路作成に応用してみよう。
137-迷路を作成するには、基本的には枝をつけるだけでよい。
138-しかし、適当に枝を伸ばすと、
139-「入り口からいけない場所(死に領域)ができる」
140-「ループができてしまい、解答が一意でなくなる」
141-などの問題ができてしまう。
142-そこで、クラスタリングを使って解答のパスが一意で、
143-なおかつ死に領域ができないことを保証する。
144-</P>
145-<P>
146- 迷路の作成アルゴリズムは以下の通り。
147-<ul>
148-<li> <P>部屋を要素とし、通し番号をつけておく</P>
149-<img src=fig/maze1.gif>
150-<li> <P>ランダムに壁を壊す。このとき、隣あう部屋がつながったとしてクラスタリングする</P>
151-<img src=fig/maze2.gif>
152-<li> <P>同じクラスタ番号に属す部屋の間の壁(下図の赤い線)は壊さない (<strong>ループを作らない保証</strong>)。</P>
153-<img src=fig/maze3.gif>
154-<li> <P>すべてが同じクラスタ番号に属すまで続ける(<strong>死に領域が出来ない保証</strong>)</P>
155-<img src=fig/maze4.gif>
156-</ul>
157-以上で死に領域とループがない迷路の完成である。
158-</P>
159-<hr>
160-<H2>迷路作成例</H2>
161-<P>
162- 以上のアルゴリズムを用いて、「解くと絵が浮かび上がる迷路」を
163-作ることができる。やり方は簡単で、先に解答のパスを作り、その部分だけ
164-クラスタリングしてから壁を壊し始めれば、ループを作らない保証から
165-与えた解答が最短距離となる迷路が出来上がる。
166-以下の図はそのようにして作成した迷路の例である。
167-左図の迷路を解くと、右図のような絵が浮かび上がる。
168-</P>
169-<P>
170-<img src="fig/mazeex1.gif">
171-<img src="fig/mazeex2.gif">
172-</P>
173-<hr>
174-<H2>おわりに</H2>
175-<P>
176- クラスタリングアルゴリズムを応用し、
177-「解くと絵が浮かび上がる迷路」を
178-作成してみた。クラスタリングはあらゆるネットワークの解析に使えるし、
179-コードも20行もないので知っていて損はないアルゴリズムである。
180-</P>
181-<hr>
182-</body>
183-</html>
Show on old repository browser