道順組み合わせの最短距離有無の式について

質問

最近、道順に関する組み合わせを題材にした組合せ爆発の動画が話題になっており、
それを見たのですが・・・
同じ所を2度通らない道順の組み合わせでの式がわかりません・・・

最短距離に関する組み合わせは、高校数学で習うと思うですが、最短距離でなく同じ所を2度通らない組み合わせに式など存在するのでしょうか？（画像参照）
2ｘ2の場合、最短距離は6通りですが、2度通らない条件だと12になってしまいます。
3ｘ3の場合、最短距離は20通りですが、2度通らない条件だと184通り
4ｘ4の場合、最短距離は70通りですが、2度通らいない条件だと8512通りになります。

2度通らない条件での式が存在すれば、敷や解き方教えていただけないでしょうか？
もし「アルゴリズム」というものを使用しなければ回答することができなければ、アルゴリズムのさわりだけでも教えていただけると嬉しいです。

よろしくお願いします。

回答No.3

queuerev2 · ベストアンサー

No.2です。
動画見ました。
あの終わり方はちょっと寂しいですね。

さて、道順の数を求める方法ですが、動画でも「最先端のアルゴリズム技術」と述べていますし、
No.2で示したリンク先にも正方形の場合は数が書いてあるだけであったので、やはりアルゴリズムを使うしかないのだと思います。
そこで実際にプログラムを書いてみました。言語はVBScript(WScript)ですが、VBAでも「Call Kumiawase_Bakuhatsu」の行を削除すれば動きます。
使ったアルゴリズムですが、行けるところに行ってゴールに到達したら数えるという単純なものなのです。
なお、このプログラムで実用的に計算できるのはせいぜい5x5だと思います。
もし６以上の数を入れて計算が終わらなくなったら、VBScriptならタスクマネージャからプロセスの終了を、VBAならBreak (Ctrl + Pause)を行ってください。

Option Explicit
Dim N '１辺の点の数 兼 終点の座標
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
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度も回答有り難うございます！

ちょっと儚いですよね・・・
数学の壮大さを目の当たりにしました（

わざわざプログラムを書いてくださりありがとうございます！
戸惑いながらも、実際に実行してみましたー
いやぁ・・・すごいですね
感激しました！！
5ｘ5でも40秒かかってしまいました（
6ｘ6は、5分たっても返答帰ってこないので、まだ放置していますｗ

簡単なものでも、結果が膨大になると、やはり時間も膨大にかかってしまうんですね（
VBScript　というものを初めて知る切っ掛けにもなりましたし、とても感謝しています。

ありがとうございます！

回答No.2

queuerev2

最短距離でない場合の式ですが、英語のページが１つだけみつかりました。

http://www.iwriteiam.nl/Crook_path.html

チェスのrook path 問題というものと同等だと書いてありますが、rook pathっていったい何でしょうね。

まず、経路の数え方の基準ですが、質問者様は変の長さ（道の数）で数えていますがリンク先は点の数で数えていました。そのため、質問者様の数え方の方が１だけ大きくなっていますのでご注意ください。
以下、リンク先の内容を質問者様の数え方で書きます。

まず、1ｘnは2^nと単純です。
2以上の場合ですが、とても複雑なようです。
2ｘn、3ｘn、4ｘnの場合は、nが大きいところでの漸化式が書いてありましたが、正方形などnが大きくないところでは数が書いてあるのみでした。

ともかく難しい数学の話であるうでに英語なのでよくわからないというのが正直なところです。

参考URL：

http://www.iwriteiam.nl/Crook_path.html

お礼

回答ありがとうございます！

数式で取り扱うと、とても難しくなるんですね・・・
やはり、2ｘn、3ｘn、4ｘnの個別の式はあるが、2ｘ2、3ｘ3、4ｘ4...と大きくしていく際の式はないのか、気になります・・・

わざわざ英語の解説ページを探してくださりありがとうございます！

回答No.1

kotetu12

http://www.kwansei.ac.jp/hs/z90010/sugaku1/kakuritu/combi2/combi2.htm

詳しく書いてあります。

道順に応用出来るそうです。

お礼

回答ありがとうございます！

補足

リンク先を熟読してみましたが、残念ながら書かれているのは、既に式が分かっている「最短ルートでの道順」です。
最短ではなく、「『同じ所を2度通らず』スタートからゴールまで行く道順の個数」を求めたいのです。

様々な計算を行いましたが、見つからず・・・
数学って難しいですよね・・・