道を探して-サルタン王はラプラシアンをマスターする

...彼は言います：「私が生きていれば、私はすばらしい島を訪問します、私はGuidonを助けます。」

サルタン王国には欠陥があります。 法律は可決されました。非常線を乗り越えないでください。しかし、ここにプリンスギドンがいます。

再び彼はお辞儀をし、御treat走への招待を送りました-政治的決定がなされなければなりません。



カイツブリに似た宮殿の陰謀は、壁を立ち上げました-「言う、患者と言う」。 しかし、サルタンは、Gvidonov水ギセル、エメラルドリス、ヒーローの矢について聞いた。 そして、主な目新しさは若いジンカです。 一般的に、「私は長い間海外にいませんでした」に行くことが決定されました。



ただし、1つの問題がありました。ルートまたはスキームが必要でした。 誰も（Wrangel Baronを除く）はGuidon島への行き方を知りませんでした。 船員はカードをくれました-私は机に座っていなければなりませんでした。 サルタンは地図に寄りかかった-ブヤン島はどこですか？ タスクはよく知られているように見えました-ギドン島への道を開くこと。 しかし、あまりにも多くの方法があるとき、どのように方法を見つけるのでしょうか？



サルタンは夜まで問題を解決し、最終的に冬眠状態に陥りました。 彼はマトリックスとドットを夢見ていたが、沼地のバンプで。 ネオはボルネオ島からバンプに飛び乗った。

-締め切りに間に合いたい場合は、最大の流れに沿って泳いでください。

-何？ -サルタンはほとんど目を覚ました。 しかし、ネオはすでにうさぎになっています。

マップと隣接行列

「ラプラシアンの可能性に関するサルタン王の物語」を読んでいない場合は、おそらく今すぐ読んでください。 そこで与えられた概念を使用します。





サルタンのタスクを簡素化-7つの島だけを考えてください。 マップは、島とその長さの間の可能なパスを日単位で示します。





はい、地図は少し曲がっているように見えますが、造船業者に厳しすぎることはありません。 このマップでサルタンからギドンまでの最適な（最短の）道を見つけることは難しくありません。 「（S）アルタン>（A）ライオン>（B）ウヤン>（C）ランケル>（G）ヴィドン。」 合計6日間の旅。



このような問題を解決する一般的な方法に興味があります。それから、任意のサイズのグラフの方法を探すことができます。 さまざまな検索アルゴリズムがありますが、これは私たちのためではありません。 私たちはラプラシアンの可能性を所有しており、この可能性を利用したいと考えています。



最初のステップは明らかです。 距離行列から隣接行列に移動する必要があります（接続性）。 島間の距離が大きいほど、島同士のつながりが少なくなります。 つまり、接続の大きさは距離に反比例します。 （電子工学では、同様です- 導電率は導体の長さに反比例します）。



次に、島の隣接行列は次の形式を取ります（値は丸められ、0.33 = 1/3）：







このマトリックスは（前の記事で検討したものとは異なり）対称です。つまり、接続されたグラフは無指向です。



パスを見つけるタスクは2つに分かれています。 1つ目は、特定のポイント間で少なくとも何らかの方法を見つけることです。これは、特定のソースからの目標の達成を保証する方法です。 第二-最高の選択する多くの方法から。 この記事では、最初の比較的単純なものを検討します。



この問題を解決するには、ターゲットまでの距離に応じて島をランク付けできる特定の基準が必要です。 次に、指定された場所から航行できる島を選択すると、目標に近づいているかどうかがわかります。

島のポテンシャル

各島の潜在的な値は、そのような基準として役立ちます。 はい、はい、前の記事で使用した1次の可能性。 ただし、ラプラシアンのポテンシャルを直接使用することはできません。 対称行列（無向グラフ）の場合、そのようなポテンシャルのすべての値は互いに等しく、キルヒホッフ定数行列と呼ばれます。 対称ラプラシアンでは、この定数は行列式（行列式）の役割を果たします。 さらに、キルヒホッフ定数を一般的な（スカラー）ポテンシャル-単なる用語（あまり成功していないかもしれません）と呼びます。



したがって、対称ラプラシアンでは、ポテンシャルベクトルはスカラーになります-共通のポテンシャルです。 ラプラシアンの場合、総ポテンシャルの値は約8.61です。 それは単純であると考えられます-隣接行列に基づいて、ラプラシアンが構築され（上記のように）、ラプラシアンから行と列を削除し、行列式を考慮します。 これが私たちの共通の可能性です。



これはすべて素晴らしいことですが、これまでのところ、方法を見つけるのは無意味です。 島のポテンシャルが異なる必要があると同時に、最大値（サルタン）から最小値（Gvidon）、またはその逆に変化します。違いはありません。 これを達成する方法は？

2つの美しい方法があります（おそらくそれ以上）。 最初は古典的です。 それではそれから始めましょう。

第一の方法。 ディリクレ問題を解く

そして、古典的なのは、電気回路（マルコフも）のアナロジーを使用することです。 異なる電位が必要なので、初期状態（島）とターゲットの間に電位差を適用するだけです。 この違いは、ノード（島）間のフローにつながり、その結果、各島には独自の可能性があります。



ここで重要なのは、ポテンシャル値が調和である 、つまり、各ポテンシャルの値が隣接するポテンシャルの値に対して平均であることです。 このような調和ベクトル（関数）には1つの特性があります。境界で最小値と最大値を取ります。 私たちの場合、境界は、潜在的な値が設定（固定）されているノード、つまり、サルタン島とギドン島です。 潜在的なベクトルの調和により、これらの島の1つでは潜在力が最大になり、他の島では潜在力が最小になることが保証されます。 そして、残りの島々のポテンシャルはそれらの間のどこかになります。 これが必要なものです。



Guidon島に割り当てるポテンシャルが低い場合、Saltanからウェイを検索するときは、現在よりもポテンシャルが小さい島のみを選択し、ポテンシャルの大きい島を除外する必要があります。



少し残った-島の可能性を見つけるために。 この問題は、第1回の記事で解決した問題と似ているため、ポテンシャルUの調和を強調する形でバランス方程式を再度示します。







違いは、いくつかの可能性が設定されていることです。 そのような値の境界を呼び出すのが習慣です。 この用語はあまり成功していないかもしれませんが、一般的に受け入れられています。



境界で既知によって未知のポテンシャルを見つける問題は、通常ディリクレ問題と呼ばれます。 彼女には解決策があります（喜んで）。

基本マトリックス

電位が与えられたノード間の結合の大きさ（導電率）は重要ではありません。 つまり、それら（これらの接続）は決定に影響しません。 したがって、与えられた（境界）ノードをラプラシアンから除外できます。 この例では、サルタン島とギドン島をラプラシアンから除外します。 次のような追加のマイナーラプラシアンが得られます。







このマイナーの逆行列は、 基本 （トラップ付きマルコフ連鎖の理論からの用語）と呼ばれます。 このカードの場合、基本マトリックスの形式（チェック）は次のとおりです。







次に、外部ノード（国内ではSaltan島とGvidon島）と内部ノードを接続する必要があります。 つまり、2つの列だけが残っている隣接行列の少数派です。







基本マトリックスに外部と内部（世界）間の所定のマイナー接続を乗算すると、内部に対する外部の影響のマトリックスを取得します（そして、操作の完了に近づきます）。 影響マトリックスは次のとおりです。







このマトリックスの要素の値は、内部への外部ポテンシャルの寄与を反映しています。 たとえば、サルタナのポテンシャルのバイヤナのポテンシャルへの寄与は0.513です。 外部ポテンシャル（SaltanおよびGuidon）を設定することにより、影響マトリックスに外部ポテンシャルのベクトルを掛けることで、他のすべての島のポテンシャルを計算できます。 私の意見では、非常にクールです。



各行の値の合計は1です。つまり、預金の重量は正規化されます。 これは、たとえば、島がサルタンに近いほど、ギドンから遠いほど、逆もまた同様であることを意味します。



島をランク付けするという問題を解決するには、原則として、このマトリックスで十分です。その値に基づいて、ターゲットへの距離/近接度によって既に島をソートできるからです。 つまり、目標を達成できますが、最初に検討します

島のポテンシャルを計算する別の方法。

2番目の方法。 対称ラプラシアンの摂動

基本的なマトリックスによる島のポテンシャルのランキングは、普遍的なアプローチです。 普遍的なすべてのものと同様に、それは私たちのタスクにとって少し冗長（重い）です。 つまり、キルヒホッフ行列（ラプラシアン諸島）を怒らせるのが簡単です。



上記のように、対称ラプラシアンの場合、ポテンシャルベクトルのすべての成分は等しくなります。 等しくないことが必要です。 したがって、ラプラシアンを非対称にする必要があります。 これを行う方法も理解できます。 サルタン島からギドンまでの潜在的な勾配が必要なので、対応する接続​​を怒らせる必要があります。 この接続により、電位勾配が設定されます。



「怒り」とは何ですか？ これは、隣接（伝導性）マトリックスで、いずれかの方向の結合値を特定のデルタ（たとえば1）増加させることを意味します。 また、反対方向では、値は変更されません。 たとえば、ギドン島はサルタン島に接続されていますが、反対方向には接続されていません。



ある意味では、隣接行列（およびラプラシアン）のこのような歪み（摂動）は、島への外部ポテンシャルの適用と同等です。 実際、ノード間の外部電位の差を維持するには、何らかの種類の接続が必要です（電子機器では、バッテリー）。



摂動行列の場合、前の記事で紹介した1次ポテンシャルとして、島のポテンシャルをすでに計算できます。



ラプラシアン諸島の私たちの混乱した心は次のとおりです。







摂動を受けていないものとの違いは、右上隅の単位であり、これが「インジネーション」です。 そのような行列の潜在的なベクトルは等しい（前の記事の計算方法）：







問題は、摂動行列のポテンシャルのベクトルと、基本行列を通して計算されたポテンシャルのベクトルが同等になるかどうかです。 要するに、はい。 これを確認する最も簡単な方法は、サルタン島とグウィドン諸島の摂動ポテンシャルを外部ポテンシャル（25.28、8.61）に置き換えることです。 この2つの値のベクトルに影響行列を乗算すると、ポテンシャルの内部値が得られます。



なぜこれが起こったのですか？ それを理解してみましょう。 第一に、摂動されたポテンシャルも同じ平衡方程式を満たすため、調和ポテンシャルです。 第二に、摂動ポテンシャルの境界値も常に極端です-そのうちの1つ（この場合、サルタンポテンシャル）は最大であり、もう1つ（Guidonポテンシャル）は最小です（摂動の方向を変更すると、それぞれ逆になります）。 摂動ポテンシャルが極端な理由を理解するには、それらがどのように計算/取得されるかを知る必要があります。

可能性のあるデリバティブ

サルタンからギドンまでではなく、例えばゴードンからアルビオンまで、島を異なる順序でランク付けする必要があるとします。 毎回、方向を決定する島を変更するときに行列式および/または逆行列を数えることは良い考えのようには見えません。 一度逆数をカウントしてから、この逆を使用することは可能ですか？



摂動により合計（スカラー）ポテンシャルがどのように変化するかを見てみましょう。 フォーミュラの言語では、これは、接続の値を変更するときに、総ポテンシャルの導関数（変更）を見つける必要があることを意味します。 幸運なことに、前述のように、可能性は接続の積の合計によって決まります。 つまり、条件付き線形および導関数はすべて単純でなければなりません。



一次電位依存性 接続の価値について 二次ポテンシャルにより決定：







可能性の順序とはどういう意味ですか？ 1次ポテンシャルを取得するには、1行1列をラプラシアンから削除する必要があります。 2次のポテンシャルを得るには、2行2列を削除する必要があります。 3日目-3つを削除するなど 行列の行と列を削除した後に残っている行列（追加のマイナーと呼ばれる）については、行列式を考慮します-その値はn次のポテンシャルの対応する値になります。 さて、1次と2次のポテンシャルを使用し始めたので、前者をベクトルポテンシャル、後者をマトリックスポテンシャルと呼ぶのが便利です。



式（2.1）では、2次ポテンシャルは 。 インデックスはコンマで区切られます-最初は削除された行を意味し、2番目は列を意味します（逆の場合もあります）。



摂動を受けた島にインデックスを割り当てます。 S-サルタン、G-ギドン、およびブヤン島のインデックスB。その後、「G-S」接続の摂動によるブヤン島のポテンシャルの変化は次のように表現できます。







ラプラシアンのこの変化を計算します。 対応する行と列をラプラシアンから削除し、行列式を計算します。 わかった 。 Buyana島のポテンシャルからGuidon島のポテンシャル（一般的な摂動されていないポテンシャルと一致）を引くと、同じ値が得られます：17.15-8.61 = 8.55。 つまり、すべてが正しく、式が機能します（これは、単一の摂動を選択したためです-一般的な場合、接続Cの変化を掛けることを忘れてはなりません）。



そして、式（2.1）に従って、摂動した島-サルタンとグウィドンのポテンシャルを計算するとどうなりますか？ 式（2.1 '）の対応するインデックスを代入すると、次のようになります。







ロシア語に翻訳すると、ギドン島のポテンシャルは外乱SGによって変化せず（合計に等しいままです）、サルタン島のポテンシャルは2次の主要ポテンシャルの値によって変化します。

ポテンシャルの種類

「主要な」および他のタイプの可能性について話すために、少し余談します。 ラプラシアンから削除された行インデックスが列インデックスと一致する場合、ポテンシャルプリンシパルを呼び出します。 したがって、主要なポテンシャルについては、インデックスのセットを1つだけ示すだけで十分です。 。



そして、非主要種とは何ですか？ さらに2つの状況が考えられます-削除された行インデックスのセットは、列インデックスと交差し（そのようなポテンシャルを隣接と呼びます）、交差しません（自由ポテンシャル）。 式（2.1）では、隣接するポテンシャルが関係しています（インデックスkによる交差）。



今、注意！ 神の贈り物は、すべての非主要な可能性を主要なものを通して表現できるということです。 対称ラプラシアンの一般式は次のとおりです。







隣接するポテンシャルの式は次のとおりです。







（2.4）を（2.1）に代入して、ノードの電位の導関数と主な電位との関係を取得します。







あげます！ この式は、私たちが探していたツールです。 それを調べ、開始し、使用することができます。

二次ポテンシャル行列

したがって、対称ラプラシアン（無向グラフ）の真に基本的なマトリックスは、2次の主要なポテンシャルのマトリックスです。 私たちの島に対する彼女の見解は次のとおりです。







このマトリックスから、サルタンとギドンの間の接続の乱れを伴うブヤナ島の可能性の増分を計算します。







すでにこの図を見たことがありますので、式は機能しているようです。



特定のラプラシアンについてこの行列を取得する方法は？ もちろん、行/列を愚かに削除し、未成年者の決定要因を読み取ることができますが、これはコストがかかり、非効率的です。 したがって、通常、それらは異なる動作をします。 追加のマイナーラプラシアン（つまり、1行目、1行目、1列目など）を削除し、それに対応する随伴行列を計算します（ 随伴行列は逆行列で、その値に行列式が乗算されます）。 このようにして得られたマトリックスは複雑なポテンシャルですが、値に距離変換を適用することで拡張できます（はい、多くのあいまいな用語がありますが、どういうわけかすべてを呼び出す必要があります）。 その結果、目的のマトリックス電位が得られます。 つまり、ここにそのようなホーナースキームがあります。



ポテンシャルマトリックス=距離（マトリックスアタッチメント（追加マイナー（ラプラシアン）））



距離の変換は次のとおりです。







対称行列の場合







ポテンシャルマトリックスは、抵抗距離のマトリックス （合計ポテンシャルの係数によって値が異なります）、および逆ラプラシアンであるグリーンマトリックスに直接関連していますが、これについてはどういうわけか別の時間です。

ジオメトリとの関係

行列ポテンシャルの値は、グラフのノード間の距離の二乗に比例します。 実際、マトリックスの値を見て、それらを造船所の地図と比較すると、サルタン島とギドン島の間の最高値（16.67）であるこの文が真実であるように見えることがわかります。



これは、ベクトルポテンシャルの導関数に幾何学的な意味を与えることができることを示唆しています。 式（2.5）を次の形式に書き換えます







（ここでは表記を使用しました ）、この式を学校のコースで知られているコサイン定理と比較します







次に、ベクトルポテンシャルの導関数と三角形のパラメーターの間の次の関係を取得します（インデックスは三角形の頂点の表記法i = C、j = B、k = Aにつながりました）。











式（2.7）は、三角形-BAの反対側の導電率（接続性）の変化に伴う頂点Cの電位の変化を示しています。 式は置換BAに関して非対称であることに注意してください。 これは、ポテンシャルの導関数が方向に依存するという事実によるものです。







方向を変更すると、導関数の値は他の側面と別の角度で表現されます：







式（2.7）は、三角形の摂動側のポテンシャルの極値を示しています。 角度のコサインの値は常に（モジュロ）1未満であるため、頂点Cが三角形の他の頂点（ AまたはB ） のいずれかと一致する場合にのみ、三角形のポテンシャルの極値が発生することは明らかです。 これは、調和関数の特性と三角形の特性の間の予期しない接続です。

まとめ

締めくくりの時間です。 振り返ってください。 無向グラフのノード間のパスを決定する方法を探し、ノードをランク​​付けする方法から始めました。 これは一般的な方法であり、パス検索タスクだけでなく適用できます。



対称的に相互接続されたオブジェクトのセットを用意します（接続は、たとえばオブジェクトの近接度を反映する場合があります）。 ソート基準がない限り、これらのオブジェクトをソートすることはできません。すべてのオブジェクトは同じです。 ただし、セットからいくつかの2つのオブジェクトを選択し、一方が最大でもう一方が最小であることを示す場合、他のすべてのオブジェクトは、大小への近接度によってランク付けできます。 単純に境界（大小のオブジェクト）を定義することにより、与えられた境界に関して残りのオブジェクトを偏光します（異なるポテンシャルを与えます）。





面白い。

ええ、はい、出航するには早すぎます。 目的地への航行を保証する方法を見つけましたが、最適な（最短）経路を見つける方法を示していませんでした。 ここに続きます。