接触している7つのシリンダーに関する記事を読んだ後、私は疑問に思いました。このタスクは本当に難しいのでしょうか。 または彼女は以前に真剣に関与していませんでしたか？
空間内の既知の半径の無限円柱の位置は、4つの独立した量によって定義されます（4つの自由度があります）。 一般的な位置にある7つのシリンダーの場合、28個の値が必要です。 「2つのシリンダーが接触する」各条件には1つの制限があり、合計で7つの自由度があります。 それらのうち6つ-空間の動き、後者は構成自体に残ります。 つまり、トポロジが破損しない限り、1つ以上の1パラメーター構成のファミリを取得する必要があります（そのため、ソリューションがまったくない場合があります）。
シリンダーの代わりに、直線で作業する方が便利です。 2つのシリンダーの直径が同じで、たとえば1に等しい場合、それらの軸間の距離が1に等しい場合にのみ（外部で）接触します。 この事実を考慮し、
最初のタスクは、システムを記述する変数の数を可能な限り減らすことです。 空間の変位を取り除くことから始めましょう。 最初の行がOz軸であるとしましょう。 Ozまでの距離が1である別の線Bがあると仮定します。Ozに最も近いB上の点に座標（x、y、z）があります。 次に、見やすいように、条件
、およびラインBの方向ベクトルは、一部のdに対して（-y、x、d）の形式で指定できます。 したがって、線は4つの数字x、y、z、dと1つの追加条件で定義されます。
Oz軸に沿ったシフトとその周りの回転という2つの自由度があります。 2行目でx = 1、y = z = 0を選択して修正します。 残りの20の未知数（残りの5行のパラメーター）は、さらに制限されません。
パラメーター（x 1 、y 1 、z 1 、d 1および（x 2 、y 2 、z 2 、d 2 ）を持つ2つの線の間の距離が1であるという条件は、
これは、8つの未知数をリンクする6次方程式です。 線のわずかに異なるパラメーター化（ポイント（x、y、0）を通過し、方向ベクトル（u、v、1）を持つ ）を取得すると、次数を4番目に減らすことができますが、Ozに垂直な線は失われます。
したがって、多項式があります。 21の未知数を持つ20のそのような方程式のシステムを構成し、それをどう処理するかを考えることは残っています。 これを覚えて、別の方法を探してください。
それを言ってみましょう
ある角度のために 
。 その後、私たちとの行は3つのパラメータによって設定されます 
、2行目には 
、2本の線の間の距離を固定する式は次のようになります。
どこで
。 これは、 z 2 -z 1の 2次方程式です。つまり、量を知っています。 
z 2 -z 1の 2つの可能な値を簡単に取得できます。
アクションプランは次のようになります。
1.ランダム検索を試してみましょう。 ランダムセットを生成する
。 3番目から7番目までの各行について、2番目の行までの距離の条件を記述します。これにより、未知数z 3 ... z 7の 2つの可能な値が得られます。 これらの値の32の可能な組み合わせのそれぞれについて、残りのラインペア間の距離が1からどれだけ異なるかをチェックし、最適な組み合わせを選択します。 何らかの最適化方法により、すべての距離を1にしようとします。成功した場合は、勝ちました。 そうでない場合は、さらに100万回繰り返します。
2.検索で結果が返されなかった場合、検索を拡張します。 z 3 、... z 7のすべての可能な組み合わせから始めます。
3. 4つのシリンダーが接触している場合、シリンダーの数がそれらすべてに接触することに注意してください。 何らかの方法で最初の4つのシリンダー（4つの自由度があります）を構築し、次に（ランダム検索により）接触しているシリンダーをできるだけ多く探し、3つのシリンダーを選択します。軸間のペアワイズ距離は可能な限り1に近く、受信したセットを最適化します。
4.同じことですが、最初に、接触しているすべてのシリンダーを探して、4つの多項式のシステムを解き（32の根を持つ複雑なフィールド）、3つの軸すべてを反復します。
5.再び不運な場合は、これらの構成とその使用方法について考え始めます。
残念ながら、この計画には何もありませんでした。 なんで？
ランダム検索と最適化
ランダム解を最適化するために、最もテストされた方法であるニュートンの方法を使用しました。 確かに、彼は未知数の数に等しい方程式の数を持っている必要があるので、未知のd 2 （つまり、1番目と2番目の直線の間の角度）を修正することにしました。 によって偏微分z k -z mを見つける
技術の問題であり、システムのサイズが10 * 10のヤコビ行列を簡単に構築できます。 確かに、通常の式x：= xJ -1 f（x）の代わりに、スローモーションx：= xc * J -1 f（x）を使用しました 。ここで、cは0.1から0.001まで変化しました（さまよわなければならない地形のため、非常に不均一で、極小値がたくさんあります）。 さらに、この方法は直線の接着を崇拝し、その後0で割ろうとします-私は彼に説明しなければならなかった 
行のペアがゼロに近い場合、この試行では失敗しました。
そのような検索を書くことは難しくありませんでした。 不明な瞬間をすべて修正した後、私はそれを起動しました-そして、最初の解決策は、約9000回目の試みで、数秒後に発見されました。 次の30分間で、プログラムは500個の構成を検出し、平均で7,500回の試行のうち1回が成功しました。
独立したチェックにより、解が正しいことが示されました-線のペア間の距離は1から10 -9以上異なりませんでした。 しかし、構築された写真を見ると、それらの多くがいくぶん似ていることがわかりました...それで、次の質問は、どの構成が同じで、どのような意味ですか？
この問題へのアプローチ方法は考えられませんでした。 したがって、私は残りの自由度を思い出し、シリンダーが互いに離れることなくどのように動くことができるかを見ることにしました。 たとえば、次のようになりました。
各構成についてシリンダーの最小必要長さ（つまり、軸に沿って測定された各シリンダーのタッチポイント間の最大距離）を計算し、グラフをプロットすると、見つかった構成のほとんどが同じパスを提供するという結論に達しました。 このような軌道を小さなステップで構築し、その構成ごとに不変式のセットを計算することは難しくありませんでした。 次に、見つかった500個のソリューションのそれぞれについて、この軌跡上で最も近いポイントを見つけました。 480の構成が軌道に直接当たりましたが、他の20の構成は新しいものでした。 彼らは次のように振る舞った：
何らかの理由で、この軌道は、無限大で終わりますが、ある種の行き止まりで始まり、失敗するまで続きます。 私はこの謎をまだ解決していません。 さらに、ある場所の2つの軌跡が非常に密接に交差または収束する兆候があります。
いずれにせよ、計画の2〜5ポイントは必要ありませんでした。
さらに7000万ポイントを経て10,000以上のソリューションを見つけた後、プログラムは新しいものを見つけませんでした。 したがって、スコアの最初の1分だけが有効に使用されました...
UPD：状況は思ったより少し悪かった。 構成の2番目のファミリは、最初のファミリのブランチの1つにすぎませんでしたが、最初の2つのシリンダの選択が異なります。 そして、一方の端では、この枝は先端だけでなく、いくつかの通行不能なジグザグの上にもあります-そして、私はまだその継続を見つけることができませんでした。
これまでのランダム検索では、すでに見つかった家族からのポイントのみが提供されます。 他の構成（およびソリューションセットの接続コンポーネント）がない可能性があります。 ハンガリー人が見つけた構成が実際に異なるかどうかを確認する必要があります。
UPD2：一般に、プログラムにエラーがありました-いくつかの行列係数が正しくありませんでした（しかし、それにもかかわらず、反復は何らかの形で収束しました:)）。 修正後、収束は著しく改善され、約1時間で1億の開始点が処理されました。 見つかったすべてのソリューション（約9000）は主な軌道に落ちました...どうやら、これ以上のソリューションはありません。
ところで、多項方程式系を解くと、正しい解を見つけるのが難しくなります。 線間の距離が1であるという条件を記述する多項式は、平行線の任意のペアに対して消失するため、解のセットには多くのスプリアス成分が存在します。