位相整列

위키百科, 우리 모두의 百科事典.

位相 整列 (topological sorting)은 有香 그래프 의 꼭짓點들(vertex)을 邊의 方向을 거스르지 않도록 羅列하는 것을 意味한다. 位相整列을 가장 잘 說明해 줄 수 있는 例로 大學의 選手科目(prerequisite) 構造를 例로 들 수 있다. 萬若 特定 受講科目에 選手科目이 있다면 그 選手 科目부터 受講해야 하므로, 特定 科目들을 受講해야 할 때 位相 整列을 통해 올바른 受講 順序를 찾아낼 수 있다. 이와 같이 先後 關係가 定義된 그래프 救助 床에서 先後 關係에 따라 整列하기 爲해 位相 整列을 利用할 수 있다. 整列의 順序는 有香 그래프 의 構造에 따라 여러 個의 種類가 나올 수 있다. 位相 整列이 成立하기 위해서는 반드시 그래프 의 循環 이 存在하지 않아야 한다. 卽, 그래프가 非循環 有香 그래프 (directed acyclic graph)여야 한다.

一般的인 位相 整列의 適用은 主로 業務의 日程을 일어나야 할 順序에 따라 配置하기 위하는 것으로, 이 알고리즘은 프로젝트 管理 技法을 評價 및 分析하기 위한 技法(PERT)에 適用하기 위한 目的을 위해 1960年代 初盤부터 硏究되었다 (Jarnagin 1960). 이 때, 該當 業務는 꼭짓點 으로 表現되었고, 各 꼭짓點을 連結하는 辯은 該當 業務 間의 先後 關係를 表現하였다. 假令, 옷을 다리기 爲한 業務는 반드시 옷을 洗濯機에 돌리는 業務 뒤에 配置되어야 한다. 이와 같이, 位相整列은 各 業務를 遂行하기 위한 順序를 提供하였다.

Topological sorting(位相 整列)은 컴퓨터 科學에서, 方向 그래프의 位相 整列 또는 位相 配置는 頂點의 線形 順序이다. 꼭짓點 u에서 꼭짓點 v로의 모든 方向 꼭짓點 uv는 v의 順序 前에 u가 오는 것이다. 例를 들어, 그래프의 꼭짓點은 아마 遂行하는 일은 代表한다. 그리고 꼭짓點은 어떤 일이 다른 것보다 먼저 遂行되어야 하는 許可되지 않은 것을 代表한다. 이러한 것에서, 位相 配列은 일의 有用한 順序에 不過하다. 正確히 位相 整列은 모든 從屬性을 訪問한 後에만 各 노드 v를 訪問하는 그래프 循環이다. 位相 配列은 可能하다. 正말 萬若에 그래프 方向이 없는 循環이라면, 아마 그것은 方向 循環 그래프(DAG)일 것이다. 어떤 DAG는 最小 하나의 位相 配列을 가지고 있다. 그리고 알고리즘은 어떤 DAG 속 線形 時間의 位相 配列이 構成한다고 알려져 있다. 位相 整列은 feedback arc set 와 같은 랭킹 問題를 解決하는데 많이 使用된다. 位相 整列은 甚至於 DAG의 要素가 連結되지 않을지라도 可能하다.

位相整列의 遂行過程 [ 編輯 ]

  1. 自己 自身을 가리키는 變이 없는 꼭짓點을 찾음.
  2. 찾은 꼭짓點을 出力하고 出力한 꼭짓點과 그 꼭짓點에서 出發하는 變을 削除
  3. 아직 그래프에 꼭짓點이 남아있으면 段階 1로 돌아가고, 아니면 알고리즘을 終了시킨다.

例示 [ 編輯 ]

位相 整列의 基本 適用은 그들의 從屬性을 基盤으爐하여 일 또는 職業의 連續된 日程에 있다. 이 일은 꼭짓點에 對해 대표된다. 그리고 x로부터 y로의 모서리가 있다. 萬若 日 x가 日 y가 始作하기 前에 끝났다.그런 다음, 位相 整列은 일을 遂行한 順序를 준다. 가까운 관계된 位相 整列 알고리즘의 適用은 1960年에 프로젝트 管理에서 스케줄링을 위한 PERT 技術의 脈絡에서 처음으로 學習한다. 이러한 適用은, 그래프의 꼭짓點을 代表한다. 프로젝트의 重要한 段階와 모서리는 하나의 重要한 段階와 다른 것 사이 遂行된 일을 代表한다. 位相 整列은 프로젝트의 致命的인 方法을 찾기 위해 線形 時間 알고리즘으로부터 왔다. 重要한 일의 連續은 綜合的인 日程의 길이를 統制한다.

컴퓨터 科學에서, 이러한 類型의 適用은 日程을 構成하면서 發生한다. 細胞 鎭火 公式의 順序는 스프레드 시트나 綜合 論理를 다시 公式을 計算한 價値가 있을 때, 生成 파일에서 일을 完璧히 遂行하는 것을 決定한다. 데이터 直列火, 그리고 되풀이 象徵은 링커들에 달려있다. 또한 데이터 베이스에서 外來 키가 있는 테이블을 가져오는 順序를 決定하는데 使用된다.

왼쪽의 그래프는 많은 有用한 位相 整列을 보여준다.
  • 5, 7, 3, 11, 8, 2, 9, 10 ( 맨 위에서 왼쪽에서 오른쪽으로 아래까지 )
  • 3, 5, 7, 8, 11, 2, 9, 10 ( 第一 작은 數부터 利用 可能한 첫 꼭짓點까지 )
  • 5, 7, 3, 8, 11, 10, 9, 2 ( 왼쪽 맨 위를 처음으로 )
  • 7, 5, 11, 3, 10, 8, 9, 2 ( 가장 큰 數부터 利用 可能한 첫 꼭짓點까지 )
  • 7, 5, 11, 2, 3, 8, 9, 10 ( 맨 위부터 왼쪽에서 오른쪽으로 試圖하여 아래까지 )
  • 3, 7, 8, 5, 11, 10, 2, 9 ( 제멋대로 )

알고리즘 [ 編輯 ]

位相 整列의 一般的인 알고리즘은 꼭짓點의 羊水 노드의 線形 實行 時間을 가진다.

Kahn의 알고리즘 [ 編輯 ] 

 Kuhn의 알고리즘과 헷갈리지 않도록 注意!

位相 整列 알고리즘 中 하나이다. Kahn에 依해 1962年에 처음으로 言及되었다. 窮極的인 位相 整列로써 같은 順序 속에 일은 꼭짓點에 依해 選擇된다. 처음으로, “始作 노드”를 찾는다. 꼭짓點과 連結되지 않고, S集合에 連結되어 있는; 적어도 하나의 노드는 비어있지 않은 循環 그래프 안에 存在한다.

L ← Empty list that will contain the sorted elements 

S
 ← Set of all nodes with no incoming edge

while
 S
 is not
 empty 
do

    remove a node 
n
 from 
S

    add 
n
 to 
L

    for each
 node 
m
 with an edge 
e
 from 
n
 to 
m
 do

        remove edge 
e
 from the graph
        
if
 m
 has no other incoming edges 
then

            insert 
m
 into 
S


if
 graph
 has edges 
then

    return
 error   
(graph has at least one cycle)

else

    return
 L
   (a topologically sorted order)

萬若 그래프가 DAG라면, 解決策은 L 리스트(解決策은 특별한 것이 必要 없다.) 안에서 抑制하는 것이다. 마찬가지로, 그래프는 적어도 하나의 循環을 가지고 있어야 한다. 그러므로 位相 整列은 不可能하다. 結果的으로 整列의 특별하지 않은 것을 反映하여, 構造 S는 Set 또는 queue 또는 stack으로 簡單化 할 수 있다. 順序에 依해, 노드 n들은 集合 S로부터 除去된다. 그리고 다른 解決策을 生成한다. kahn의 알고리즘의 變形은 연병렬 스케줄링 및 階層 그래프 그리기를 위한 Coffman-Graham 알고리즘의 核心 構成 要素를 辭典式으로 連結을 끊는다.

깊이 于先 探索 [ 編輯 ]

位相 整列의 代替 可能한 代案 알고리즘은 깊이 于先 探索을 基盤으로 한다. 알고리즘의 任意的인 順序 속 그래프의 各 노드를 통한 루트는 그것이 이미 始作 以後로 거쳐간 노드의 位相 整列 또는 꼭짓點을 가지지 않은 다른 노드를 건들 때 着手한 깊이 于先 探索이 除去한다. 

L
 ← Empty list that will contain the sorted nodes
while
 exists nodes without a permanent mark 
do

    select an unmarked node 
n

    visit(
n
)

function
 visit(node 
n
)
    
if
 n
 has a permanent mark 
then

        return

    if
 n
 has a temporary mark 
then

        stop
   (not a DAG)


    mark 
n
 with a temporary mark

    for each
 node 
m
 with an edge from 
n
 to 
m
 do

        visit(
m
)

    remove temporary mark from 
n

    mark 
n
 with a permanent mark
    add 
n
 to head of 
L

各 노드 n은 出力 리스트 L에서 모든 다른 노드를 考慮한 後에 n에 依存한다. 特히 알고리즘이 노드 n을 追加할 때, 우리는 모든 노드가 n에 依存한다는 것을 保障하는 것은 이미 出力 리스트 L에 있다는 것이다. : 그들은 되풀이 되는 訪問 呼出에 依해 n에 訪問하기 前에 끝나거나, n이 呼出되기 前에 끝나는 것 둘 다 L에 追加한다. 各 꼭짓點과 노드가 하나를 訪問한 以來로, 알고리즘은 線形 時間에서 實行한다. 그리고 깊이 于先 探索의 基礎 알고리즘은 Cormen et al에 依해 2001年에 만들어진다. 그것은 1976年 Tarjan 印刷에서 처음 만들어져 온 것처럼 보인다.

Parallel 알고리즘 [ 編輯 ]

Parallel의 랜덤 接續 機械에 依하면, 位相 配置는 O (log 2 n ) 時間 안에 多數의 프로세서를 使用해 構成할 수 있다. 問題 속 複雜한 클래스 NC 2 ' . [1] 을 넣는다. 이를 遂行하는 한 가지 方法은 주어진 그래프, 論理的 時間의 隣接 行列을 反復的으로 제곱하는 것이다. 結果 行列은 가장 긴 길이가 그래프에서 줄어들게 만든다. 꼭짓點을 整列하는 것은 그들의 가장 긴 方法의 길이에 依해 位相 配置를 生成한다.

最短 거리 찾기에서 適用 [ 編輯 ]

位相 配置는 亦是 길이의 DAG를 通해서 最短 距離를 빠르게 計算하는데 使用된다. V를 토폴로지 順序로 이러한 그래프의 頂點 目錄이라고 하자. 그런 다음 알고리즘을 따라 最短 距離를 計算한다.

틀:Framebox

  • d 를 V 와 같은 길이의 配列이라고 하자. 이것은 s 에서 最短 經路 距離를 維持한다. d [ s ] = 0 , d [ u ] = ∞ .
  • p 를 V 와 同一한 길이의 配列로, 모든 要素는 nil 로 初期化한다. 各 p [ u ] 는 s 에서 u 까지의 最短 經路에서 u 의 善行者를 保有한다.
  • s 에서 始作하여 V 에서 順序대로 頂點 u 를 反復한다. :
    • u 바로 뒤에 오는 各 꼭짓點 v 에 對해 (卽, u 에서 v 까지의 幹線이 存在한다.):
      • w 를 u 에서 v 까지의 幹線의 加重値라고 하자.
      • 가장자리를 풀다. : if d [ v ] > d [ u ] + w , set
        • d [ v ] ← d [ u ] + w ,
        • p [ v ] ← u .

틀:Frame-footer

그래프의 n 꼭짓點과 m 꼭짓點에서, 이 알고리즘은 O( n + m ) . 卽, 線形 時間에 實行이 된다.

獨特한 點 [ 編輯 ]

萬若 位相 整列이 모든 連續된 꼭짓點을 모서리가 連結된 整列 排置에서 所有한다면, DAG 속 Hamiltonian path로부터 모서리이다. 萬若 Hamiltonian path가 存在한다면, 位相 整列 配置는 獨特한 것이다; 다른 모서리의 길 配置는 考慮하지 않는다. 正反對로, 萬若 位相 整列이 Halmiltonian path로부터 온 것이 아니라면, DAG는 두 가지 또는 더 많은 種類의 位相 配置를 가질 것이다. 이러한 境遇 이것은 恒常 두 連續된 點이 各各 連結되지 않는 것이 可能하다. 그러므로, 그것은 線形 時間에서 獨特한 配置가 存在하던 아니던, 그리고 Hamiltonian path가 存在하던 아니던, 보다 一般的인 方向 그래프에 對한 Hamiltonian path 問題의 NP經度에도 不拘하고 테스트가 可能하다.( 卽, 循環 그래프이다. )

各州 [ 編輯 ]

  1. ↑ Cook, Stephen A. (1985), “A Taxonomy of Problems with Fast Parallel Algorithms”, 《Information and Control》 64 (1?3): 2?22, doi : 10.1016/S0019-9958(85)80041-3  
元本 住所 " https://ko.wikipedia.org/w/index.php?title=位相整列&oldid=32380638 "