プラレール問題 #

概要 #

タカラトミーのプラレールという鉄道玩具が広く知られています [1]．前ページまでで，レールとレイアウトの形式的定義について述べました．本ページでは，レールとレイアウトに関するどのような問題が考えられるかについて述べます．

プラレール問題 #

プラレールに関する問題について考えます．通常，手元にあるレールは有限です．もう少し正確にいうと，有限種類のレールが有限個ずつあるのが普通です．レールは接続ができればどの向きにおいても裏返しても構わないのでした．

問題の定式化を考える前に，まず準備として記号の定義を追加します．

Definition 1. \(\sigma\) を \(\mathbb{R}^3\) 上の直交変換とする．
\(\phi\in\Phi\) に対して \(\phi^\sigma\) を，\(\phi^\sigma(\theta)=\phi(\theta)^\sigma,(0<\theta<1)\) で定める．
レール \(r=(\phi_1,\dots,\phi_n,t_1,\dots,t_m,\psi,u_1,\dots,u_{n-1})\in\mathcal{R}\) に対して \(r^\sigma\) を，\(r^\sigma=(\phi^\sigma_1,\dots,\phi^\sigma_n,t_1,\dots,t_m,\psi,u_1^\sigma,\dots,u_{n-1}^\sigma)\) で定める．
\(\)

\(\sigma\) は3次元空間上の回転を表すので，これはレールの回転を表すための記号です．

Definition 2. \(N\) を1以上の整数とし，\(r_1,\dots,r_N\) をレール，\(n_1,\dots,n_N\) を1以上の整数とする．レイアウト \(R=(r'_1,\dots,r'_n,c_1,\dots,c_m)\) について，各 \(i=1,2,\dots,n\) について，\(j_i\) と，ある \(\mathbb{R}^3\) 上の直交変換 \(\sigma_i\) が存在し，\(r'_i=r_{j_i}^{\sigma_i}\) であり，\(|\{j\mid \exists \sigma\,(r_i={r'_j}^\sigma\}|\le n_i\) であるとき，レイアウト \(R\) は \(r'_1,\dots,r'_n,c_1,\dots,c_m\) で 実現可能 であるといい，このレイアウト全体を \(\mathcal{A}_{r_1,\dots,r_N,n_1,\dots,n_N}\) で表す．

実現可能という定義は，手元のレールセットでレイアウトが組めるものを指します．

このとき，以下の問題が考えられます．

Problem 3. \(N\) を1以上の整数とし，\(r_1,\dots,r_N\) をレール，\(n_1,\dots,n_N\) を1以上の整数とする．
\(R\in\mathcal{A}_{r_1,\dots,r_N,n_1,\dots,n_N}\) であり，\(R\) が完全レイアウトであるものを一つ求めよ．
\(R\in\mathcal{A}_{r_1,\dots,r_N,n_1,\dots,n_N}\) であり，\(R\) が完全レイアウトであるのうち，\(R=(r_1,\dots,r_n,c_1,\dots,c_m)\) における \(n\) が最大になるレイアウト \(R\) を一つ求めよ．
\(\epsilon>0\), \(\epsilon’>0\) とする．\(R\in\mathcal{A}_{r_1,\dots,r_N,n_1,\dots,n_N}\) として，\(R\) が \((\delta,\delta')\)-レイアウトのとき，すべての \(i\) について \(\delta_i<\epsilon\), すべての \(i\) について \(\delta'_i<\epsilon'\) であるものを1つ求めよ．
\(\epsilon>0\), \(\epsilon’>0\) とする．\(R\in\mathcal{A}_{r_1,\dots,r_N,n_1,\dots,n_N}\) として，\(R\) が \((\delta,\delta')\)-レイアウトのとき，すべての \(i\) について \(\delta_i<\epsilon\), すべての \(i\) について \(\delta'_i<\epsilon'\) であるもののうち，\(R=(r_1,\dots,r_n,c_1,\dots,c_m)\) における \(n\) が最大となるレイアウトを一つ求めよ．

Prob. 3. について，1, 2 はプラレールで環状のレイアウトを作る問題で，1に対して2はより大きい（より多くのレールを使う）レイアウトを求める問題です．3, 4 はそれにいわゆる なじませつなぎ を許容して，環状のレイアウトを求める問題です．

一般には，車止めや車両基地などが含まれるなど，作るべきレイアウトが環状とは限りませんが，ここでは簡単のため省略します．ただし，意図的にレイアウトに次数が1となるような頂点を含ませる場合は，接続先が1方向しかない頂点にループ辺をもたせることで回避可能と思われます．

まとめ #

レールやレイアウトは，一般に数学的にモデル化しようとすると，複雑なものになることがわかりました．その結果，本節の定義においては，たとえば，手元のレールセットで実現可能なレイアウトで，環状になるものを求める問題は，難しい問題と考えられます．

しかし，玩具としては成り立っていることを考えると，通常のユーザは，一般的解法を検討することなく，ヒューリスティックな方法でレイアウトを考えているものと思われます．本節の検討結果から，レイアウトの自動生成などを考える場合は，そのようなヒューリスティクスを調査することが有用と思われます．

参考文献 #

[1] タカラトミー，“トップページ｜プラレール｜タカラトミー”, https://www.takaratomy.co.jp/products/plarail/ , 2023/5/14 最終アクセス．