（上記のプログラムはGeminiと生成、以下はCopilotの解説をベースに作成）
Turnpike問題（ターンパイク問題）は、一見するとパズルのようですが、実はX線回折やDNA解析、質量分析などにも関係する有名な逆問題です。
一直線上に何個かの点が並んでいるとします。
0 2 7
●---●------●
という3点があるとき、点同士の距離は
2（0↔2）
5（2↔7）
7（0↔7）
です。Turnpike問題では逆に、点の位置はわからないが、すべての点対の距離だけが与えられるという状況を考えます。上記の例だと、{2, 5, 7}だけが与えられ、そこから点の位置を復元するのがTurnpike問題です。
昔の有料道路（Turnpike）を考えます。道路沿いに料金所や出口が並んでいるとして、すべての料金所間の距離がわかっている。そこから、料金所が道路上のどこにあるかを求めたい。これがTurnpike問題の名前の由来です。
では、例として距離が {2,2,3,4,5,7} の場合について解いてみましょう。
最大距離を探す
距離集合の最大値は必ず左端と右端の距離です。この例だと最大距離は7なので
(0 - 7)
を最初に固定します。
残りから最も大きい距離に着目
{2,2,3,4,5,7}から最大距離7を除去すると{2,2,3,4,5}になります。この残りの中で最も大きい距離は「5」なのでこれに着目します。これを満たすには
新しい点と右端の距離が5 → 新しい点の座標は 7−5=2 → (0 - [2] - 7)
新しい点と左端の距離が5 → 新しい点の座標は 5 → (0 - [5] - 7)
のどちらかになるはずですので、これを両方試して「矛盾している方を棄却」することで解を選別していきます。ただし、最初の試行は矛盾が生じないので、この方法では鏡像の関係を破ることはできません。ここでは便宜上、(0 - 2 - 7)を採用することとします。
あとは繰り返し
先ほどの(0 - 2 - 7)から出てきた距離は {2, 5, 7}、残りの距離は{2, 3, 4}となります。この時、5を逆の端から読んだ距離「2」が回収されるのがポイントで、両端から距離を回収していくというアルゴリズムにより距離を決めることができます。あとは上と同じように残りの距離から最大距離となる「4」に着目して考える…というのを繰り返します。今の例の場合、既に左側に2が配置されていますので
新しい点と右端の距離が4 → 新しい点の座標は 7−4=3 → (0 - 2 - [3] - 7)
新しい点と左端の距離が4 → 新しい点の座標は 4 → (0 - 2 - [4] - 7)
が次の候補です。しかし、後者のケースは2と3の間の距離が1となりますが、これは{2,3,4}の中には含まれていないので矛盾します。一方、前者のケースは7との間の距離が3、2との間の距離が2となり全て{2,3,4}の中には含まれています。なので、このケースでは後者を採択し、前者を棄却します。この例ではこれで全ての距離が説明完了となりますが、数が多い場合もこれを繰り返すだけでOKです。
小さい例なら簡単ですが、例えば20点あると、距離の数は190個になります。しかもこの点を左に置くか？右に置くか？という選択が大量に発生します。したがって
候補を試す
矛盾したら戻る
という探索問題になるのですが、上記の基準無しでこれを行うのは非常に厄介です。
Turnpike問題は距離情報から元の配置を求める問題です。これは回折実験で出てくる
位相問題
Patterson関数
と非常によく似ています。例えば結晶中に原子が
x₁, x₂, x₃,...
にあるとき、Patterson関数は原子間ベクトルの集合を与えます。つまり
位置 → 距離情報
はわかるが、
距離情報 → 位置
を求めるのが難しい。この構造がTurnpike問題そのものです。そのため、Turnpike問題は「1次元版の結晶構造決定問題」だと言えます。