トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

Coursera Algorithm - Week1

[アルゴリズム]

Coursera Algorithm - Week1

  Union-Findアルゴリズム

  • Wikipedia - 素集合データ構造
    • 最初の概念はここに書いてありそうかな?
    • と、思いけや詳しいことは書いてないですね
    • このアルゴリズム、3年目ぐらいのとき欲しかった…

SIer的自然言語で説明すると

図を見たほうが早い

Union-Findは、この木構造を構築するためのアルゴリズムと言える。続く3つの方法は構築が遅い順に紹介されている。

dynamic connectivity

愚直に木構造の連結を確認していくやりかた

quick find

  • 木構造の全体の要素数をNとする配列を用意する
  • 木構造を検査して、接続しているもの同士を同じIDで埋める

quick union

一番とっつきやすいかもしれない

  • 木構造の全体の要素数をNとする配列を用意する
  • 木構造を検査して、ある要素の親が存在すればN[i] = 親のIDとする

weighted quick union

基本的にはquick unionと同じだが、木の作成時にできるだけ木構造の高さが大きくなりすぎないように調整する

AOJの例題

ブログに記事としてまとめている

lines = <<'EOS'
10 30
1 3 2
1 0 8
0 6 9
1 1 3
1 8 3
0 6 9
0 7 2
0 0 3
1 2 4
1 1 7
0 4 5
0 4 0
0 4 3
1 0 6
0 1 9
1 5 1
0 4 5
1 0 7
0 3 4
0 0 9
0 6 2
0 3 0
1 9 5
1 9 7
1 7 4
0 9 6
0 3 5
1 6 9
0 2 5
1 8 1
EOS

#lines = $stdin.read

array = lines.split("\n")

n = array[0].split(" ")[0].to_i
q = array[0].split(" ")[1].to_i

it = -1
id = Array.new(n){it+=1}
sn = Array.new(id)

def root(i, id)
  while i != id[i] do
    i = id[i]
  end
  i
end

# find, check if p and q has the same root
def same?(p, q, id)
  root(p, id) == root(q, id)
end

# union, to merge components containing p and q
# set id of p's root to the id of q's root
def unite(p, q, id)
  i = root(p, id)
  j = root(q, id)
  id[i] = j
end

for i in 1..q
  com = array[i].split(" ")[0]
  x   = array[i].split(" ")[1].to_i
  y   = array[i].split(" ")[2].to_i

  if com == '0'
    # unite(4,3) id[4] = 3, 4の頭を3にする
    unite(x, y, id)
  else
    # same
    puts same?(x, y, id) ? "1" : "0"
  end
end

  アルゴリズムのオーダーの話

後でまとめる

  プログラミング問題

  • Percolation いきなり意味わかんねえ…
    • どうやら以下のような碁盤の目(一辺の要素数がNで与えられる)をランダムで埋めて、上から下まで一気通貫できたら Percolation(浸透) らしい
  • Percolation してる図
  • Percolation してない図

maven

  • アルゴリズムはわけわかんないけどMavenはわかるのでリポジトリを使う
    • maven-checkstyle-plugin をコンパイル時に実行している
  <build>
    <finalName>percolation</finalName>

    <plugins>
      <plugin>
        <groupId>org.codehaus.mojo</groupId>
        <artifactId>exec-maven-plugin</artifactId>
        <version>1.2.1</version>
        <configuration>
          <mainClass>Percolation</mainClass>
	  <arguments>
	    <argument>input6.txt</argument>
	  </arguments>
        </configuration>
      </plugin>
      <!-- execute findbugs -->
      <plugin>
	<groupId>org.codehaus.mojo</groupId>
	<artifactId>findbugs-maven-plugin</artifactId>
	<version>3.0.0</version>
	<executions>
          <execution>
            <phase>compile</phase>
            <goals>
              <goal>check</goal>
            </goals>
          </execution>
	</executions>
	<configuration>
	  <includeFilterFile>findbugs-coursera.xml</includeFilterFile>
          <failOnError>true</failOnError>
          <xmlOutput>no</xmlOutput>
          <outputEncoding>UTF-8</outputEncoding>
	</configuration>
      </plugin>
      <!-- execute checkstyle -->
      <plugin>
      	<groupId>org.apache.maven.plugins</groupId>
      	<artifactId>maven-checkstyle-plugin</artifactId>
      	<version>2.17</version>
        <dependencies>
          <dependency>
            <groupId>com.puppycrawl.tools</groupId>
            <artifactId>checkstyle</artifactId>
            <version>6.19</version>
          </dependency>
        </dependencies>
      	<executions>
          <execution>
            <phase>compile</phase>
            <goals>
              <goal>check</goal>
            </goals>
          </execution>
      	</executions>
      	<configuration>
          <configLocation>checkstyle-coursera.xml</configLocation>
          <suppressionsLocation>checkstyle-suppressions.xml</suppressionsLocation>
          <encoding>UTF-8</encoding>
          <consoleOutput>true</consoleOutput>
          <failsOnError>true</failsOnError>
          <linkXRef>false</linkXRef>
      	</configuration>
      </plugin>
      <!-- exclude unnecessary sources -->
      <plugin>
	<groupId>org.apache.maven.plugins</groupId>
	<artifactId>maven-compiler-plugin</artifactId>
	<configuration>
	  <excludes>
	    <exclude>*Visualizer.java</exclude>
	  </excludes>
	</configuration>
      </plugin>
    </plugins>
  </build>

  <dependencies>
    <dependency>
      <groupId>edu.princeton.cs</groupId>
      <artifactId>algs4</artifactId>
      <version>1.0.2</version>
    </dependency>
  </dependencies>

findbugs-maven-plugin

基本的に、配布されているものを使用する findbugs-coursera.xml

checkstyle-maven-plugin

基本的に、配布されているものを使用する checkstyle-coursera.xml が、一部コメントアウトしべし。

  • 以下をコメントアウトしておく、${suppressions} が普通にコンパイルしたとき渡されないので本当に困る
    <!-- suppress certain checks on a file-by-file basis -->
    <!-- the property "suppresions" is passed as a -D command-line option to Java -->
    <module name="SuppressionFilter">
        <property name="file" value="${suppressions}"/>
        <property name="optional" value="true"/>
    </module>

Testing

Possible Progress Steps

 These are purely suggestions for how you might make progress. You do not have to follow these steps.

以下は純粋にどのように進捗していくかについての解き方のヒントです。あなたは以下の段階を踏む必要はない。

 1. Consider not worrying about backwash for your first attempt.
 If you're feeling overwhelmed, don't worry about backwash when following the possible progress steps below.
 You can revise your implementation once you have a better handle on the problem and have solved the problem without handling backwash.

1. 「backwash」については最初は気にしないようにせよ。

  • 以下の参考となる解き方に従ってなおアルゴリズムの難しさに圧倒されてしまった場合でも気にする必要はない
  • 後で実装を改善することが出来るし、問題をうまく扱い、backwashなしに問題を解けるだろう
 2. For each method in Percolation that you must implement (open(), percolates(), etc.), make a list of which WeightedQuickUnionUF methods might be useful for implementing that method.
 This should help solidify what you're attempting to accomplish.

2. あなたはPercolationクラスの全てのメソッドを実装しなくてはならない、WeightedQuickUnionUFクラスの一連のメソッドはこれを実装するのに役立つだろう

  • これはきっとあなたが完遂しようとしていることを固めることの助けになります
 3. Using the list of methods above as a guide, choose instance variables that you'll need to solve the problem.
 Don't overthink this, you can always change them later. Instead, use your list of instance variables to guide your thinking as you follow the steps below,  and make changes to your instance variables as you go. 
 Hint: At minimum, you'll need to store the grid size, which sites are open, and which sites are connected to which other sites.
 The last of these is exactly what the union-find data structure is designed for.

3. 上のガイドにあるような一連のメソッドを使用し、問題を解くために必要なインスタンス変数を選べ

  • 余り考えすぎないで、あなたは後でそれを変更できます。その代わり、以下の段階に従ってあなたの考えをガイドするような一連のインスタンス変数を使用してください、そして思うままにインスタンス変数に変更を加えてください
  • ヒント:最低限、あなたは格子のサイズを保持する必要がある、このサイズはどの枠(site)がオープンになっているかを示し、他の枠(site)と繋がっている
  • これらの最後のものはまさにunion-findのデータ構造として設計されたものだ
 4. Plan how you're going to map from a 2-dimensional (row, column) pair to a 1-dimensional union find object index. 
 You will need to come up with a scheme for uniquely mapping 2D coordinates to 1D coordinates.
 We recommend writing a private method with a signature along the lines of int xyTo1D(int, int) that performs this conversion.
 You will need to utilize the percolation grid size when writing this method.
 Writing such a private method (instead of copying and pasting a conversion formula multiple times throughout your code) will greatly improve the readability and maintainability of your code.
 In general, we encourage you to write such modules wherever possible. Directly test this method using the main() function of Percolation.

4. どのようにして、2次元のpair型のデータ(行、列)から1次元のunion-find型のオブジェクト配列に変換を行うか考えなさい

  • あなたは2次元データを一意に1次元にマッピングする方法を思いつく必要があるでしょう
  • ここではxyTo1D(int, int)のような型をもったプライベートメソッドを書き、この変換をおこなうことをおすすめします
  • このメソッドを書く時はPercolation格子のサイズを利用する必要があるでしょう
  • このようなプライベートメソッドを書くと、あなたのコードの保守性と可読性はすごく向上するでしょう
  • 一般的に、わたしどもはあなたが出来る限りそのようなモジュールを書くことを推奨します。平たく言えば、このメソッドをmain関数から呼び出してテストしてください。
 5. Write a private method for validating indices.
 Since each method is supposed to throw an exception for invalid indices, you should write a private method which performs this validation process.

5. インデックス値を検証するためのプライベートメソッドを書きなさい

  • 各メソッドは不正なインデックス値に例外を投げることが想定されているので、あなたはこの検証処理を行うプライベートメソッドを書く必要がある
 6. Write the open() method and the Percolation() constructor.
 The open() method should do three things.
 First, it should validate the indices of the site that it receives.
 Second, it should somehow mark the site as open.
 Third, it should perform some sequence of WeightedQuickUnionUF operations that links the site in question to its open neighbors.
 The constructor and instance variables should facilitate the open() method's ability to do its job.

6. open()メソッドとPercolationのコンストラクタを書きなさい

  • open()メソッドは以下の3つのことをすべきです
    • 1.受け取った枠(site)のインデックス情報を検証する
    • 2.どうにかして枠(site)がオープンであることを記録する
    • 3.オープンになっている隣の枠(site)に対して繋がっているかどうか問う操作をWeightedQuickUnionUFクラスの一連の操作で行う
  • コンストラクタとインスタンス変数はopen()メソッドの処理を行うための能力を容易にするでしょう
 7. Test the open() method and the Percolation() constructor. 
 These tests should be in main().
 An example of a simple test is to call open(1, 1) and open(1, 2), and then to ensure that the two corresponding entries are connected (using .connected() in WeightedQuickUnionUF).

7. open()メソッドとPercolationのコンストラクタをテストしなさい

  • 単純なテストの例としては open(1,1) や open(1,2)、そして2つの関係するエントリが繋がったかどうか確かめることです(これもWeightedQuickUnionUF#connectedを使用する)
 8. Write the percolates(), isOpen(), and isFull() methods.
 These should be very simple methods.

8. percolates(), isOpen(), isFull() のメソッドを書きなさい

  • これらは単純なメソッドであるべきです
 9. Test your complete implementation using the visualization clients.

9. 完全な実装をvisualization clientsでテストしなさい

 10. Write and test the PercolationStats class.

10. PercolationStatsクラスを書いてテストしなさい

目論見

  • PercolationのAPI
public class Percolation {
   public Percolation(int n)                       // create n-by-n grid, with all sites blocked
   public    void open(int row, int col)       // open site (row, col) if it is not open already
   public boolean isOpen(int row, int col)  // is site (row, col) open?
   public boolean isFull(int row, int col)     // is site (row, col) full?
   public     int numberOfOpenSites()       // number of open sites
   public boolean percolates()                // does the system percolate?

   public static void main(String[] args)     // test client (optional)
}
  • 一辺がN個ある枠なので、すべての要素を数えるとN^2になるはず
    • ただし、授業で言われているように、正方形の上辺と下辺の両側にそれぞれ仮想の要素を用意したほうがよさそう(よって+2)

だから、コンストラクタはこうなるか?

    /////////////////////////////////////////////////
    // Union-Find...
    /////////////////////////////////////////////////
    private WeightedQuickUnionUF qu;
    /////////////////////////////////////////////////

    public Percolation(int n) {
        // create n-by-n grid, with all sites blocked
        qu = new WeightedQuickUnionUF(n*n+2);
        StdOut.printf ("Create n^2 = %d sites\n", qu.count());
        StdOut.println("Index is 0 to " + (n*n+1));
    }
  • 2次元のpair型のデータ(行、列)から1次元のunion-find型のオブジェクト配列に変換
    • こんな感じでいいだろうか
    private int xyTo1D(int row, int col) {
	int square = qu.count() - 2;
	int side   = (int) Math.sqrt(square);
	int index  = side * (row-1) + col;
        StdOut.printf("There are %d sites = %d^2\n", square, side);
	StdOut.printf("(%d, %d) conv to %d \n", row, col, index);
	return index;
    }
  • quick-unionのアルゴリズム自体は WeightedQuickUnionUF にて提供されるのでそれを使う
  • もし、openな要素が現れたら、その仮想の要素と繋がっていることとする