Approach

(1)Greedy:妥当性の検証
(2)DP:最適な局所構造、局所問題の繰り返し
(2)Divide&Conquer:最適なローカル構造のみで、特定の条件を満たす最適値?
(2)パラメータ探索:決定関数二分化,条件関数単調関数
(3)DFS:すべてのパスをブラウズし,スタック方式で実装する.
(3)BFS:最短距離ナビゲーション、ステップポイントナビゲーション、キュー実装

1. Greedy

グリディアルゴリズム(貪欲法)は、現在の状況で良いものだけを選択する方法を意味する.

従来の階調アルゴリズムは、最も少ない解題構想を考え出すことができることを要求している.

対応アルゴリズムでは,その正当性解析が重要である.

単純に最良のものを繰り返し選択し、最良の年が見つかるかどうかも検討する.

コットでは、ほとんどのグリディ問題は貪欲法が得た年が最良の年になった場合、推論してこそ解決できる.

ex)小銭問題

マルチアウトレット最短パスアルゴリズム

特定のノードから他のすべてのノードへの最短パスを計算します.

多出口最短経路アルゴリズムは、負の幹線がない場合に正常に動作する.

現実世界の道路(幹線)は負の幹線として表現されない.

マルチ出口最短経路アルゴリズムはGRIDアルゴリズムに分類される.

ページの場合、最もコストの低いノードを選択し、任意のプロセスを繰り返します.

アルゴリズムの動作過程は以下の通りである.

出発ノードを設定します.

最短距離テーブルを初期化します.

がアクセスしていないノードで、最短距離で最も短いノードを選択します.(グリディアルゴリズム)

は、ノードを介して他のノードへのコストを計算し、最短パステーブルを更新する.

ビットでは、3回と4回繰り返します.

アルゴリズムの特徴は以下の通りである.

グリディアルゴリズム:いずれの場合も、アクセスしたことのない最もコストの低いノードを選択し、任意のプロセスを繰り返します.

段階を経て、一度処理されたノードの最短距離は一定に保たれる.
各ステップは、ノードの最短距離を見つける必要があると理解できます.

マルチアウトアルゴリズムが完了すると、各ノードの最短距離情報がテーブルに格納される.

の完全な形式の最短パスを得るには、ソースコードにより多くの機能を追加する必要があります.

共O(V)O(V)O(V)回,最短距離が最も短いノードを線形に探索する.

従って,時間全体の複雑さはO(V 2)O(V^2)O(V 2)であった.

は、通常、符号化試験の最短パス問題において、総ノード数が5000個未満である場合、このコードを使用して問題を解決することができる.

2.実施（完全ナビゲーション、シミュレーション）

フルナビゲーション:すべての場合、データの合計数が100万個を超えないと判断する必要がある場合は、迷わずすべての数のソリューションを計算できます<-OK(ナビゲーション)

シミュレーション:問題タイプ

は、提案されたアルゴリズムを一歩一歩実行する必要がある

ex)アルゴリズムは簡単ですが、コードが長すぎる問題

ex)実数演算に関し、特定の小数位数に出力する必要があるという問題

.

ex)文字列が特定の基準で切断する必要がある問題

.

ex)適切なライブラリの検索と使用が必要な問題

ex)すべてのシーケンスと組合せを検索する必要がある問題

シミュレーションおよび完全探索問題では,二次元空間における方向バックがしばしば用いられる.

// 동, 북, 서, 남
dx = {0, -1, 0, 1}; // 행
dy = {1, 0, -1, 0}; // 열

// 현재 위치
x, y = 2, 2

for (i = 0; i < 4; ++i)
{
	// 다음 위치 // 동북서남 탐색
	nx = x + dx[i];
	ny = y + dy[i]
	print(nx, ny);
}