プログラミングの問題を解決するための特定のアルゴリズムの適用を強調したいと思います。
複数の開発者が直面しているかなり実例はデッドロックです。 実際、デッドロックはデッドロックであり、その結果、システムまたはいくつかの別個のプロセスが1つのリソースを奪い合い始めます。
人生では、このような状況が発生します。たとえば、2人の人々が入り口で、たとえば観客にお互いを通過させたい場合です。 ただし、3〜4フレーズ「後だけ！」の後、誰かが最初に合格します。
ソフトウェアレベルでは、プログラムが考えることができるようになるまでますます困難になり、「あなただけの後で！」というフレーズのマシンアナログが、再起動するまで繰り返されます。
ランタイムシステムはこのプロセスにどのように影響しますか？ ここで、グラフ上のアルゴリズムが役立ちます。
まず、グラフの要素となるものと、それをコンパイルする方法を決定します。
さらに「マシン」の例を見てみましょう。インターネットにアクセスできるシングルスレッドのJavaアプリケーションです。 コードとメッセージ出力システムが1つのスレッドで実行されることを想像してください。この場合、接続を開く前に、インターネットを使用するためにこのアプリケーションを本当に信頼するかどうかの要求がユーザーに開始されます。 ロックがあり、ユーザーが「OK」をクリックするまでコードは終了しませんが、メッセージはコードが完了した後にのみ可能になります。 この例のグラフを作成してみましょう。
頂点によって、プログラムの機能ノードを、アークによって、ノードの操作を継続するために必要な外部クエリで示します。
輪郭は、頂点からそれ自体へのパスとして定義します。 この場合、グラフでは、各コンターがデッドロックを示しています。
これで、アルゴリズム自体の正式な説明の準備がすべて整いました。
1.グラフのすべての頂点に番号を付けます。
2.グラフのすべての頂点を新規としてマークします
3.グラフのすべての円弧を新規としてマークします
4.グラフの任意の頂点をスタックに配置します
5.スタックが空でない間、スタックから最後の頂点を（プッシュせずに）読み取り、検索（ノードV）プロシージャを適用します
6.スタックが空であるが新しい頂点が残っている場合、新しい頂点のいずれかをスタックに配置して、手順5に進みます。
検索手順（ノードV）
ピークVについては、新規性の兆候を取り除きます。
すべての新しいアークDについて、頂点Vの隣接リストから
Dから目新しさの兆候を取り除きます。
アークDが新しい頂点につながる場合
D.LinkNodeをスタックに配置します。
検索（ノードD.LinkNode）を実行します。
終了（If）;
上部が新しくなく、スタック上にある場合
現在の頂点からD.LinkNodeにスタックを読み取り、検出された輪郭のデータを保存します
終了（If）;
終了（すべての新しいアークD）;
スタックからVをプッシュします。
終了（手順の検索）;
D.LinkNodeは、アークが指す頂点です。
アルゴリズムの実装例：
まず、グラフとその頂点のデータ型を宣言する必要があります。
public class GraphNode
{
public bool New;
public List <GraphNode> Links;
}
* This source code was highlighted with Source Code Highlighter .
public class Graph
{
public List <GraphNode> Nodes;
}
* This source code was highlighted with Source Code Highlighter .
次に、輪郭を検索するクラスを実装します
public static class PathFinder
{
static List <GraphNode> list;
static List < List <GraphNode>> paths;
public static List < List <GraphNode>> Find(Graph graph)
static void InternalFind(GraphNode node)
}
* This source code was highlighted with Source Code Highlighter .
そして実際、私たちの主な機能：
static List < List <GraphNode>> Find(Graph graph)
{
list = new List <GraphNode>(); //
paths = new List < List <GraphNode>>(); //
foreach (GraphNode node in graph.Nodes)
{
node.New = true ;
}
list.Add(graph.Nodes[0]); //
bool done = false ;
while (!done)
{
while (list.Count > 0)
{
InternalFind(list[list.Count - 1]);
}
//
done = true ;
foreach (GraphNode node in graph.Nodes)
{
if (node.New)
{
list.Add(node);
done = false ;
break ;
}
}
}
return paths;
}
* This source code was highlighted with Source Code Highlighter .
スタックは、リストによって意図的に実装されました。 要素を押し出さずに輪郭を読み取る必要があります
static void InternalFind(GraphNode node)
{
node.New = false ;
foreach (GraphNode nextNode in node.Links) //
{
if (nextNode.New)
{
list.Add(nextNode);
InternalFind(nextNode);
}
else if (list.IndexOf(nextNode) != -1) // ,
{
List <GraphNode> newPath= new List <GraphNode>();
int firstElement = list.IndexOf(nextNode);
for ( int i = firstElement; i < list.Count; i++)
{
newPath.Add(list[i]);
}
paths.Add(newPath);
}
}
list.Remove(node);
}
* This source code was highlighted with Source Code Highlighter .
グラフィカルに、アルゴリズムは次のように考えることができます：
パスの開始点である頂点「0」から下に移動し、次のステップでアルゴリズムがスタック内にある頂点を指す円弧を見つけた場合（この場合、頂点は「4」から来ます）、スタックの頂点から輪郭が形成されます（オン例：それぞれ0-2-3-4-5-0）、アークが新しい頂点ではなく、既にスタックから押し出された頂点（たとえば、頂点 "1"）を指している場合、輪郭は発生しません。
このアルゴリズムは、有向グラフの深層探索として知られています。
したがって、ランタイムはすべてのメソッド呼び出しのみを監視し、定期的にロックをチェックできます。
見つかったロックを処理する方法は？ デッドロックは非常に混乱しやすいため、デッドロックされたコードを再開する方がはるかに簡単な場合があります。いずれにしても、これは特定のシステムに対して個別に既に決定されているはずです。
次回（私の場合）は、トポロジカルソートのアルゴリズムです。これは、特に、ニューラルネットワークのニューロンの活性化のチェーンをコンパイルおよび分析するために使用できます。
UPD ：サンプルコードを追加
UPD2 ：アルゴリズムに移行、ありがとう