
最近、道順に関する組み合わせを題材にした組合せ爆発の動画が話題になっており、
それを見たのですが・・・
同じ所を2度通らない道順の組み合わせでの式がわかりません・・・
最短距離に関する組み合わせは、高校数学で習うと思うですが、最短距離でなく同じ所を2度通らない組み合わせに式など存在するのでしょうか?(画像参照)
2x2の場合、最短距離は6通りですが、2度通らない条件だと12になってしまいます。
3x3の場合、最短距離は20通りですが、2度通らない条件だと184通り
4x4の場合、最短距離は70通りですが、2度通らいない条件だと8512通りになります。
2度通らない条件での式が存在すれば、敷や解き方教えていただけないでしょうか?
もし「アルゴリズム」というものを使用しなければ回答することができなければ、アルゴリズムのさわりだけでも教えていただけると嬉しいです。
よろしくお願いします。

No.3ベストアンサー
- 回答日時:
No.2です。
動画見ました。
あの終わり方はちょっと寂しいですね。
さて、道順の数を求める方法ですが、動画でも「最先端のアルゴリズム技術」と述べていますし、
No.2で示したリンク先にも正方形の場合は数が書いてあるだけであったので、やはりアルゴリズムを使うしかないのだと思います。
そこで実際にプログラムを書いてみました。言語はVBScript(WScript)ですが、VBAでも「Call Kumiawase_Bakuhatsu」の行を削除すれば動きます。
使ったアルゴリズムですが、行けるところに行ってゴールに到達したら数えるという単純なものなのです。
なお、このプログラムで実用的に計算できるのはせいぜい5x5だと思います。
もし6以上の数を入れて計算が終わらなくなったら、VBScriptならタスクマネージャからプロセスの終了を、VBAならBreak (Ctrl + Pause)を行ってください。
Option Explicit
Dim N '1辺の点の数 兼 終点の座標
Dim No_Entry() '立入禁止地図。立入禁止(外、立入済)は1、立入可は 0
Dim Counter
Dim x_Next, y_Next '次(周囲)の点の座標加算値の配列
Call Kumiawase_Bakuhatsu 'VBscriptの実行開始点・VBAでは削除(orコメントアウト)
Sub Kumiawase_Bakuhatsu() '初期化と計数開始
Dim i
N = InputBox("正方形の分割数(1辺の道の数)を入力してください") + 1
ReDim No_Entry(N + 1, N + 1) '立入禁止地図の初期化
For i = 0 To N + 1 '外にはみ出さないように周囲は立入禁止
No_Entry(0, i) = 1: No_Entry(N + 1, i) = 1
No_Entry(i, 0) = 1: No_Entry(i, N + 1) = 1
Next
x_Next = Array(0, 0, -1, 1) '次(周囲)の点のx座標加算値・上下左右の順
y_Next = Array(-1, 1, 0, 0) '次(周囲)の点のy座標加算値・上下左右の順
Counter = 0 '道順数カウンタ初期化
Call Michi_Jun(1, 1) '道順数計数開始。開始点は座標(1,1)
MsgBox N - 1 & " x " & N - 1 & vbCrLf & vbCrLf & Counter & " 通り"
End Sub
Sub Michi_Jun(ByVal x, ByVal y) '道順数計数
Dim i
If x = N And y = N Then '終点なら道順が見つかったので
Counter = Counter + 1 'カウントし、
Else '終点でないなら
No_Entry(x, y) = 1 '現在地を立入禁止にし、
For i = 0 To 3 '次の点のうち行けるところに(再帰的に最後まで)行き
If No_Entry(x + x_Next(i), y + y_Next(i)) = 0 Then
Call Michi_Jun(x + x_Next(i), y + y_Next(i))
End If '(どこにも行けなければそのま現在地で)
Next '行けるところすべてに行って現在地に戻ってきたら
No_Entry(x, y) = 0 '現在地の立入禁止を解除し、
End If
End Sub '戻る。
2度も回答有り難うございます!
ちょっと儚いですよね・・・
数学の壮大さを目の当たりにしました(
わざわざプログラムを書いてくださりありがとうございます!
戸惑いながらも、実際に実行してみましたー
いやぁ・・・すごいですね
感激しました!!
5x5でも40秒かかってしまいました(
6x6は、5分たっても返答帰ってこないので、まだ放置していますw
簡単なものでも、結果が膨大になると、やはり時間も膨大にかかってしまうんですね(
VBScript というものを初めて知る切っ掛けにもなりましたし、とても感謝しています。
ありがとうございます!
No.2
- 回答日時:
最短距離でない場合の式ですが、英語のページが1つだけみつかりました。
http://www.iwriteiam.nl/Crook_path.html
チェスのrook path 問題というものと同等だと書いてありますが、rook pathっていったい何でしょうね。
まず、経路の数え方の基準ですが、質問者様は変の長さ(道の数)で数えていますがリンク先は点の数で数えていました。そのため、質問者様の数え方の方が1だけ大きくなっていますのでご注意ください。
以下、リンク先の内容を質問者様の数え方で書きます。
まず、1xnは2^nと単純です。
2以上の場合ですが、とても複雑なようです。
2xn、3xn、4xnの場合は、nが大きいところでの漸化式が書いてありましたが、正方形などnが大きくないところでは数が書いてあるのみでした。
ともかく難しい数学の話であるうでに英語なのでよくわからないというのが正直なところです。
参考URL:http://www.iwriteiam.nl/Crook_path.html
回答ありがとうございます!
数式で取り扱うと、とても難しくなるんですね・・・
やはり、2xn、3xn、4xnの個別の式はあるが、2x2、3x3、4x4...と大きくしていく際の式はないのか、気になります・・・
わざわざ英語の解説ページを探してくださりありがとうございます!
No.1
- 回答日時:
この回答への補足
リンク先を熟読してみましたが、残念ながら書かれているのは、既に式が分かっている「最短ルートでの道順」です。
最短ではなく、「『同じ所を2度通らず』スタートからゴールまで行く道順の個数」を求めたいのです。
様々な計算を行いましたが、見つからず・・・
数学って難しいですよね・・・
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
高校1年の数学なのですが 因数...
-
三角関数 範囲が-πからπのとき...
-
外積が右ねじの向きであること...
-
右下の小さい数字について
-
円筒座標におけるナビエストー...
-
「原点に返る」と「原点に戻る...
-
座標(x,y)間(=2点)の...
-
座標を入力すると角度を得られ...
-
「0でない2つのVのベクトルu,v...
-
ベクトル解析の恒等式と座標系...
-
2つの円が接する条件
-
重分積分の極座標変換について
-
連立不等式の表す領域
-
楕円面と平面の方程式
-
宝探し
-
平面と円柱の交点の求め方を教...
-
最小二乗法による球の中心・半...
-
任意の2質点間の距離が一定であ...
-
「通常の平面上の座標に三角形...
-
数3 関数の極限 どういう問題の...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
座標(x,y)間(=2点)の...
-
右下の小さい数字について
-
「原点に返る」と「原点に戻る...
-
重分積分の極座標変換について
-
測量座標と算数座標の違い
-
三角関数 範囲が-πからπのとき...
-
なぜベクトルの外積の向きが右...
-
座標のS/I方向について
-
高校1年の数学なのですが 因数...
-
2点からその延長線上にある点の...
-
生データーからのグラフから関...
-
等角螺旋(らせん)の3次元的...
-
AB=2である2定点A、Bに対して...
-
斜距離の算出公式はありますか?
-
距離と方向角から座標を求める...
-
「0でない2つのVのベクトルu,v...
-
3点との座標との距離によってあ...
-
楕円の円周上の座標を求める計...
-
楕円の角度とは?
-
外積が右ねじの向きであること...
おすすめ情報