Giải thuật AT – giá thành cực tiểu

 

1. Tìm kiếm đường đi có giá thành cực tiểu – Thuật toán AT
Cho đồ thị G= (V, E) biểu diễn bài toán với đỉnh xuất phát n0 và tập đích DICH xác định.
Với mỗi phép chuyển trạng thái n(i)->n(i+1) tốn chi phí c(i, i+1), ở đây có thể xem là trọng số của cung nối n(i) và n(i+1)
Phương pháp
Tương tự phương pháp tìm kiếm theo chiều sâu, nhưng tại mỗi biết ta tính giá thành của mỗi đỉnh và chọn đỉnh có giá thành tối ưu nhất
2. Giải thuật
Input:
Đồ thị G = (V,E), Đỉnh xuất phát n0
Hàm chi phí c
Tập các đỉnh đích DICH
Output:
Đường đi từ đỉnh n0 đến đỉnh n* in DICH sao cho g(n*) = MIN


bool result = false;
openList.Push(n0);
while (!openList.IsEmpty())
{
node = openList.Pop();
if (node.Equals(n*))
{
result = true;
break;
}
closeList.Push(node);
for (n in Tn(node))
{
if (!openList.InList(n) && !closeList.InList(n))
{
openList.Push(n);
n.Cost = node.Cost + Edge(node, n).Value;
BeforeOfNode(n, node);
}
else if (!closeList.InList(n) && n.Cost > node.Cost + Edge(node, n).Value)
{
n.Cost = node.Cost + Edge(node, n).Value;
BeforeOfNode(n, node);
}
}
openList.Sort(SortType.ASCENDING);//sắp xếp lại để chọn đỉnh tối ưu nhất ở đỉnh Stack
}
if (result)
{
DisplayResult();
}
else
{
NotFound();
}

 

3. Ví dụ

Cho đồ thị như hình vẽ
Đỉnh xuất phát là (1), đỉnh đích là (10)

Các bước chi tiết thực hiện giải thuật

Kết quả
Chi phí là 6

  1. #1 by hongnhung on Tháng Mười 17, 2010 - 02:12

    Cám ơn vì bài viết.

  2. #2 by Hưng HAT on Tháng Mười Một 3, 2010 - 22:15

    Bạn có thể gửi cho mình code như hình vẽ để mình tham khảo ko🙂

    thanks b nhiều, email mình: nguyenhung1121990@gmail.com
    YM: now_and_forever_t12

  3. #3 by HUNG on Tháng Mười Hai 14, 2010 - 14:08

    m đang rất cần code giai thuật này. nếu được thì bạn có thể chia sẻ mình với. thank nhiu!!
    hungmt3@gmail.com

  4. #4 by hung on Tháng Tư 5, 2011 - 11:08

    Bạn ơi bạn có tất cả code của các thuật toán về nguyên lý tham lam, nguyên lý thứ tự, leo đồi, At, Akt, A*, taci, Tháp Hà Nội, mạng ngữ nghĩa, TG vương hạo, Robinson, Quinlan, Tô màu bản đồ k? Nếu bạn có cho mình xin dc k? làm bằng c#. mình học về phần này nhưng mà ngu quá chẳng bít gì ka, giờ mình đang có bài tập lớn mình muốn xem bài của bạn để học hỏi thêm. Mong bạn giúp đỡ. Cảm ơn bạn nhiều!
    Mail: hnnguyenvanhung8@gmail.com

  5. #5 by Elnino on Tháng Tư 6, 2011 - 21:20

    Bạn ơi có thể gửi cho mình code như hình vẽ để mình tham khảo không?
    Mail của mình là :se7en_Japan_2006@yahoo.com

  6. #6 by anhnhut on Tháng Năm 11, 2011 - 09:23

    ban cho minh code bai nay bang C# duoc k,minh dang rat can,cam on ban nhe,gui qua mail dum mjnh nha anhnhut.ho@gmail.com

  7. #7 by hoale on Tháng Tám 15, 2011 - 21:58

    Có anh chị nào có code thuật toan AT này ko gởi cho em tham khảo với : hoale.info@gmail.com
    xin cảm ơn mấy anh chị.

  8. #8 by sonnqs on Tháng Mười Một 1, 2011 - 20:38

    ban cho minh code bai nay bang C# duoc k,minh dang rat can,cam on ban nhe,gui qua mail dum mjnh nha sonnq.sp@gmail.com

  9. #9 by tuấn on Tháng Mười Hai 28, 2011 - 22:00

    ban cho minh code bai nay bang C# duoc k,minh dang rat can,cam on ban nhe,gui qua mail dum mjnh nha anhtuankhmt3k5@gmail.com

  10. #10 by Giải thuật AT – giá thành cực tiểu on Tháng Bảy 22, 2012 - 23:14

    bạn gửi cho mình xin code này vào mail tam141991@gmail.com với mình đang rất cần

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: