ALGORITMA DIVIDE AND CONQUER PADA JAVA



ALGORITMA DIVIDE AND CONQUER

Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

1. Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
2. Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
3. Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif (perulangan dengan memanggil dirinya sendiri). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif. Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer  yaitu merge sort, insert sort, quick sort dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute force.

PENERAPAN ALGORITMA DIVIDE AND CONQUER

Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer

Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma Divide and Conquer, hal ini dapat dipandang sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya :

1. Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).
2. Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).
3. Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.
4. Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).
5. Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung dan mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.

Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition) dan penelitian operasi. Divide and Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.
Algoritma Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain itu juga, algoritma ini dapat digeneralisasi untuk permasalahan convex hull yang berdimensi lebih dari 3.

Penyelesaian dengan Algoritma Divide and Conquer :

1. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).
2. Algoritma Closest Pair :
a. SOLVE : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Euclidean.
b. DIVIDE : Bagi titik-titik itu ke dalam dua bagian, PLeft dan PRight, setiap bagian mempunyai jumlah titik yang sama.
c. CONQUER : Secara rekursif, terapkan algoritma D-and-C pada masingmasing bagian.
d. Pasangan titik yang jaraknya terdekat ada tiga kemungkinan letaknya :
  • Pasangan titik terdekat terdapat di bagian PLeft.
  • Pasangan titik terdekat terdapat di bagian PRight.
  • Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di PRight.
Jika kasusnya adalah (c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.

IMPLEMENTASINYA PADA JAVA

import java.util.Random;

public final class MaxSumTest
{
    static private int seqStart = 0;
    static private int seqEnd = -1;

    /**
     * Cubic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum1( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
            for( int j = i; j < a.length; j++ )
            {
                int thisSum = 0;

                for( int k = i; k <= j; k++ )
                    thisSum += a[ k ];

                if( thisSum > maxSum )
                {
                    maxSum   = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }

        return maxSum;
    }

    /**
     * Quadratic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum2( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
        {
            int thisSum = 0;
            for( int j = i; j < a.length; j++ )
            {
                thisSum += a[ j ];

                if( thisSum > maxSum )
                {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }
        }

        return maxSum;
    }

    /**
     * Linear-time maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum3( int [ ] a )
    {
        int maxSum = 0;
        int thisSum = 0;

        for( int i = 0, j = 0; j < a.length; j++ )
        {
            thisSum += a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
            else if( thisSum < 0 )
            {
                i = j + 1;
                thisSum = 0;
            }
        }

        return maxSum;
    }

    /**
     * Recursive maximum contiguous subsequence sum algorithm.
     * Finds maximum sum in subarray spanning a[left..right].
     * Does not attempt to maintain actual best sequence.
     */
    private static int maxSumRec( int [ ] a, int left, int right )
    {
        int maxLeftBorderSum = 0, maxRightBorderSum = 0;
        int leftBorderSum = 0, rightBorderSum = 0;
        int center = ( left + right ) / 2;

        if( left == right )  // Base case
            return a[ left ] > 0 ? a[ left ] : 0;

        int maxLeftSum  = maxSumRec( a, left, center );
        int maxRightSum = maxSumRec( a, center + 1, right );

        for( int i = center; i >= left; i-- )
        {
            leftBorderSum += a[ i ];
            if( leftBorderSum > maxLeftBorderSum )
                maxLeftBorderSum = leftBorderSum;
        }

        for( int i = center + 1; i <= right; i++ )
        {
            rightBorderSum += a[ i ];
            if( rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }

        return max3( maxLeftSum, maxRightSum,
                     maxLeftBorderSum + maxRightBorderSum );
    }

    /**
     * Return maximum of three integers.
     */
    private static int max3( int a, int b, int c )
    {
        return a > b ? a > c ? a : c : b > c ? b : c;
    }

    /**
     * Driver for divide-and-conquer maximum contiguous
     * subsequence sum algorithm.
     */
    public static int maxSubSum4( int [ ] a )
    {
        return a.length > 0 ? maxSumRec( a, 0, a.length - 1 ) : 0;
    }

    public static void getTimingInfo( int n, int alg )
    {
        int [] test = new int[ n ];

        long startTime = System.currentTimeMillis( );;
        long totalTime = 0;

        int i;
        for( i = 0; totalTime < 4000; i++ )
        {
            for( int j = 0; j < test.length; j++ )
                test[ j ] = rand.nextInt( 100 ) - 50;

            switch( alg )
            {
              case 1:
                maxSubSum1( test );
                break;
              case 2:
                maxSubSum2( test );
                break;
              case 3:
                maxSubSum3( test );
                break;
              case 4:
                maxSubSum4( test );
                break;
            }

            totalTime = System.currentTimeMillis( ) - startTime;
        }

        System.out.println( "Algorithm #" + alg + "\t"
             + "N = " + test.length
             + "\ttime = " + ( totalTime * 1000 / i ) + " microsec" );
    }
   
    private static Random rand = new Random( );
   
    /**
     * Simple test program.
     */
    public static void main( String [ ] args )
    {
        int a[ ] = { 4, -3, 5, -2, -1, 2, 6, -2 };
        int maxSum;

        maxSum = maxSubSum1( a );
        System.out.println( "Max sum is " + maxSum + "; it goes"
                       + " from " + seqStart + " to " + seqEnd );
        maxSum = maxSubSum2( a );
        System.out.println( "Max sum is " + maxSum + "; it goes"
                       + " from " + seqStart + " to " + seqEnd );
        maxSum = maxSubSum3( a );
        System.out.println( "Max sum is " + maxSum + "; it goes"
                       + " from " + seqStart + " to " + seqEnd );
        maxSum = maxSubSum4( a );
        System.out.println( "Max sum is " + maxSum );
       
          // Get some timing info
        for( int n = 10; n <= 1000000; n *= 10 )
            for( int alg = 4; alg >= 1; alg-- )
            {
                if( alg == 1 && n > 50000 )
                    continue;   
                getTimingInfo( n, alg );
            }
    }
}

 

Semoga bisa membantu para bloger sekalian.
Terima kasih telah mengunjungi blog saya :)



Komentar

  1. Unknown26 Maret 2016 pukul 20.08

    makasih banyak gan, ngebantu banget buat tugas

    BalasHapus
  2. Unknown13 Maret 2020 pukul 18.12

    Did you hear there is a 12 word phrase you can communicate to your crush... that will trigger deep feelings of love and impulsive attractiveness for you deep inside his chest?

    That's because hidden in these 12 words is a "secret signal" that fuels a man's impulse to love, please and care for you with his entire heart...

    ====> 12 Words That Fuel A Man's Love Impulse

    This impulse is so built-in to a man's mind that it will make him try harder than ever before to love and admire you.

    Matter of fact, fueling this mighty impulse is so important to having the best possible relationship with your man that the instance you send your man a "Secret Signal"...

    ...You will instantly notice him open his mind and soul to you in such a way he's never experienced before and he'll see you as the one and only woman in the galaxy who has ever truly tempted him.

    BalasHapus

Posting Komentar