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

Đề tài: Thuật toán trong lý thuyết đồ thị ( Help)

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

    Mặc định Thuật toán trong lý thuyết đồ thị ( Help)

    Hix, em vừa nhận được đề tài thực tập tốt nghiệp như sau : " tìm hiểu các thuật toán trong lý thuyết đồ thị, xây dựng chương trình tìm đường đi". Các bác chỉ cho em biết là trong Lý Thuyết Đồ thì có bao nhiêu thuật toán và tên các thuật toán là gì nhé.

  2. #2
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Bạn thử tìm hiểu sơ qua sách của tác giả Lê Minh Hoàng đi, có lý thuyết đồ thị đó, sau đó bạn cần làm gì với đề tài của mình. Môn này không phải dễ dàng đâu.
    Bạn post thế này thì chịu
    Không biết ghi gì luôn ...

  3. #3
    Ngày gia nhập
    01 2008
    Bài viết
    3

    Hix, mình chuyên bên PHP, nhưng bốc thăm đề tài lại trúng môn này nên giờ chẳng biết phải làm sao nữa, để mình tìm mấy tài liệu đọc xem sao.

  4. #4
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    Trong lý thuyết đồ thị có rất nhiều thuật toán ví dụ:Tìm đường đi ngắn nhất(gồm thuật toán Dijkstra ,Ford-bellman,Floyd) ,thuật toán duyệt đồ thị (BFS và DFS),tìm chu trình Euler,chu trình hamilton,Cây khung nhỏ nhất(Prim và Kruskal)...và 1 số nữa.Nếu chịu khó làm các bài toán trong tin học bạn sẽ thấy đồ thị là 1 phần vô cùng quan trọng ( theo quan điểm của cá nhân mình ) vì thế bạn nên ngâm cứu cho kĩ.Chúc bạn học tốt.

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

    có bạn nào hiểu rõ về thuật toán tham lam chỉ hộ mình với
    mình đang cần giải một bài về tô màu độ thị bằng thuật toán tham lam?
    cảm ơn trước nha !

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

    Mặc định Thuật toán trong lý thuyết đồ thị ( Help)

    bạn nào biétvề bài toán sắp xếp có thể chỉ mình không

  7. #7
    Ngày gia nhập
    09 2008
    Nơi ở
    Thanh Pho Hồ Chi Minh
    Bài viết
    8

    Thuật toán Dijkstra.
    Thuật toán được xây dựng trên cơ sở gán cho các đỉnh của các nhãn tạm thời. Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất từ đỉnh s đến nó.Các nhãn này sẽ được biến đổi theo một thủ tục lặp, mà mỗi một bước lặp có một nhãn tạm thời trở thành nhãn cố định. Nếu nhãn của một đỉnh nào đó trở thành cố định thì nó sẽ cho ta không phải là cận trên mà là độ dài của đường đi ngắn nhất từ đỉnh s đến nó.

    Thuật toán Dijkstra được mô tả cụ thể như sau:
    procedure Dijkstra;
    /* Đầu vào : Đồ thị có hướng G=(V,E) với n đỉnh,
    s thuộc V là đỉnh xuất phát, a[u, v], u, v thuộc V, ma trận trọng số;
    Giả thiết: a[u,v]>=0, u,v thuộc V.
    Đầu ra: Khoảng cách từ đỉnh s đến tất cả các đỉnh còn lại d[v], v thuộcV.
    Trước[v], v thuộc V, ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v */
    begin
    // Khởi tạo
    for v thuộc V do
    begin
    d[v]:=a[s,v];
    Truoc[v]:=s;
    end;
    d[s]:=0; T:=V\{s};//Tập T là tập các đỉnh tạm thời
    // Bước lặp
    while T khác rỗng do
    begin
    Tìm đỉnh u thuộc T thỏa mãn d[u]=min{d[z]:z thuộc T};
    T:= T\{u}; //Cố định nhãn của đỉnh u
    for v thuộc T do // Gán nhãn lại cho các đỉnh trong T
    if d[v]>d[u]+a[u,v] then
    begin
    d[v]:=d[u]+a[u,v];
    Truoc[v]:=u;
    end;
    end;
    end;
    Con đường IT lắm gian nan.

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

  1. Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++
    Gửi bởi rox_rook trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 31
    Bài viết cuối: 30-01-2015, 10:41 PM
  2. Project Demo một số thuật toán Lý thuyết đồ thị
    Gửi bởi zkday2686 trong diễn đàn Dự án & Source code VC++
    Trả lời: 5
    Bài viết cuối: 28-09-2013, 04:53 PM
  3. [ Solved ]Thuật toán trong cây nhị phân
    Gửi bởi thientran trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 01-06-2008, 03:06 PM
  4. [Solved]Lỗi cơ bản trong một thuật toán sắp xếp đơn giản
    Gửi bởi hacker_mubaohiem trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 21-03-2008, 06:35 PM
  5. Lý thuết đồ thị | Bài tập Lý thuyết đồ thị
    Gửi bởi soda_chanhmuoi trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 11-02-2008, 08:01 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