Q&A
「そうした結果幾つのグループ」と「経路数」はイコールなのですか？
機械学習に関連した質問です。
以下のような問いを考えます。
問い「任意の迷路を10×10マスの範囲で与えた時、プログラムによってその迷路の経路数を答えさせるにはどのようなプログラムを組めば良いか？
スタート位置座標、ゴールの位置座標、壁の位置座標をコンピューターに与えるものとする。」
僕の最初の着想はこうでした。
つまり、ランダムに進んでゆくコマに迷路を進ませて、ゴールにたどり着いた時に、そのコマの経路を記憶してゆきます。こうして経路の情報を蓄積してゆき、互いに似た特徴（ここが難しいのですが・・・）を持ったものを類別してゆく。そうした結果幾つのグループができるか、で経路数を弾きだすというものです。
試しに、自作した迷路について、ゴールにたどり着くまでの経路の長さを記録するプログラムを書いてみました。以下がそのコードです。
経路の長さを記録する
上のプログラムにおいて、プログラムがとっている迷路の経路数は直感的には「２」ですが、それは別に経路の長さと相関は持ちません。
この場合、経路の長さから経路数を割り出すことは難しい。
では何の情報を分析して経路数を割り出すようにプログラムするのが合理的なのか？
なかなか難しそうです。
ご助言あれば、お待ちしています。
回答ありがとうございます。
イコールであることが望ましいことは言うまでもないのですが、現状を考えると、あまり贅沢は言えないような気がします・・・・。
少なくとも「ある特徴」によって意味のあるグループ分けができれば、前進と考えていいのではないでしょうか。
質問文中のプログラムの実行結果を見て気になったのですが、経路には上下左右の移動の他に、斜め45度の移動も含みますか？
回答ありがとうございます。
含みます。自分の周り八マスをランダムに選んで進むようにプログラムを組んでいます。
ただ、ここでの目的は、経路数を求めることなので、必ずしもその進み方が必要なわけではないのです。
サンプルとして、以下のような進み方を想定しています。
https://jsfiddle.net/justmeet0924/jhkynus9/10/show/
[与えられたマップ・スタート位置・ゴール位置]に対して、自滅せずにゴールに至るまでの重複しない経路数を、"厳密に"算出することが目的なのですか？
もしそうであれば、特にランダムに進ませる必要はない気がしますが、なぜランダムが出てくるのでしょうか。
（スタート地点から順番に、とりうるマスを選択し、記録していった方が効率的ではないかと思いますが）
それとも厳密な経路数を求める必要はなく、ある程度の量の「ゴールまでの経路情報」を取得できれば十分なのでしょうか。
そもそも、そのような経路数や経路情報を取得した先に、何か「別の目的」があるのでしょうか。
目的は、例えば上のサンプルプログラムの地図であれば、「３」をコンピューターに答えさせることがおそらく目的になります。
つまり、雑多な経路情報から、「本質的に」イコールであるものを類別していって、（言い方を変えれば、これとこれは「同じ」という判断をプログラムにさせて）その結果そのグループ数を答えさせたい、というのが質問の趣旨です。
ご指摘の通り、全ての経路を算出する、というのでもOKです。
本質的な部分は得られた経路情報をいかに分析するか、というところにあります。
ランダムに算出することで、そうした場合に取り得る経路の偏りが出るのか、といった情報を得られるなどの利点もあり、質問文中のサンプルプログラムを書いてみました。
ありがとうございます。なんとなく質問者さんの意図が理解できたような気がします。
ただ、現時点に提示されているコメントや内容だけだと、"経路が「本質的に同じ」とする判断基準"が明確に示されておらず、なかなか難しいような気もします。
（それ自体を、回答者にゆだねているのかもしれませんが)
参考にお聞きしたいのですが、質問者さんはどのような観点から経路グループを分析／分類し、「３個」という結論になったのでしょうか。
ありがとうございます。
お察ししてくださった通り、「本質的に同じ」の定義の部分が議論の主要なポイントになっています。
これがクリアーに定まらないからこそ、この問題に論じる価値があるのだと思います。
３個の経路についてですか・・・・。難しいですね。人間の目で見ると、「違う」ことが明確な場合でも、コンピューターがわかる基準に言い直そうとすると、非常に煩雑になる。
３個の経路については、何かが決定的に違うような気がするのです・・・・。
理論的に正しいかはわかりませんが、たとえば下記のようなアプローチはいかがでしょうか。
（１）計算量軽量化のため、分類の基準となるデータの取得は、マップの縦横50%の範囲におけるルートとする（それ以降の部分は切り捨てる）（たとえばスタートが真ん中にある場合は、そのスタートを中心とする縦横50%の範囲）（スタートが左上にある場合は、スタートを左上隅とする縦横50%の範囲）
（２）スタートマスから各ステージで移動するマスについて、移動前の位置に対して左上から右下までをA～Hまでの文字列で表し、移動ごとに、これを追記する。
（例：５ｘ５の場合、「HHHHH」（右下一直線） というルートや、「EEEEGGGG」（右に4マス、下に4マス）というルートが有り得る）
（３）（２）で得られた経路を表す文字列群について、各々ベクトル化し、K-means法等でクラスタリングする。
例）HHHHHとHHHHEGは類似度が高く同じグループ、 「EEEEGGGG」と「EEEGEGGG」は同じグループ
※（１）はたとえば計算量を気にしないならば全ルートでもよいでしょうし、「スタートから最初の10マス」でもよいかもしれません。
質問文中のコードに出てきた迷路について、私の勝手な想像で経路を「3種類」に分類するなら、
1. 右に5マス→下に3マス およびそれに類似した経路
2. 下に9マス→右に9マス→上に2マス→左に5マス→上に4マス→右に1マス およびそれに類似した経路
3. 右に2マス→下に9マス→右に7マス→上に2マス→左に5マス→上に4マス→右に1マス およびそれに類似した経路
となりますが、これをどう分類するかということですかね。
回答1件
0
自己解決
数学的には、経路問題はホモトピー同値、の概念で説明できそうです。
ホモトピー同値とは、Aという経路を連続的に変化させていって、それをBに変えられるとき、AとBはホモトピー同値である、という風に定義されます。
この問題の場合、経路Aと経路Bを比較する際に、それらをつなぎ合わせたスタート地点を含む閉回路を作り、その閉回路の内部に、壁が含まれると、AからBへの連続的な変化が阻まれるので、AとBはホモトピー同値ではない、ということになります。
また、経路数は、おそらく外壁と接していない、孤立した壁の数で決定されそうです。
質問文中の地図で言うと、孤立した壁の数は「２」です。
投稿2021/12/06 02:20
総合スコア44
あなたの回答
tips
プレビュー
