ALGORITMA SEARCH

                ALGORITMA SEARCH

Algoritma pencarian

Dalam ilmu komputer , sebuah algoritma pencarian, secara umum, adalah algoritma untuk mencari item dengan sifat tertentu antara koleksi item. Item dapat disimpan secara individual sebagaicatatan dalam database yang , atau mungkin menjadi elemen dari sebuah ruang pencarian didefinisikan oleh rumus matematika atau prosedur, seperti akar dari suatu persamaan dengan bilangan bulatvariabel , atau kombinasi dari dua, seperti Hamiltonian sirkuit dari grafik .

Untuk ruang pencarian maya

Algoritma untuk mencari ruang virtual yang digunakan dalam masalah kepuasan kendala , di mana tujuannya adalah untuk menemukan satu set nilai ke variabel tugas tertentu yang akan memuaskan matematis tertentu persamaan dan inequations . Mereka juga digunakan ketika tujuannya adalah untuk menemukan tugas variabel yang akan memaksimalkan atau meminimalkan fungsi tertentu dari variabel tersebut. Algoritma untuk masalah ini termasuk dasar pencarian brute force (juga disebut "naif" atau "kurang informasi" pencarian), dan berbagai heuristik yang mencoba untuk memanfaatkan pengetahuan parsial tentang struktur ruang, seperti relaksasi linier , generasi kendala , dan kendala propagasi .

Subclass penting adalah pencarian lokal metode, yang melihat unsur-unsur ruang pencarian sebagai simpul dari suatu graf, dengan tepi yang didefinisikan oleh satu set heuristik berlaku untuk kasus ini, dan scan ruang dengan bergerak dari item ke item sepanjang tepi , misalnya menurut keturunan curam atau terbaik pertama kriteria, atau dalam pencarian stokastik . Kategori ini mencakup berbagai besar umum metaheuristic metode, seperti simulated annealing , pencarian tabu , A-tim, dan pemrograman genetik , yang menggabungkan heuristik sewenang-wenang dengan cara tertentu.

Kelas ini juga mencakup berbagai algoritma pencarian pohon , yang melihat unsur-unsur sebagai simpul dari pohon , dan melintasi pohon itu di beberapa pesanan khusus. Contoh terakhir ini termasuk metode lengkap seperti depth-first search dan breadth-first search , serta berbagai heuristik berbasis pemangkasan pohon pencarian metode seperti kemunduran dan cabang dan terikat . Tidak seperti metaheuristics umum, yang di tempat kerja terbaik hanya dalam arti probabilistik, banyak dari pohon-cari metode dijamin untuk menemukan solusi yang tepat atau optimal, jika diberikan cukup waktu.

Sub-kelas lain yang penting terdiri dari algoritma untuk menjelajahi pohon permainan dari beberapa pemain game, seperti catur atau backgammon , yang terdiri dari semua node situasi permainan kemungkinan yang bisa dihasilkan dari situasi saat ini. Tujuan dalam masalah ini untuk menemukan gerakan yang menyediakan kesempatan terbaik untuk menang, dengan mempertimbangkan semua kemungkinan bergerak lawan (s). Masalah serupa terjadi ketika manusia atau mesin harus membuat keputusan yang berurutan yang hasil tidak sepenuhnya di bawah kendali seseorang, seperti dalamrobot bimbingan atau dalam pemasaran , keuangan atau militer perencanaan strategi. Masalah seperti ini telah dipelajari secara ekstensif dalam konteks kecerdasan buatan . Contoh algoritma untuk kelas ini adalah algoritma minimax , alpha-beta pruning , dan algoritma A * .

Untuk sub-struktur dari struktur yang diberikan

Nama pencarian kombinatorial umumnya digunakan untuk algoritma yang mencari struktur sub-spesifik yang diberikan struktur diskrit , seperti grafik, sebuah tali , sebuah terbatas kelompok , dan sebagainya. Istilah optimasi kombinatorial biasanya digunakan ketika tujuannya adalah untuk menemukan struktur sub-dengan nilai (atau minimum) maksimum beberapa parameter. (Karena struktur sub-biasanya diwakili dalam komputer dengan satu set variabel integer dengan kendala, masalah ini dapat dipandang sebagai kasus khusus dari kepuasan kendala atau optimasi diskrit, tetapi mereka biasanya dirumuskan dan diselesaikan dalam pengaturan lebih abstrak dimana representasi internal tidak disebutkan secara eksplisit.)

Subclass penting dan ekstensif dipelajari adalah algoritma grafik , khususnya grafik traversal algoritma, untuk mencari sub-struktur yang spesifik dalam grafik yang diberikan - seperti subgraphs , jalan ,sirkuit , dan sebagainya. Contohnya termasuk algoritma Dijkstra , algoritma Kruskal , yang algoritma tetangga terdekat , dan algoritma Prim .

Subclass lain penting dari kategori ini adalah algoritma pencarian string yang , yang mencari pola dalam string. Dua contoh terkenal adalah Boyer-Moore dan Knuth-Morris-Pratt algoritma , dan beberapa algoritma berdasarkan akhiran pohon struktur data.

Untuk komputer kuantum

Ada juga mencari metode yang dirancang untuk komputer kuantum , seperti algoritma Grover , yang secara teoritis lebih cepat daripada pencarian linear atau brute force bahkan tanpa bantuan struktur data atau heuristik.

Algoritma pencarian biner

Umumnya, untuk mencari nilai dalam array disortir, kita harus melihat melalui elemen dari sebuah array satu per satu, sampai nilai dicari ditemukan. Dalam hal nilai dicari tidak ada dari array, kita melalui semua elemen. Rata-rata, kompleksitas algoritma tersebut sebanding dengan panjang array.

Situasi perubahan signifikan, ketika array diurutkan. Jika kita tahu itu, kemampuan akses acak dapat dimanfaatkan sangatefisien untuk menemukan nilai dicari cepat. Biaya dari algoritma pencarian untuk logaritma biner mengurangi panjang array.Untuk referensi, log ₂ (1 000 000) ≈ 20. Ini berarti, bahwa dalam kasus terburuk, algoritma membuat 20 langkah untuk menemukan nilai dalam array diurutkan dari satu juta elemen atau mengatakan, bahwa hal itu tidak hadir array.

Algoritma

Algoritma ini cukup sederhana. Hal ini dapat dilakukan baik secara rekursif atau iteratif:

1. mendapatkan elemen tengah;
2. jika elemen tengah sama dengan nilai dicari, algoritma akan berhenti;
3. sebaliknya, dua kasus yang mungkin:
• mencari nilai kurang, dari elemen tengah. Dalam hal ini, pergi ke langkah 1 untuk bagian dari array, sebelum elemen tengah.
• mencari nilai lebih besar, dari elemen tengah. Dalam hal ini, pergi ke langkah 1 untuk bagian dari array, setelah elemen tengah.

Sekarang kita harus mendefinisikan, saat iterasi harus berhenti. Kasus pertama adalah ketika elemen dicari ditemukan.Yang kedua adalah ketika subarray tidak memiliki elemen. Dalam kasus ini, kita dapat menyimpulkan, bahwa nilai dicari tidak hadir dalam array.

Contoh

Contoh 1. Cari 6 di {-1, 5, 6, 18, ​​19, 25, 46, 78, 102, 114}.

Langkah 1 (elemen tengah adalah 19> 6):   -1 5 6 18 19 25 46 78 102 114

Langkah 2 (elemen tengah adalah 5 <6):   -1 5 6 18 19 25 46 78 102 114

Langkah 3 (elemen tengah adalah 6 == 6):   -1 5 6 18 19 25 46 78 102 114

Contoh 2. Cari 103 di {-1, 5, 6, 18, ​​19, 25, 46, 78, 102, 114}.

Langkah 1 (elemen tengah adalah 19 <103):   -1 5 6 18 19 25 46 78 102 114

Langkah 2 (elemen tengah adalah 78 <103):   -1 5 6 18 19   25 46 78 102 114

Langkah 3 (elemen tengah adalah 102 <103):    -1 5 6 18 19 25 46 78 102 114

Langkah 4 (elemen tengah adalah 114> 103):    -1 5 6 18 19 25 46 78 102 114

Langkah 5 (nilai dicari tidak ada):       -1 5 6 18 19 25 46 78 102 114 

Kompleksitas analisis

Keuntungan besar dari algoritma ini adalah bahwa kompleksitas itu tergantung pada ukuran array logaritmis dalam kasus terburuk. Dalam prakteknya ini berarti, algoritma yang akan dilakukan di log yang paling ₂ (n) iterasi, yang merupakan jumlah yang sangat kecil, bahkan untuk array besar. Hal ini dapat terbukti sangat mudah. Memang, di setiap langkah ukuran bagian dicari berkurang setengahnya. Algoritma berhenti, ketika tidak ada unsur untuk mencari masuk Oleh karena itu, pemecahan kesenjangan berikut dalam bilangan bulat:

n / 2 ^iterasi> 0

mengakibatkan

iterasi <= log ₂ (n).

Ini berarti, bahwa algoritma pencarian biner kompleksitas waktu adalah O (log ₂ (n)).

Potongan kode.

Anda dapat melihat solusi rekursif untuk Java dan iteratif untuk C + + di bawah ini.

Java

/ **

  * pencarian untuk sebuah nilai di diurutkan susunan

  *

  * @ Param susunan

  *             susunan untuk pencarian di

  * @ Param nilai

  *             mencari nilai

  * @ Param kiri

  *             Indeks dari kiri batas

  * @ Param benar

  *             Indeks dari benar batas

  * @ Return posisi dari mencari nilai, jika itu menyajikan di yang susunan atau - 1, jika

  *          itu adalah absen

  * /

int binarySearch (int [] array, nilai int, int kiri, kanan int) {

      jika (kiri> kanan)

            return -1;

      int tengah = (kiri + kanan) / 2;

      if (array [tengah] == nilai)

            kembali menengah;

      lain if (array [tengah]> nilai)

            kembali binarySearch (array, nilai, kiri, tengah - 1);

      lain

            kembali binarySearch (array, nilai, tengah + 1, kanan);

}

C + +

/ *

* Mencari nilai dalam array diurutkan

* Arr adalah array untuk mencari di

* Nilai dicari nilai

* Kiri adalah indeks batas kiri

* Tepat adalah indeks dari batas kanan

* Mengembalikan nilai posisi dicari, jika menyajikan dalam array

* Atau -1, jika ada

* /

int binarySearch (int arr [], int nilai, int kiri, kanan int) {

sementara (kiri <= kanan) {

int tengah = (kiri + kanan) / 2;

if (arr [tengah] == nilai)

kembali menengah;

else if (arr [tengah]> nilai)

kanan = tengah - 1;

lain

kiri = tengah + 1;

      }

return -1;

}

http://translate.google.co.id/translate?hl=id&langpair=en|id&u=http://en.wikipedia.org/wiki/Search_algorithm

http://translate.google.co.id/translate?hl=id&langpair=en|id&u=http://www.algolist.net/Algorithms/Binary_search

ALGORITMA QUICK SORT

             ALGORITMA QUICK SORT

Algoritma quick sort diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960, dan dimuat sebagai artikel di “Computer Journal 5” pada April 1962. Quick sort adalah algoritma sorting yang berdasarkan pembandingan dengan metoda divide-and-conqueror. Disebut Quick Sort, karena Algoritma quick sort mengurutkan dengan sangat cepat. Quick sort disebut juga dengan partition exchange sort, karena konsepnya membuat partisi-partisi, dan sort dilakukan per partisi.

Teknik mempartisi tabel:

(i) pilih x ϵ {a1, a2, …, an} sebagai elemen pivot.

(ii) pindai (scan) tabel dari kiri sampai ditemukan elemen ap ≥ x.

(iii) pindai tabel dari kanan sampai ditemukan elemen aq ≤ x

(iv) pertukarkan ap <-> aq

(v) ulangi (ii) dari posisi p + 1, dan (iii) dari posisi q – 1, sampai kedua pemindaian bertemu di tengah tabel.

Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.

Walaupun begitu algoritma quick sort tidak selalu merupakan pilihan yang terbaik. Seperti yang telah disebutkan sebelumnya, algoritma ini dilakukan secara rekursif yang berarti jika dilakukan untuk tabel yang berukuran sangat besar, walaupun cepat, dapat menghabiskan memori yang besar pula. Selain itu, algoritma ini adalah algoritma yang terlalu komplex untuk mengurutkan tabel yang berukuran kecil (hanya puluhan elemen misalnya). Selain itu algoritma quick sort mempunyai tingkat efisiensi yang buruk ketika dioperasikan pada tabel yang hampir terurut atau pada tabel yang terurut menurun.

Algoritma Quick Sort

Dalam algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :

1. Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kanan.

2. Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.

3. Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.

Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTISI dan prosedur QUICKSORT. Berikut pseudocode dari algoritma quick sort :

Procedure QuickSort (input/output a : array [1..n] of integer, input i , j : integer )

{mengurutkan tabel a[i..j] dengan algoritma quick sort. Masukkan: Tabel a[i..j] yang sudah

terdefinisi elemen-elemennya. Keluaran: Tabel a[i..j] yang terurut menaik.}

Deklarasi :

k : integer;

Algoritma :

if (i<j) then

Partisi(a,i,j,k) { Ukuran (a) > 1}

QuickSort(a,i,k)

QuickSort(a,k+1, j)

Endif

Procedure Partisi (input/output: a : array[1..n] of integer, input i , j : integer, output q : integer)

{Membagi tabel a[i..j] menjadi subtabel a[i..q] dan a[q+1..j]. Keluaran upatabel a[i..q] dan subtabel a[q+1..j]. Sedemikian sehingga elemen tabel a[i..q] lebih kecil dari elemen tabel a[q+1..j]}

Deklarasi :

Pivot, temp : integer

Algoritma :

Pivot <- A[(i+j) div 2] { pivot = elemen tengah }

p <- i

q <- j

repeat

while a[p] < pivot do

p <- p + 1

endwhile

{ Ap >= pivot }

while a[q] > pivot do

q <- q – 1

endwhile

{ Aq >= pivot }

if (p _ q) then

{ pertukarkan a[p] dengan a[q]}

temp <- a[p]

a[p] <- a[q]

a[q] <- temp

{ tentukan awal pemindaian berikutnya}

p <- p+ 1

q <- q – 1

endif

until p > q

Kompleksitas Algoritma Quick Sort

Kebutuhan waktu dari quicksort bergantung pada pembuatan partisi, seimbang atau tidak, yang bergantung juga pada elemen yang digunakan sebagai pivot. Dalam menghitung kompleksitas ini, perlu dilihat pula perhitungan recurrence, karena terdapat fungsi rekursif untuk penyelesaian sub-masalah.

Terdapat 3 jenis kompleksitas waktu dari quicksort:

1.       Kasus terburuk (worst case), yaitu terjadi bila terbentuk partisi dengan komposisi sub-masalah antara n – 1 elemen dan 0 elemen. Dengan demikian pemanggilan fungsi secara rekursif dengan array berukuran 0 akan langsung kembali, T(0) = Θ(1), sehingga berlaku: T(n) = T(n – 1) + cn = O(n²).

2.       Kasus terbaik (best case), yaitu terjadi bila terbentuk partisi dengan dengan komposisi seimbang, dengan ukuran masing-masing tidak lebih dari n/2. Sehingga didapat: T(n) = 2T(n/2) + cn = na + cn log n = O(n log n).

3.       Kasus rata-rata (average case), yaitu terjadi dari perimbangan pivot antara terbaik dan terburuk, yang dalam prakteknya lebih mendekati kasus terbaik ketimbang terburuk. Sehingga didapat: T_avg(n) = O(n log n).

Kelebihan dan Kelemahan Algoritma Quick Sort

Beberapa hal yang membuat quick sort unggul:

·         Secara umum memiliki kompleksitas O(n log n).

·         Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.

·         Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti merge sort dan heap sort.

·         Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.

·         Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).

Namun terdapat pula kelemahan quick sort:

·         Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).

·         Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n²).

·         Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).

·         Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.

Implementasi Algoritma Quick Sort

Berikut adalah implementasi dari quick sort dalam bahasa C. Implementasinya terbagi menjadi dua prosedur, yaitu prosedur partisi dan prosedur quicksort.

void quicksort(int x[], int first, int last) {

int pivIndex = 0;

if(first < last) {

pivIndex = partition(x,first, last);

quicksort(x,first,(pivIndex-1));

quicksort(x,(pivIndex+1),last);

}

}

int partition(int y[], int f, int l) {

int up,down,temp;

int piv = y[f];

up = f;

down = l;

goto partLS;

do {

temp = y[up];

y[up] = y[down];

y[down] = temp;

partLS:

while (y[up] <= piv && up < l) {

up++;

}

while (y[down] > piv  && down > f ) {

down–;

}

} while (down > up);

y[f] = y[down];

y[down] = piv;

return down;

}

Partition algorithm in detail

There are two indices i and j and at the very beginning of the partition algorithm i points to the first element in the array andj points to the last one. Then algorithm moves i forward, until an element with value greater or equal to the pivot is found. Index j is moved backward, until an element with value lesser or equal to the pivot is found. If i ≤ j then they are swapped and i steps to the next position (i + 1), j steps to the previous one (j - 1). Algorithm stops, when i becomes greater than j.

After partition, all values before i-th element are less or equal than the pivot and all values after j-th element are greater or equal to the pivot.

Example. Sort {1, 12, 5, 26, 7, 14, 3, 7, 2} using quicksort.

http://www.algolist.net/Algorithms/Sorting/Quicksort

Notice, that we show here only the first recursion step, in order not to make example too long. But, in fact, {1, 2, 5, 7, 3} and {14, 7, 26, 12} are sorted then recursively.

Why does it work?

On the partition step algorithm divides the array into two parts and every element a from the left part is less or equal than every element b from the right part. Also a and b satisfy a ≤ pivot ≤ b inequality. After completion of the recursion calls both of the parts become sorted and, taking into account arguments stated above, the whole array is sorted.

Complexity analysis

On the average quicksort has O(n log n) complexity, but strong proof of this fact is not trivial and not presented here. Still, you can find the proof in . In worst case, quicksort runs O(n²) time, but on the most "practical" data it works just fine and outperforms other O(n log n) sorting algorithms.

Code snippets

Partition algorithm is important per se, therefore it may be carried out as a separate function. The code for C++ contains solid function for quicksort, but Java code contains two separate functions for partition and sort, accordingly.

Java

int partition(int arr[], int left, int right)

{

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

     

      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      };

     

      return i;

}

void quickSort(int arr[], int left, int right) {

      int index = partition(arr, left, right);

      if (left < index - 1)

            quickSort(arr, left, index - 1);

      if (index < right)

            quickSort(arr, index, right);

}

C++

void quickSort(int arr[], int left, int right) {

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

      /* partition */

      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      };

      /* recursion */

      if (left < j)

            quickSort(arr, left, j);

      if (i < right)

            quickSort(arr, i, right);

}

http://www.algolist.net/Algorithms/Sorting/Quicksort

http://www.google.com