99-3週間航行し、1,2,3を加える
1750 ワード
Today I learned
2022/01/24
回顧録
1/24
航行99、アルゴリズム1週目
教材:Pythonアルゴリズムインタビュー
第12章図表
1.理論
バックトラック
太陽を探している間に、現在のパスが太陽ではないように見える場合は、戻りません.
これは、符号化が重複文の数を減らし、効率を向上させることを意味する.
これを枝切りといいます.不要な部分を取り除き、できるだけ正しい方向に進むことを意味します.
通常は、不要な経路を事前に遮断して、状況の数を減らすことができますが、N!の場合、最悪の場合でも指数関数時間が必要になるため、処理できない問題があります.どれだけうまく剪定すれば効率が決まるか.
まとめると、backtrackingは、特定の条件を満たす場合にのみ、可能な限り考慮されます.
すなわち,答えが可能か否かを判断し,そうでなければ探索を行わずに剪定枝を遡及と見なす.
主に、問題解決では、DFSなどを使用して、すべての状況で答えが見つからない場合を定義し、条件文で実装できます.この場合、ブラウズを停止して前の状況に戻り、他の状況でナビゲートすることができます.
👍 ポストトラッキング技術の発展の見通しを確定する
どのノードに希望があるか、すなわちどのノードが有害かを判断し、希望がないと判断した場合、そのノードの前の(親)ノードに戻り、次のサブノードに戻ります.
有害である可能性がある場合を希望(希望)と呼び,到達不可能なノードを剪定(剪定)する.
2.質問
https://www.acmicpc.net/problem/9095
3. MySol Back Tracking この問題はDFSと再帰関数の理解に非常に役立つ問題である. 5.総評
回帰、DFSトレーニング
2022/01/24
回顧録
1/24
航行99、アルゴリズム1週目
教材:Pythonアルゴリズムインタビュー
第12章図表
1.理論
バックトラック
太陽を探している間に、現在のパスが太陽ではないように見える場合は、戻りません.
これは、符号化が重複文の数を減らし、効率を向上させることを意味する.
これを枝切りといいます.不要な部分を取り除き、できるだけ正しい方向に進むことを意味します.
通常は、不要な経路を事前に遮断して、状況の数を減らすことができますが、N!の場合、最悪の場合でも指数関数時間が必要になるため、処理できない問題があります.どれだけうまく剪定すれば効率が決まるか.
まとめると、backtrackingは、特定の条件を満たす場合にのみ、可能な限り考慮されます.
すなわち,答えが可能か否かを判断し,そうでなければ探索を行わずに剪定枝を遡及と見なす.
主に、問題解決では、DFSなどを使用して、すべての状況で答えが見つからない場合を定義し、条件文で実装できます.この場合、ブラウズを停止して前の状況に戻り、他の状況でナビゲートすることができます.
👍 ポストトラッキング技術の発展の見通しを確定する
どのノードに希望があるか、すなわちどのノードが有害かを判断し、希望がないと判断した場合、そのノードの前の(親)ノードに戻り、次のサブノードに戻ります.
有害である可能性がある場合を希望(希望)と呼び,到達不可能なノードを剪定(剪定)する.
2.質問
https://www.acmicpc.net/problem/9095
3. MySol
def is_it_okay(vstd):
tot = sum(vstd)
if tot == n:
return True
else:
return False
def solution(n):
result = []
graph = [1,2,3]
visited = []
stack = []
def dfs_stack(level, path):
stack=[1,2,3]
for adj in stack:
visited.append(adj)
if is_it_okay(visited) :
result.append(visited[:])
visited.pop()
break
else :
dfs_stack(level+1,visited)
visited.pop()
dfs_stack(1,[])
print('result : ' + str(result))
return len(result)
if __name__ == '__main__':
n=4
result = []
result.append(solution(n))
print(str(result))
4.学んだこと回帰、DFSトレーニング
Reference
この問題について(99-3週間航行し、1,2,3を加える), 我々は、より多くの情報をここで見つけました https://velog.io/@jsw4215/항해99-3주차-123-더하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol