正二十面体の二点間ルート

正二十面体の二点間のルートを探索してみます。 頂点の数も多いので、目視では

なくプログラムを使って調べます。

課題（その１）

_１２Ｃ_２＝６６通りある二点の組み合わせを分類してください。 三次元的な距離を基

に分類しても構いません。

ヒント： 点Ａから見て以下のように各頂点を分類できます。

（１）点Ｂ、点Ｃ、点Ｄ、点Ｅ、点Ｆ

（２）点Ｇ、点Ｈ、点 Ｉ、点Ｊ、点Ｋ

（３）点Ｌ

（図１、Ｆｕｎｃｔｉｏｎｖｉｅｗで作成）

まずは、プログラムを実行する為に必要な結線情報を作成します。

　　Ａ　Ｂ　Ｃ　Ｄ　Ｅ　 Ｆ　Ｇ　 Ｈ　 Ｉ 　Ｊ　 Ｋ　Ｌ

Ａ　０，１，１，１，１，１，０，０，０，０，０，０

Ｂ　１，０，１，０，０，１，１，１，０，０，０，０

Ｃ　１，１，０，１，０，０，０，１，１，０，０，０

Ｄ　１，０，１，０，１，０，０，０，１，１，０，０

Ｅ　１，０，０，１，０，１，０，０，０，１，１，０

Ｆ　１，１，０，０，１，０，１，０，０，０，１，０

Ｇ　０，１，０，０，０，１，０，１，０，０，１，１

Ｈ　０，１，１，０，０，０，１，０，１，０，０，１

Ｉ　 ０，０，１，１，０，０，０，１，０，１，０，１

Ｊ　０，０，０，１，１，０，０，０，１，０，１，１

Ｋ　０，０，０，０，１，１，１，０，０，１，０，１

Ｌ　０，０，０，０，０，０，１，１，１，１，１，０

上の結線情報を使ってプログラムを実行してみます。経由する頂点の数が増えると

ルートの数も急速に増えることが予想されるので 、ここでは経由する頂点数を最大

４に抑えたシミュレーションを行います。試行回数は１０００００に増やしています。

点Ａから点Ｂへのルートを示します。

課題（その２）

経由する頂点数が大幅に増えると、 可能なルートを求める為に膨大な試行回数が

必要になります。 全ての頂点を通るルートを効率よく得る方法を議論してください。

例えば、始点と終点の両方から探索をスタートさせるなどです。

Topへ