重み付けされていない有向グラフと考えることができるグローバル ユニーク パス テーブルがあります。各ノードは、制御されている物理ハードウェアの一部、またはシステム内の一意の場所を表します。テーブルには、ノードごとに次の情報が含まれています。
- 一意のパス ID (int)
- コンポーネントのタイプ (char - 'A' または 'L')
- そのノードが接続されているパス ID のカンマ区切りのリストを含む文字列 (char[])
開始ノードと終了ノードを指定して、2 つのノード間の最短パスを見つける関数を作成する必要があります。通常、これは非常に単純な問題ですが、ここに私が抱えている問題があります。メモリ/リソースの量が非常に限られているため、動的メモリ割り当て (つまり、キュー/リンク リスト) を使用できません。再帰的でない場合もいいでしょう (ただし、テーブル/グラフ自体が非常に小さい場合は、それほど大きな問題にはなりません。現在、26 個のノードがあり、そのうち 8 個は決してヒットしません。最悪の場合、合計で約 40 ノードになります)。
何かを組み立て始めましたが、必ずしも最短経路が見つかるとは限りません。擬似コードは次のとおりです。
bool shortestPath(int start, int end)
if start == end
if pathTable[start].nodeType == 'A'
Turn on part
end if
return true
else
mark the current node
bool val
for each node in connectedNodes
if node is not marked
val = shortestPath(node.PathID, end)
end if
end for
if val == true
if pathTable[start].nodeType == 'A'
turn on part
end if
return true
end if
end if
return false
end function
このコードを修正する方法、またはそれを機能させるために使用できる何かを知っている人はいますか?
- - - - - - - - - 編集 - - - - - - - - -
Aasmund のアドバイスを受けて、幅優先検索の実装を検討しました。以下に、オンラインで見つけた疑似コードを使用してすぐにまとめた c# コードをいくつか示します。
オンラインで見つかった疑似コード:
入力: グラフ G と G の根 v
procedure BFS(G,v):
create a queue Q
enqueue v onto Q
mark v
while Q is not empty:
t ← Q.dequeue()
if t is what we are looking for:
return t
for all edges e in G.adjacentEdges(t) do
u ← G.adjacentVertex(t,e)
if u is not marked:
mark u
enqueue u onto Q
return none
このコードを使用して作成した C# コード:
public static bool newCheckPath(int source, int dest)
{
Queue<PathRecord> Q = new Queue<PathRecord>();
Q.Enqueue(pathTable[source]);
pathTable[source].markVisited();
while (Q.Count != 0)
{
PathRecord t = Q.Dequeue();
if (t.pathID == pathTable[dest].pathID)
{
return true;
}
else
{
string connectedPaths = pathTable[t.pathID].connectedPathID;
for (int x = 0; x < connectedPaths.Length && connectedPaths != "00"; x = x + 3)
{
int nextNode = Convert.ToInt32(connectedPaths.Substring(x, 2));
PathRecord u = pathTable[nextNode];
if (!u.wasVisited())
{
u.markVisited();
Q.Enqueue(u);
}
}
}
}
return false;
}
このコードは問題なく実行されますが、パスが存在するかどうかしかわかりません。それは私には本当にうまくいきません。理想的には、「if (t.pathID == pathTable[dest].pathID)」というブロックで、どのノードから取得する必要があるかをリストまたは確認する方法が必要です。他の場所で処理するリストを返すのではなく、そこでそれらのノードを処理できるように、ソースと宛先。その変更をどのように行うことができるかについてのアイデアはありますか?