最大10,000 ノードのグラフがあり、各ノードは最大4 つの隣接ノードを持つことができます。グラフは重み付けされておらず、無向です。タスクは、ノード A からノード B への最短パスを見つけることです。パスの長さは、パスで訪れたノードの数です。BFS アルゴリズムは、そのパスを1 秒未満で、 64 MB未満のメモリを使用して見つけることができますか?
元の問題は、グリッド (最大 100*100) と、訪問できる場所、開始場所、終了場所、および訪問できない場所です。私の最初の推測は、BFS 検索を使用して重み付けされていないグラフで最短経路を見つけることです。しかし、大きなグラフを使用したそのソリューションの速度とメモリ使用量についてはわかりません。
スペースの複雑さ
したがって、10,000 個のノードがあり、各ノードは最大 4 つの他のノードに接続できます。頂点の最大数は 40 000 です。隣接リストO(|V|+|E|)=50 000では、メモリにスペースが必要です。各変数は、リストでそれを表すために 32 ビットを必要とします。最大メモリ量は40000*32/(1000*1000*8)=0.16M バイトです。隣接行列が使用される場合、Mbytes が必要になりますO(|V|^2)=40000*40000/(1000*1000*8)=200。
時間の複雑さ
ウィキペディア:
最悪の場合、すべての頂点とすべてのエッジが探索されるため、時間計算量は O(|V|+|E|) として表すことができます。注: O(|E|) は O(|V|) と O(|V|^2) の間で変化する可能性があり、これは入力グラフがどの程度まばらであるかによって異なります (グラフが接続されていると仮定)。
したがって、最悪の場合、時間計算量は になりますO(|V|+|E|) = 40 000 + 10 000 = 50 000。最新のコンピューターでは、1 秒未満で計算されることは問題になりません。
1秒は私見です（0.001秒に似ています-最新のコンピューターでは10 ^ 9操作/秒）。
メモリ -- 隣接リスト表現配列 int[10000][4] + 閉じている/使用されている/見えないノード >= 10000*4*6 = 240000 = 0.24MB が必要です。私の数学が大丈夫なら、それは問題ないはずです。