Đề Xuất 8/2022 ❤️ Disjoint Set Cấu Trúc Dữ Liệu Đơn Giản Mà Hiệu Quả ❣️ Top Like | Comforttinhdauthom.com

Đề Xuất 8/2022 ❤️ Disjoint Set Cấu Trúc Dữ Liệu Đơn Giản Mà Hiệu Quả ❣️ Top Like

Xem 11,781

Cập nhật nội dung chi tiết về Disjoint Set Cấu Trúc Dữ Liệu Đơn Giản Mà Hiệu Quả mới nhất ngày 19/08/2022 trên website Comforttinhdauthom.com. Hy vọng thông tin trong bài viết sẽ đáp ứng được nhu cầu ngoài mong đợi của bạn, chúng tôi sẽ làm việc thường xuyên để cập nhật nội dung mới nhằm giúp bạn nhận được thông tin nhanh chóng và chính xác nhất. Cho đến nay, bài viết này đã thu hút được 11,781 lượt xem.

Top 10 Cuốn Sách Hay Về Cấu Trúc Dữ Liệu Và Giải Thuật

Review Và Chia Sẻ Sách Về Cấu Trúc Dữ Liệu Và Giải Thuật Cho Mọi Ngôn Ngữ Cực Hay Cho Ace ” Cafedev.vn

Bài Tập Lớn Môn Nhập Môn Cơ Sở Dữ Liệu

Giáo Trình Hệ Quản Trị Cơ Sở Dữ Liệu Sql

Tìm Hiểu Cấu Trúc Dữ Liệu #1: “chết Vì Thiếu Hiểu Biết”

Bất kì bài toán tin học nào cũng được giải quyết dựa trên thuật toán (Algorithm) và cấu trúc dữ liệu biểu diễn nó (Data Structure).

Algorithms + Data Structures = Programs

Tuy nhiên, trong quá trình giải quết bài toán ta thường quá chú tâm tới giải thuật mà quên mất rằng việc lựa chọn cấu trúc dữ liệu hợp lý ảnh hưởng rất nhiều tới thuật toán. Hay hiệu quả của thuật toán phụ thuộc vào cấu trúc dữ liệu được sử dụng.

Cấu trúc dữ liệu cũng rất đa dạng từ những cấu trúc dữ liệu đơn giản như mảng một chiều, nhiều chiều tới ngăn xếp, hàng đợi, bảng băm, cấu trúc dữ liệu dạng cây như cây nhị phân, heap, … và những cấu trúc dữ liệu nâng cao khác.

Ngoài ra còn có một dạng cấu trúc dữ liệu cài đặt khá đơn giản nhưng rất hiệu quả trong nhiều bài toán đó là Disjoint set.

Disjoint set là gì ?

Theo wikipedia: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Disjoint set là một cấu trúc dữ liệu theo dõi (tracking) một tập các phần tử được phân chia thành các tập con khác nhau không chồng chéo nhau (non-overlapping).

Hay đơn giản hơn ta có ví dụ sau:

Bài toán 1

Ta có 6 thành phố là A, B, C, D, E, F. Thành phố A có thể đi tới thành phố B và C. Thành phố B có thể đi tới thành phố D. Thành phố E có thể đi tới thành phố F. Các thành phố xảy ra chiến tranh những thành phố có đường đi trưc tiếp ( chẳng hạn từ A tới B và C) hoặc gián tiếp ( từ A tới D qua B) thì tướng lĩnh của thành phố đó có thể đem quân đánh chiếm thành phố khác sáp nhập làm của mình tạo thành một vùng mới và có 1 vị vua cai quản. Vậy khi tàn cuộc có bao nhiêu vùng đất khác nhau được cai quản bởi các vị vua.

Để tìm số vùng đất được cai quản bởi các vị vua khác nhau ta sẽ chia tập hợp các thành phố {A, B, C, D, E, F} thành các tập con sao cho hai tập con bất kì không thể có đường đi từ thành phố của tập con này tới thành phố của tập con kia.

Dễ thấy các vùng đất {A, B, C, D} có đường đi với nhau cuối cùng sẽ gộp chung lại thành 1 vùng đất được cai quản bởi 1 vị vua. Tuy nhiên vị vua đó không thể tiến đánh các thành phố E, F do không có đường đi. Cuối cùng sẽ chỉ có 2 vùng đất được tạo thành bởi các thành phố {A, B, C, D} và {E, F}.

Bài toán 2

Với một bài toán tương tự nhưng ta xét một ví dụ dễ biểu diễn trong máy tính hơn đó là: Cho tập hợp gồm N phần tử A = {1, 2, 3, 4, 5, 6, 7, 8 } các phần tử (1, 2) (1, 3) (2, 3) (4, 7) (4, 8) (5, 6) có liên kết với nhau. Tìm các tập hợp con mà giữa 2 tập hợp không có liên kết trực tiếp hoặc gián tiếp.

Nếu không sử dụng ý tưởng cấu trúc dữ liệu disjoint set ta có cách tiếp cận sau

Sử dụng mảng link = link = {1, 2, 3, 4, 5, 6, 7, 8}.

Bây giờ ta sẽ duyệt qua tất cả phần tử và kiểm tra liên kết trực tiếp của nó. Khi thêm liên kết ta sẽ thực hiện 2 thao tác đó là

find(x, y) kiểm tra x và y có liên kết chưa (link)

union(x, y) hợp x vào y và tất cả các phần tử liên kết với x cũng đều liên kết với y.

Chẳng hạn:

Bắt đầu với 1 có

Tiếp theo với phần tử 2

Ý tưởng của disjoint set

Lúc này ta có 3 cây với 3 root là 5, 6, 4 là 3 tập hợp con. Do ta xây dựng 3 tập hợp con là cấu trúc dạng cây nên để kiểm tra 2 phần tử có liên kết hay không ta chỉ cần kiểm tra xem chúng có chung root hay không

find(x, y) sẽ thực hiện findSet(x) == findSet(y) với findSet(x) trả về phần tử root của tập hợp chứa x. Ví dụ findSet(2) = 4, findSet(7) = 4. Độ phức tạp thuật toán là O(logN) hàm findSet sẽ đệ quy theo chiều cao của cây.

Cài đặt disjoint set

Ở bước khởi tạo ta coi mỗi phần tử là 1 cây với 1 nút root là chính nó thông qua makeSet(x)

Tiếp theo ta viết hàm xác định tập hợp (cây) chứa x

Cuối cùng là union thay vì luôn gắn root của cây chứa y vào root của cây chứa x ta thực hiện union by rank

Với các ví dụ trên việc áp dụng cấu trúc dữ liệu disjoint set thay vì độ phức tạp là O(N2) sẽ có độ phức tạp là 0(NlogN)

Ứng dụng

Ta cần xây dựng 1 hệ thống cáp nối tất cả các điểm trong thành phố A, B, C, D, … Tuy nhiên chi phí cáp giữa các điểm là khác nhau. MST giúp ta xác định đươc 1 hệ thống (dạng cây) nối tất cả các điểm với chi phí nhỏ nhất như hình vẽ.

Ý tưởng của thuật toán Kruskal dựa trên disjoint set và tham lam đã được trình bày ở đây: https://viblo.asia/p/cac-dang-bai-su-dung-thuat-toan-tham-lam-greedy-algorithm-problems-924lJARYZPM#_cac-bai-toan-lien-quan-toi-do-thi-6

Xây dựng hệ thống đếm số lượng bạn chung (mutual friends)

Hiện tại một nhóm sinh viên trong trường đang có trang social networking giúp kết nối bạn bè trong trường học tương tác với nhau, những người e ngại việc sử dụng facebook do bị leak thông tin. Một trong số những tính năng mà adminstrator đang cần bạn phát triển đó là hiển thị số lượng bạn chung (mutual friend) của giữa X và Y ở đây tất những người bạn trực tiếp với X hay gián tiếp qua một người bạn Z của X lúc này có thể coi là bạn chung với Y. Các requirement bạn nhận được như sau:

Nếu user A gửi request cho user B thì A sẽ following B. A và B chỉ là bạn bè khi B cũng following A

Khi A và B đã là bạn bè, có thể xem được số lượng bạn chung giữa A và B.

Phân tích

Đối với yêu cầu 1 ta xây dựng 1 mảng vector following sẽ là 1 vector chứa các id của user đang following user có id là 3. A và B là bạn bè khi following của B chứa id của A và ngược lại.

Khi A và B đã là bạn bè ta sẽ hợp (union) X và Y.

Đối với yêu cầu 2 khi nhận được yêu cầu đếm số lượng bạn chung giữa A và B ta chỉ việc kiểm tra xem A và B có chung root hay không nó có trả về số lượng thành viên của root đó.

Note: Ở trên ta cài đặt union by rank theo độ cao của cây. Tuy nhiên đối với bài toán này ta cần lưu trữ số lượng thành viên của root (số lượng phần tử trong cây của root) nên ta thực hiện union by size thay vì union by rank

Để dễ biểu diễn nhất ta quy định yêu cầu 1 sẽ truyền và params là ‘following’ A_id B_id với A_id là user_id người gửi request following cho B_id. yêu cầu 2 sẽ truyền params là ‘mutual friends’ A_id B_id.

Ta có implement đơn giản trong C như sau

Tìm Hiểu Map Và Set Trong Javascript

Cấu Trúc Dữ Liệu Disjoint Sets

Cấu Trúc Dữ Liệu Và Giải Thuật: Ngăn Xếp (Stack)

Cấu Trúc Dữ Liệu Ngăn Xếp (Stack)

Làm Việc Với Cấu Trúc Dữ Liệu Hàng Đợi (Queue)

Bạn đang đọc nội dung bài viết Disjoint Set Cấu Trúc Dữ Liệu Đơn Giản Mà Hiệu Quả trên website Comforttinhdauthom.com. Hy vọng một phần nào đó những thông tin mà chúng tôi đã cung cấp là rất hữu ích với bạn. Nếu nội dung bài viết hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất. Chúc bạn một ngày tốt lành!

Yêu thích 2211 / Xu hướng 2291 / Tổng 2371 thumb
🌟 Home
🌟 Top