Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Thuật toán tìm kiếm Tam Phân | Tổng quan về tìm kiếm tam phân

  1. #1
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Wink Thuật toán tìm kiếm Tam Phân | Tổng quan về tìm kiếm tam phân

    Thuật toán tìm kiếm Tam Phân
    Tìm kiếm là một yêu cầu rất thường xuyên trong đời sống hàng ngày. Trong tin học nó đặt nền móng cho nhiều tác vụ tính toán quan trọng. Bài toán tìm kiếm là sự xác định vị trí của một hay nhiều phần tử, gọi là đối trị tìm kiếm (Argument), trong một bảng liệt kê có thứ tự các phần tử. Mỗi phần tử đơược đại diện bằng một khoá (Key) phục vụ cho tìm kiếm. Những ứng dụng của tìm kiếm thì rất đa dạng, cũng như có rất nhiều các thuật toán với đặc trương và hiệu suất khác nhau. Một trong những phơương pháp khá hiệu quả là phương pháp tìm kiếm Tam Phân.
    Thuật toán tìm kiếm Tam Phân (Trisearch), xác định vị trí của phần tử cần tìm trong một bảng lệt kê các phần tử đươợc sắp xếp theo thứ tự tăng (hay giảm) dần của trường khoá. Bằng cách chia liên tiếp bảng liệt kê thành ba bảng liệt kê con có kích thơước tương đươơng nhau (Step=(R-L+1) div 3). Thuật toán này là sự thể hiện sinh động của tinh thần “chia để trị”. Giả sử bảng liệt kê đơược xác định bởi hai con trỏ L,R, trỏ đến phần tử trái và phải. Thuật toán sẽ chia bảng [L,R] thành ba bảng con: [L,U-1], [Ư1,V-1], [V+1,R]. Dựa vào giá trị khoá của Argument và giá trị khoá tại các điểm U=Step , V=L+2*Step. Tìm kiếm sẽ dừng nếu khoá của mẫu bằng với giá trị khoá của một trong hai điểm trên, ngược lại tìm kiếm sẽ tiếp tục trên một trong ba bảng con đơược chia. Quá trình cứ tiếp tục nhươ thế cho đến khi tìm đươợc phần tử mong muốn hoặc bảng phần tử đang sét là rỗng. Hình 1 mô tả hình thức tam phân của Trisearch theo sơ đồ “chia để trị”.
    Thuật toán sau đây đơược trình bày đưới dạng giả mã, sẽ tìm kiếm phần tử Item trong mảng Key đã được sắp xếp theo thứ tự tăng dần:
    PHP Code:

     int Trisearch
    (int key[], int itemint lint r)
    {
     
    int uvresultstep;
     
    result=0;
     while ((
    l<=r) && (result==0))
     {
         
    step =(r-l+1) / 3;
         
    u=l+stepv=l+2*step;
         if (
    item == key[u] ) result=u;
         else
         if (
    item == key[v] ) result=v;
         else
         if (
    item key[v] ) l=v+;
         else
         if (
    item key[u] )
         {
         
    l=ư1;
         
    r=v-1;
         }
     else
         
    r=u-1;
     }
     return (
    result);

    Chúng ta có thể cài đặt thuật toán trên theo phương pháp đệ quy. Với vùng bộ nhớ Stack hạn chế, nên lưu ý khi kích thước bảng phần tử lớn ta nên truyền tham số Key theo kiểu tham chiếu (địa chỉ). Điều này giúp ta tránh được lỗi “Stack overflow error” do tràn vùng bộ nhớ ngăn xếp.
    PHP Code:
     
     int Trisearch_dq
    int key[], int item,int lint r)  {
     
    int uvstep;
     if (
    l<=r)
     {
     
    step=(r-l+1) / 3;
     
    u=l+stepv=l+2*step;
     if (
    item == key[u]) return u;
         else
     if (
    item == key[v]) return v;
         else
     if (
    item key[v] )
         return 
    Trisearch_dq(keyitem,v+1,r);
         else+
     if (
    item key[u] )
         return 
    Trisearch_dq(keyitem,ư1,v-1);
         else
         return 
    Trisearch_dq(keyitem,l,u-1);
     }
     else 
    /*khong thanh cong*/
     
    return 0;
     } 
    Khi nói đến các thuật toán tìm kiếm, chúng ta sẽ cảm thấy quen thuộc hơn với thuật toán tìm kiếm nhị phân (Binsearch). Có lẽ bởi tính tự nhiên của phương pháp và dễ cài đặt của thuật toán. Binsearch có độ phức tạp thuật toán về thời gian là O(log2n). Vậy hiệu quả của Trisearch so với Binsearch? Dễ nhận thấy rằng so với Binsearch thì thuật toán Trisearch trong cài đặt đệ quy sẽ hội tụ nhanh hơn, hạn chế khả năng đệ quy sâu. Sau đây chúng ta sẽ phân tích độ phức tạp thuật toán về thời gian của Trisearch.
    Không giảm tính tổng quát, ta giả thiết phạm vi tìm kiếm là từ 1 đến N, bảng key có N phần tử. Sau lần lặp thứ nhất phạm vi tìm kiếm là phần tử, sau lần lặp thứ 2 phạm vi tìm kiếm là N/3. Trong trường hợp tồi nhất vòng lặp While sẽ kết thúc khi N/3i =1, hay I = Log3n. Trong mỗi lần lặp tốn thời gian O(1) nên thời gian thực hiện của hàm Trisearch là O(log3n). Dễ nhận thấy rằng Binsearch và Trisearch có cùng độ phức tạp, hay O(log3n) = O(log2n) (vì log3n=log32 *log2n ). Nhìn vào bảng khảo sát liệt kê giá trị tại một số điểm (hình 2), đồ thị của Log3n, log32 (hình 3) ta cũng thấy được mối tương quan giữa hai hàm.
    Nhưng có lẽ không nên đánh giá thuật toán tìm kiếm này tốt hơn thuật toán tìm kiếm khác. Điều quan trọng là sử dụng chúng sao cho phù hợp với từng ứng dụng và yêu cầu cụ thể. Không có cách nào hiểu thấu đáo một thuật toán nhanh hơn là bắt tay cài đặt chúng. Mình rất mong được học hỏi và đóng góp ý kiến của tất cả các bạn (Tanbv_it@yahoo.com).


  2. #2
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Code:
    int Trisearch_dq( int key[], int item,int l, int r)  {
     int u, v, step;
     if (l<=r)
     {
     step=(r-l+1) / 3;
     u=l+step; v=l+2*step;
     if (item == key[u]) return u;
         else
     if (item == key[v]) return v;
         else
     if (item > key[v] )
         return Trisearch_dq(key, item,v+1,r);
         else+
     if (item > key[u] )
         return Trisearch_dq(key, item,ư1,v-1);
         else
         return Trisearch_dq(key, item,l,u-1);
     }
     else /*khong thanh cong*/
     return 0;
     }
    Code:
    int Trisearch_dq( int key[], int item,int l, int r)  {
     int u, v, step;
     if (l<=r)
     {
     step=(r-l+1) / 3;
     u=l+step; v=l+2*step;
     if (item == key[u]) return u;
         else
     if (item == key[v]) return v;
         else
     if (item > key[v] )
         return Trisearch_dq(key, item,v+1,r);
         else+
     if (item > key[u] )
         return Trisearch_dq(key, item,ư1,v-1);
         else
         return Trisearch_dq(key, item,l,u-1);
     }
     else /*khong thanh cong*/
     return 0;
     }
    Cho cái code to lên 1 tí để bà con coi cho rõ nào.

  3. #3
    Ngày gia nhập
    05 2007
    Bài viết
    2

    nếu là như vậy ta hoàn toàn có thể chia làm bốn làm năm phần
    đặc biệt hữu hiệu với dãy có n lớn
    ta có các thuật toán foursearch,fivesearch,and tensearch....

  4. #4
    Ngày gia nhập
    04 2007
    Bài viết
    16

    Không có foursearch, fivesearch... mà chỉ có tetrasearch,....
    Về lý thuyết, tìm kiếm tam phân nhanh hơn nhị phân chút xíu, nhưng thực tế người ta ít dùng hơn, vì sao? Vì thời gian chậm hơn, có thể nói độ phức tạp thuật toán là như nhau, nhưng phép tìm kiếm tam phân phải dùng để 2 phép so sánh (mất thời gian đáng kể nhất là với so sánh string), còn nhị phân chỉ thực hiện một. Với giới hạn số phần tử cực kỳ lớn thì tìm kiếm tam phân mới tỏ ra hữu hiệu.

Các đề tài tương tự

  1. Thuật toán tìm kiếm nhị phân trên mảng, lỗi không tìm kiếm được?
    Gửi bởi magician1611 trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 8
    Bài viết cuối: 22-05-2012, 03:09 PM
  2. Lập trình C++ Thuật toán tìm kiếm mù(theo độ sâu hoặc rộng) và tìm kiếm leo đồi
    Gửi bởi chickentruong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 08-04-2010, 08:09 PM
  3. Thuật toán tìm kiếm | Ebooks tổng hợp thuật toán tìm kiếm ???
    Gửi bởi Hoadao trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 1
    Bài viết cuối: 11-05-2009, 02:20 PM
  4. Tìm kiếm trên file! Tìm kiếm xâu mẫu dùng giải thuật Naive | Giúp mình code sai ở đâu
    Gửi bởi totoise trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 19-04-2009, 08:22 PM
  5. Bài tập về kiến trúc tài liệu quan sát trong VC++
    Gửi bởi h.t.t trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 10
    Bài viết cuối: 30-11-2008, 03:22 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn