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

Đề tài: Giải thuật sắp xếp Topo

  1. #1
    Ngày gia nhập
    04 2008
    Bài viết
    0

    Question Giải thuật sắp xếp Topo

    Help me!!!!!!!!!!!!!!!!!!
    Ai đã từng cài đặt giải thuật sắp xếp Topo cho mình code nhé. Cám ơn nhiều
    lắm.
    Cài đặt giải thuật sắp xếp Topo :
    -Dữ liệu vào : Tệp văn bản chứa dữ liệu
    -Dữ liệu ra :Tệp văn bản

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

    Trích dẫn Nguyên bản được gửi bởi iumomo Xem bài viết
    Help me!!!!!!!!!!!!!!!!!!
    Ai đã từng cài đặt giải thuật sắp xếp Topo cho mình code nhé. Cám ơn nhiều
    lắm.
    Cài đặt giải thuật sắp xếp Topo :
    -Dữ liệu vào : Tệp văn bản chứa dữ liệu
    -Dữ liệu ra :Tệp văn bản
    Chưa nghe đến giải thuật Topo bao giờ, bạn nói qua về nó xem nào, ý tưởng, giải thuật.

  3. #3
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    444

    Sắp xếp topo là sắp xếp tập hợp trên đó quan hệ "nhỏ hơn hoặc bằng" là một quan hệ không toàn phần.

    Thí dụ, trên tập 52 quân bài trong một bộ bài Tây có thể xác định phép so sánh như sau:

    2 < 3 < 4 <...< 10 < J < Q < K < A để so sánh 2 lá bài cùng chất,
    bích < chuồn < rô < cơ để so sánh 2 lá bài cùng điểm, và
    2 lá bài khác chất và khác điểm không so sánh được với nhau.

    Khi đó, sắp xếp topo của bộ bài là sắp xếp các quân bài thành một dãy a[1],...,a[52] sao cho nếu a[i] so sánh được với a[j] thì a[i] < a[j] với i<j.

  4. #4
    Ngày gia nhập
    02 2008
    Bài viết
    66

    Mình gợi ý bạn cách sau nhé.
    Mình thấy bài này có vẻ là phải xắp sếp củng điển trước rồi mới đến chất.
    2 bích <2 chuồn < 2 rô < 2 cơ < 3 bích...
    Thì mình có ý tưởng như sau.
    2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
    Thì bạn gán giá trị tương ứng như sau:
    0 4 8 ........
    Cứ điểm tiếp thì tăng 4 đơn vị.
    bích < chuồn < rô < cơ
    thì bạn cho nhận giá trị:
    0 1 2 3
    Giá trị của một quân bài sẽ bẳng điểm nó cộng với chất.
    Ví dụ quân
    3 bich=4+0=4
    4 rô=8+2=10

    Sau đó bạn thực hiện xắp sếp dãy giá trị đó bình thường.

  5. #5
    Ngày gia nhập
    04 2008
    Bài viết
    0

    Cám ơn nha. Mình cũng hiểu được một ít rồi nhưng không cài đặt được , mình dốt lập trình lắm .Giúp mình với

  6. #6
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    444

    Mặc định Giải thuật sắp xếp Topo

    Mình google và tìm được thuật toán này:

    -------------------- Nguồn: http://en.wikipedia.org/wiki/Topological_sorting --------------------
    The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges (Θ(|V|+|E|)).

    One of these algorithms works by choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" which have no incoming edges and insert them into a queue Q (at least one such node must exist if graph is acyclic). L is the list that will contain the nodes in topological sorted order after the end of the algorithm. Then,
    Code:
    L ← Empty list where we put the sorted elements
    Q ← Set of all nodes with no incoming edges
    while Q is non-empty do
        remove a node n from Q
        insert n into L
        for each node m with an edge e from n to m do
            remove edge e from the graph
            if m has no other incoming edges then
                insert m into Q
    if graph has edges then
        output error message (graph has a cycle)
    else 
        output message (proposed topologically sorted order: L)
    If the graph was a DAG, a solution is contained in the list L (the solution is not unique). Otherwise, the graph has at least one cycle and therefore a topological sorting is impossible.

    Note that, reflecting the non-uniqueness of the resulting sort, the structure Q need not be a queue; it may be a stack or simply a set. Depending on the order that nodes n are removed from set Q, a different solution is created.

    An alternative algorithm for topological sorting is based on depth-first search. Loop through the vertices of the graph, in any order, initiating a depth-first search for any vertex that has not already been visited by a previous search. The desired topological sorting is the reverse postorder of these searches. That is, we can construct the ordering as a list of vertices, by adding each vertex to the start of the list at the time when the depth-first search is processing that vertex and has returned from processing all children of that vertex. Since each edge and vertex is visited once, the algorithm runs in linear time.
    -------------------- Nguồn: http://en.wikipedia.org/wiki/Topological_sorting --------------------

    Ghi chú: thuật toán trên sắp xếp các đỉnh của một đồ thị có hướng không chu trình (acyclic directed graph), vốn dĩ đẳng cấu với tập hợp trang bị quan hệ so sánh không toàn phần. (Trong đồ thị, tồn tại 1 cạnh dẫn từ đỉnh x đến đỉnh y nếu và chỉ nếu trong tập hợp, phần tử x có thể so sánh với phần tử y và x < y.)
    Đã được chỉnh sửa lần cuối bởi Ada : 18-04-2008 lúc 04:59 PM. Lý do: danh từ

  7. #7
    Ngày gia nhập
    04 2008
    Bài viết
    0

    Bạn cho đoạn code này mình xem mà như là ko xem ý , chả hiểu gì cả.Dù sao cũng thanks !!!!!!

  8. #8
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    444

    Thôi để mình dịch tạm ra cho bạn vậy.

    ----------------------------------------------------------------------
    Các thuật toán sắp xếp topo thường có thời gian thực hiện là tỷ lệ thuận với tổng số đỉnh và số cạnh, Θ(|V|+|E|).

    Một trong các thuật toán này hoạt động bằng cách lần lượt chọn ra các đỉnh theo đúng thứ tự sắp xếp mà ta sẽ thu được. Trước hết, tìm một danh sách các "đỉnh bắt đầu" tức là các đỉnh không có cạnh dẫn vào, và đưa chúng vào một hàng đợi (queue) Q. (Nếu đồ thị không chu trình, chắc chắn tồn tại ít nhất một đỉnh như thế.) L sẽ là danh sách các đỉnh theo thứ tự sắp xếp topo sau khi thuật toán kết thúc. Ta có

    Code:
    L ← Danh sách rỗng. 
    Q ← Tập hơp các đỉnh không có cạnh nào dẫn vào chúng.
    while Q không rỗng do
        lấy một đỉnh n ra khỏi Q
        cho n vào L
        for each đỉnh m có cạnh e dẫn từ n vào m do
            xóa cạnh e khỏi đồ thị
            if m không còn cạnh nào dẫn vào nữa then
                cho m vào Q
    if đồ thị có cạnh then
        báo lỗi: đồ thị có chu trình
    else 
        báo kết quả: danh sách L.
    Nếu đồ thị là không chu trình, L sẽ chứa một nghiệm (nghiệm này không phải là duy nhất). Nếu ngược lại thì đồ thị là có chu trình và thứ tự sắp xếp topo không tồn tại.

    Chú ý rằng do tính chất không duy nhất của nghiệm, cấu trúc Q không nhất thiết phải là hàng đợi; nó có thể là một ngăn xếp (stack) hay chỉ đơn giản là một tập hợp. Tùy theo thứ tự lấy các đỉnh n ra khỏi tập Q, ta có thể tạo được một nghiệm khác.

    Một thuật toán khác cho việc sắp xếp topo được dựa trên việc duyệt theo chiều sâu (depth-first search). (...Bỏ một đoạn...)
    Đã được chỉnh sửa lần cuối bởi Ada : 18-04-2008 lúc 09:48 PM.

  9. #9
    Ngày gia nhập
    04 2008
    Bài viết
    0

    Cảm ơn nhiều nhiều....

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

  1. Giải thuật shaker sort. Giúp mình giải thuật với?
    Gửi bởi nguyenhai trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 29-01-2015, 10:53 PM
  2. Cần giúp đỡ về Thuật toán sắp xếp Topo
    Gửi bởi xathu10011992 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 04-01-2013, 06:53 PM
  3. Giải thuật Giải thuật Chia để trị, hướng đi với giải thuật này thế nào?
    Gửi bởi maivivan13 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 23-10-2012, 10:22 PM
  4. Bài tập C Cần giải giúp 3 câu trong đề thi kĩ thuật lập trình C và Cấu trúc dữ liệu và giải thuật
    Gửi bởi nguyenthi0602 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2012, 08:42 PM
  5. Giải thuật xắp xếp Quick sort, biểu diễn bằng hình ảnh giải thuật này?
    Gửi bởi yuklong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 9
    Bài viết cuối: 09-06-2012, 09:20 AM

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