跳到主要內容

臺灣博碩士論文加值系統

(44.200.27.215) 您好!臺灣時間:2024/04/13 16:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳復強
研究生(外文):Ful-Chiang Wu
論文名稱:相信度網路L-S演算法平行處理之研究
論文名稱(外文):L-S Parallel Algorithm for Computating Probability in Belief Network
指導教授:徐旭昇徐旭昇引用關係
指導教授(外文):Chiuh-Cheng Chyu
學位類別:碩士
校院名稱:元智大學
系所名稱:工業工程研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
畢業學年度:81
語文別:中文
論文頁數:38
中文關鍵詞:相信度網路馬可夫性質最大鄰接點搜尋法平行處理
外文關鍵詞:Belief networkMarkov propertyMaximum cardinality searchParallel processing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:138
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
  在無向性圖形上處理機率計算的問題是運用網路圖形結構中所涵蓋的
馬可夫性質,去做一連串局部的運算來減少計算過程。建立在類似無向圖
形結構-Triangulated graph上的演算法(L-S演算法) 能迅速有效的計算
大型稀疏網路的機率計算問題。基本上此演算是透過局部的表示之間的轉
換,運用triangulated graph中所含有的running intersection
property來吸收和傳導資迅。隨著平行處理技術和平行計算機的出現和發
展,為平行計算機上求解問題(即平行計算)創造了條件。在相信度網路上
解決機率計算的問題,利用平行計算的方式,將可達到更高的效率。本論
文的研究目的在於分析無向演算法平行處理之可行性,並且設計出平行處
理的方式,同時做平行演算法計算複雜度的分析。

The purpose of the search is to design a parallel algorithm on
probability computations in belief networks and analyze its
computational complexity. Our study will aim at Lauritzen and
Spiegelhalter's algorithm(undirected mathod). Ross D. Shachter'
s algorithm(directed method) does not fit parallel concept
because it requires creation of barren nodes sequentially.
Pearl's algorithm(directed method) on the case of singly
connected network is well fit to parallel idea,but the
undirected method is aeneralization of his idea and useful for
general sparse networks. Pearl and Shachter proposed the idea
"cut set conditioning" to solve general sparse network but they
didn't discuss algorithmically how to obtain cut sets and
combine computed probabilities with cut sets. The idea is used
by viewing the graphical structure case by case. In this
search, we found that the only graphical operation in
undirected method which can't be parallelized is maximum
cardinality search of which the whole steps must keep in
sequential order. The computational complexity using parallel
concept for all graphical operation of undirected method is
thus O(|V|^2),where |V| is the total number of nodes in a
network. The probability computation is O(maximum clique size)
provided that there are enough parallel processors. We also
present simulation results for the distributions of cliques in
general sparse belief networks,which can be used as a reference
to see what the average time a parallel algorithm will take for
probability computations.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top