【転載】FloodFillアルゴリズムの最適化
1581 ワード
FLoodFillアルゴリズムの名前は「洪水充填アルゴリズム」で、ネット上で見た解釈によると、たぶんアクセスできるポイントを見つけてDFSかBFSを行いますが、DFSでは効率が悪いようで、BFSは書きにくいので、DFSかBFSを直接行ったほうがいいですね.そこでもう一つの実装方法を考えましたが、FloodFillの具体的な実装もよく分からないので、このアルゴリズムは少し似ているかもしれません.
このアルゴリズムは、複数のインターフェースブロックを絶えず拡張して探すことができるが、複数のインターフェースブロックを維持するために使用し、セットを調べる必要がある可能性があるので、少し面倒かもしれない.一方、1つのインターフェースブロックしか見つからないコードは基礎とすることができ、対応する複数のインターフェースブロックも書きにくくない.この最適化はDFSとBFSに比べて最大の利点はO(N!)からである.左右の複雑さはO(n^2)に低下し,メモリスペースをほとんど消費せず定数は比較的小さく,BFSより何倍も書きやすくなった.
この最適化アルゴリズムの基本思想は,まず図全体を二重サイクルで遍歴し,遍歴したノードの横に遍歴したノードがあれば自動的に連通することである.
const int MAXN = 1001;const int dx[] = {1,0,-1,0};const int dy[] = {0,1,0,-1};int N;//図の大きさbool Graph[MAXN][MAXN];bool isGo[MAXN][MAXN];for(int i=0;i!=N;++i){for(int j=0;j!=N;++j){for(int k=0;k!=4;++k){if(isGo[i+dx[k]][j+dy[k]&&Graph[i+dx[k]][j+dy[k]){//相応のことをする}}isGo[i][j]=true;}}
このアルゴリズムの時間的複雑さは確かにO(n^2)であるが,さらに最適化できる.例えば、私たちは今、検索を開始した点、すなわち、インターコネクトブロックの最初の点(左上の点)を知っています.これは、隣の点に1行の点が触れていない場合にアクセスしたことがある場合は、直接breakを出てもいいです.そうすると、次には接続できる点はありません.
しかし、このような状況を考えると、その図はこうです.(1は歩ける、0は歩けない)
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
これで明らかに最適化できるが,最悪の複雑度O(n^2)に達し,途中で退出することはできない.
そこで,行列連合FloodFillと呼ばれるアルゴリズムを研究した.名前の通り、列と行を交差して検索し、連続して検索できない場合はそのまま停止します.もちろん、直接スキャンすると、一定の重複があるため、カラムとローのアクセス長を絶えず削減し、所望の平均最適化を達成することができます.
よくわかりますよね?だから、これは私が研究したFloodFillアルゴリズムの効率的な実現です(何の役にも立たないかもしれませんが).
このアルゴリズムは、複数のインターフェースブロックを絶えず拡張して探すことができるが、複数のインターフェースブロックを維持するために使用し、セットを調べる必要がある可能性があるので、少し面倒かもしれない.一方、1つのインターフェースブロックしか見つからないコードは基礎とすることができ、対応する複数のインターフェースブロックも書きにくくない.この最適化はDFSとBFSに比べて最大の利点はO(N!)からである.左右の複雑さはO(n^2)に低下し,メモリスペースをほとんど消費せず定数は比較的小さく,BFSより何倍も書きやすくなった.
この最適化アルゴリズムの基本思想は,まず図全体を二重サイクルで遍歴し,遍歴したノードの横に遍歴したノードがあれば自動的に連通することである.
const int MAXN = 1001;const int dx[] = {1,0,-1,0};const int dy[] = {0,1,0,-1};int N;//図の大きさbool Graph[MAXN][MAXN];bool isGo[MAXN][MAXN];for(int i=0;i!=N;++i){for(int j=0;j!=N;++j){for(int k=0;k!=4;++k){if(isGo[i+dx[k]][j+dy[k]&&Graph[i+dx[k]][j+dy[k]){//相応のことをする}}isGo[i][j]=true;}}
このアルゴリズムの時間的複雑さは確かにO(n^2)であるが,さらに最適化できる.例えば、私たちは今、検索を開始した点、すなわち、インターコネクトブロックの最初の点(左上の点)を知っています.これは、隣の点に1行の点が触れていない場合にアクセスしたことがある場合は、直接breakを出てもいいです.そうすると、次には接続できる点はありません.
しかし、このような状況を考えると、その図はこうです.(1は歩ける、0は歩けない)
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
これで明らかに最適化できるが,最悪の複雑度O(n^2)に達し,途中で退出することはできない.
そこで,行列連合FloodFillと呼ばれるアルゴリズムを研究した.名前の通り、列と行を交差して検索し、連続して検索できない場合はそのまま停止します.もちろん、直接スキャンすると、一定の重複があるため、カラムとローのアクセス長を絶えず削減し、所望の平均最適化を達成することができます.
よくわかりますよね?だから、これは私が研究したFloodFillアルゴリズムの効率的な実現です(何の役にも立たないかもしれませんが).