tag:blogger.com,1999:blog-7668940394932586677.post3064837674625735182..comments2010-08-04T22:12:30.919+09:00Comments on さむしんぐあずあめも。: Google DevFest 2010 パッチワーク問題を解いてみたAnonymoushttp://www.blogger.com/profile/17682850078090291459noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-7668940394932586677.post-64143139799033428882010-03-16T03:22:33.369+09:002010-03-16T03:22:33.369+09:00Union-Findアルゴリズムは、単一のrootの要素を作ること、treeに属する要素のrootを...Union-Findアルゴリズムは、単一のrootの要素を作ること、treeに属する要素のrootをたどること、たどったroot同士を比較することでそれらが同じグループ(tree)に属しているか判定することを、素早くできるのが特徴です。<br />上記のプログラムでは、パッチワークの並び(Element)を最初はすべてrootだけからなる1個ずつのグループ(tree)として作成し、1つずつ隣同士を比較して、同じTypeであればtreeを結合して一つのグループ(tree)にするということをしています。<br />それを実際にやっているのがcompare(Element, Element)メソッドです。二つのElementのTypeが等しいとき、それぞれに対してfind()メソッドを呼び、各々のElementが所属しているtreeのroot Elementを取得します。root Elementが共通であれば、それらはすでに同じグループ(tree)に属しているので何もしません。異なっていれば、片方のtreeをもう片方のtreeの要素に組み入れる(union)ことで、それらを同じグループ(同じrootを持つtree)にします。<br />したがって最初の質問に対する答えは、compareメソッドの2つの引数が直接指しているのはある隣同士のElementですが、中でそれぞれのrootを取得することで実際に扱っているのは両方とも集合(tree)になります。<br />2つめの質問のtree同士を比較すると言うのは、おそらく上記のtreeのrootを比較することで同じtreeかどうかを判定することを指していると思います。Anonymoushttps://www.blogger.com/profile/17682850078090291459noreply@blogger.comtag:blogger.com,1999:blog-7668940394932586677.post-90770811984106680472010-03-16T01:08:27.724+09:002010-03-16T01:08:27.724+09:00http://bit.ly/ajS0vh
ここにでてくるUnionFindをよんでみたんだけど,tr...http://bit.ly/ajS0vh<br />ここにでてくるUnionFindをよんでみたんだけど,treeと要素ではなく,tree同士を比較するってのが,このパッチワーク問題にどう当てはめるのかわからんかったです.<br />教えてください.Anonymoushttps://www.blogger.com/profile/17792862882377059453noreply@blogger.comtag:blogger.com,1999:blog-7668940394932586677.post-64319157748268631702010-03-16T00:59:47.233+09:002010-03-16T00:59:47.233+09:00UnionFindを適応してるほうの,compare(Element thisElement, El...UnionFindを適応してるほうの,compare(Element thisElement, Element otherElement)の片方って要素じゃなくて集合ではいってくるの?Anonymoushttps://www.blogger.com/profile/17792862882377059453noreply@blogger.com