[SW将校学校ジャングル]WEEK 01開発ログ-IV

フルナビゲーション

Broot-Posアルゴリズム
ブルートフォスアルゴリズムは、オブジェクトのソース文字列を順番に検索し、文字を1つずつ比較する方法で検索する固定アルゴリズムです.比較する文字列とパターンを1つずつ移動し、一致するかどうかを確認します.
Broot-Posアルゴリズム比較プロセス
T:ソース文字列、P:検索する文字列パターン

T、Pはいずれも最初の文字から比較されるので、検索インデックスは最初のインデックスに設定される.

各

の検索インデックスから文字を1つずつ比較します.
①文字を比較しながら、T、Pインデックスを1つ後ろに移動します.
②比較文字が異なる場合、Tのインデックスは後ろにスペースを移動し、Pのインデックスは最初のインデックスに戻る.

ステップ

を繰り返し、2番目のプロシージャから検索終了までを実行します.

Broot-Posアルゴリズムの時間的複雑さと利点と欠点

時間複雑度:O(mn)

検索する文字列パターン長m、文字列全長n

の利点:実現しやすく、100%の確率で正解を出力します.

欠点:

:すべての資料を探索し、時間的に非常に非効率である.

브루트-포스 알고리즘 구현

def bruteForce(p, t):
    i = 0 # t의 검색 인덱스
    j = 0 # p의 검색 인덱스
    while i < len(t) and j < len(p):
        if t[i] != p[j]:
            i -= j
            j = -1
        j += 1
        j += 1
    if j == len(p):
        return i - len(p)
    else:
        return -1

ついせき

任意の数のアルゴリズム

を検索する
遡及は木型資料構造における図形探索の変形である.ほとんどの遡及アルゴリズムは深さ優先探索(Depth First Search)の形式を有する.すべての場合の深さ優先探索とは異なり,逆追跡が不可能であると考えられるノードを排除した.すなわち、危害を及ぼす可能性がある場合にのみ、そのノードに所望のサブノードがあるか否かを検査する.

特定の集合(集合)において、ある基準(標準)を満たす要素の順序(シーケンス)を選択するアルゴリズム

.
また、backtrackingでは、各要素に順次アクセスし、基準を満たしているかどうかを確認します.従って,数列や数列と組合せ問題を解く方法となる.
ぎゃくトラッキングぎじゅつ

ステータス空間ツリー
遡及にはステータス空間ツリーがあります.状態空間は答えを探索するための探索空間であり,状態空間ツリーは探索空間を木の形で黙々と解釈している.無名の解釈なので、一般的な配列を開いて、それに近いと考えられます.

深度優先ナビゲーション(DFS)
深度優先探索は,その名の通り,まず図形の最大深度を探索し,次に前の分岐点に戻って探索を継続する探索方法である.幅優先探索(Breadth First Search)は、これとは反対に、開始頂点に隣接するすべての頂点に優先的にアクセスする探索方法である.

백트래킹 구현

void backtracking(int index){
    if(index==n){		# 탈출 조건
        return;
    }
    if(isPromising()){
        visited[index] = true;	# 상태변화
        backtracking(index+1);	# 재귀호출
        visited[index] = false;	# 상태복구
    }
}

bool isPromising(int index){	# 유망함수
    if(non-promising)
        return false;
    if(promising)
        return true;
}

完全ナビゲーションの標準問題Githubリンク
百俊は関連問題を完全に探求した。