グラフ#グラフ#


学習アルゴリズムは注意力が集中しないので、記録しながら勉強しましょう
数学的により具体的には、グラフィック理論におけるグラフィックとは、オブジェクトのいくつかの対に関連するオブジェクトの集合構造を指す.

化油器経路aka「一筆描く」


すべての幹線の限られた図形に一度にアクセスします.

定義化油器


各頂点に偶数の差がある場合は、一次幹線でターゲットに到達できます.

ハミルトン経路


各頂点に一度にアクセスするアイテムなしまたはアイテム付きグラフィックパス.

ハミルトンサイクル


元の始点に戻るパス

グラフィックループakaグラフィックを参照


各頂点にアクセスするプロセス.

深度優先検索


ほとんどDFSを使っているそうです.
DFSは、主にスタックによって実装または再帰的に実装される.使用後のトレースは優れた効果を示します.

幅優先ブラウズ


BFSは主にキューによって実現される.最短パスの問題を解くために使用します.

グラフィック表示方法


図形を表す方法としては,隣接行列,隣接リストの2種類がある.

隣接リストで表示


上の図を隣接リストとして表示します.以下に示します.
grapth = {
  1: [2,3,4],
  2: [5],
  3: [5],
  4: [],
  5: [6,7],
  6: [],
  7: [3]
}
DFSとBFSで上のディックシャナをブラウズしてみましょう.

深度優先ナビゲーション(DFS)

  • は、エンドポイントに達するまで左側のノードに移動します.1 -> 2 -> 5 -> 6
  • 路地の上で右ノードをチェックし、なければまた上へ行きます.7 -> 3 , 4
  • 再配置されたDFS

    def recursive_dfs(v, discovered=[]):
      discovered.append(v)
      for w in graph[v]:
        if not w in discovered:
          discovered = recursive_dfs(w, discovered)
      return discovered

    スタック実装DFS

    def iterative_dfs(start_v):
      discovered = []
      stack = [start_v]
      while stack:
        v = stack.pop()
      
        if v not in discovered:
          discovered.append(v)
          for w in graph[v]:
            stack.append(w)
      return discovered

    幅優先ナビゲーション

  • 隣接ノードを優先的に探索する.1
  • に隣接ノードがない場合は、左側のサブノードに移動し、隣接ノードを参照します.2 -> 3 -> 4
  • を繰り返します.
  • キュー実装BFS

    def iterative_vfs(start_v):
      discovered = [start_v]
      queue = [start_v]
      while queue:
        v = queue.pop(0)
        for w in graph[v]:
          if w not in discovered:
            discovered.append(w)
            queue.append(w)
      return discovered

    ついせき


    backtrackingは汎用的なアルゴリズムであり,解決策の可能性がないと判断した場合,直ちに候補者(backtracks)を放棄して正解を探すことは,制約満足問題に特に有用である.
    backtrackingは、DFSを扱うときによく出てくる単語です.backtrackingはDFSよりも広い意味を持つ.
    逆追跡の由来は、探索の過程で、これ以上歩けなければ元の道に戻り、別の道を探すからです.
    backtrackingとは、DFSのようにナビゲーションを行うすべての方法であり、DFSはbacktrackingスケルトンを構成するアルゴリズムである.
    backtrackingは主に再帰的に実現され,各アルゴリズムはDFS変形が少し発生し,基本的にDFSの範疇に属する.
    これは体験して諦めなければならない方法であるため、最悪の場合、フルート砲のような性能も生じる.動作も同じです.

    ブルートフォースは上のすべての木をブラウズする必要があります.

    バックトラッキングを用いて,条件が満たされると,下のノードを直接切除する.これを枝切りと言います.

    制約が問題を満たす


    制約満足問題とは,多くの制約条件を満たす状態を見つけ出す数学的問題である.
    遡及は制約が問題を満たすために必要なアルゴリズムを解く.ツリーをトリムすることで、コンストレイントが問題を満たすように最適化できます.
    制約満足問題は人工知能と経営科学の分野でも深く研究されており,合理的な時間内に問題を解決するためにHuriticと組合せ探索などの概念を結びつけて解く.
    制約満足問題とは,数独のように1から9まで1回の数字しか入れない(제약 조건 충족)の正解(상태)を見つけるすべての問題タイプである.
    スドックは後追跡時に枝を剪定することによって最適化される.数独を除いて,十字パズル,8クイーンズ問題,4色問題などのパズル問題やリュックサック問題,文字列交換,組合せ最適化問題などは制約満足問題に属する.