Giải thuật A* – tìm kiếm cực tiểu

 

1. Tìm kiếm cực tiểu sử dụng hàm đánh giá – Thuật toán A*

Đối với nhiều bài toán, việc tìm kiếm đường đi cực tiểu sẽ được định hướng tập trung xung quanh  đường đi tốt nhất; nếu sử dụng các thông tin đặc tả về bài toán gọi là các heuristic.
Đối với việc tìm kiếm đường đi với chi phí cực tiểu, người ta sử dụng hàm đánh giá heuristic như sau:
Gọi g(n): giá cực tiểu đường đi từ n0->n. Tại đỉnh n, g(n) xác định được.
Gọi h(n): giá cực tiểu đường đi từ n->DICH, h(n) không xác định được Þ người ta tìm cách ước lượng giá trị này.
Đặt f0(n)=g0(n)+h0(n): dự đoán chi phí cực tiểu của đường đi từ n0->DICH có đi qua đỉnh n.
g0(n) là chi phí của đường đi từ đỉnh xuất phát đến đỉnh n tại thời điểm đang xét. h0(n) là ước lưọng (dự đoán) chi phí đường đi từ đỉnh n đến đích. Việc chọn giá trị xấp xỉ h0(n) của h(n) không có một phương pháp tổng quát và được xem như một nghệ thuật. Giá trị này sẽ do các chuyên gia đưa ra.
Lúc này giải thuật tìm kiếm cực tiểu sẽ thay việc xét hàm g bởi hàm f.
2. Giải thuật

Input:
Đồ thị G = (V,E), Đỉnh xuất phát n0
Hàm chi phí c: c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j
h: h(n) xác định dự đoán chi phí tối ưu của đường đi từ đỉnh n đến đích.

Tập các đỉnh đích DICH
Output:
Đường đi từ đỉnh n0 đến đỉnh n* thuộc DICH với giá thành cực tiểu


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 + n.Huerictis;
BeforeOfNode(n, node);
}
else if (!closeList.InList(n) && n.Cost > node.Cost + Edge(node, n).Value + n.Huerictis)
{
n.Cost = node.Cost + Edge(node, n).Value + n.Huerictis;
BeforeOfNode(n, node);
}
}
openList.Sort(SortType.ASCENDING);//sắp xếp theo chi phí của mỗi đỉnh, giá trị Min ở đỉnh Stack
}

if (result)
{
DisplayResult();
}
else
{
NotFound();
}

 

3. Ví dụ

Cho đồ thị như hình vẽ
Với giá trị Hueristic của mỗi đỉnh như sau

H(1) = 1  H(2) = 3  H(3) = 5   H(4) = 6  H(5) = 4
H(6) = 1  H(7) = 2  H(8) = 3   H(9) = 1  H(10) = 6
Đỉ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ả



Với chi phí cực tiểu là 18

  1. #1 by Nguyễn Thanh Tâm on Tháng Mười 28, 2010 - 22:53

    Mình tên là Nguyễn Thanh Tâm, bạn có thể cho mình xin code của bài toán:
    Không gian trạng thái được mô tả là hàm 3 biến nào đó. Hãy xây dựng chương trình tìm phần tử lớn nhất trên không gian đó phương phương pháp Gradient.
    Mình cảm ơn bạn rất nhiều!
    Bạn reply giúp mình theo địa chỉ : nguyenthanhtam1810@gmail.com nhé

    • #2 by mucdong06 on Tháng Mười 29, 2010 - 07:33

      Bài toán này mình không xây dựng nên không có code cho bạn được, nếu bạn câng code của mấy thuật toán mình đưa ở đây mình có thể share

      Thân!

    • #3 by Nguyễn Thanh Tâm on Tháng Mười Một 5, 2010 - 11:40

      Mình cảm ơn bạn nha!

  2. #4 by Le Trang on Tháng Ba 27, 2011 - 07:41

    Cho minh xin code cua Tim kiem sau dan, or bai toan tro choi craziro voi! va co the giup minh cach chay bang tay thuat toan tim kiem rong (BFS) voi! Thank you nhieu nhieu! neu duoc thi gui wa mail cho minh voi nha! letrangsweet.1472008@gmail.com
    Mong som duoc nhan hoi am cua ban!

  3. #5 by tùng on Tháng Năm 27, 2011 - 02:52

    bạn cho mình xin code bài toán luồng cực tiểu này được ko?
    phamvantung1628@gmail.com
    thank bạn nhiều

  4. #6 by QUốc Cường on Tháng Mười 14, 2011 - 15:33

    chào bạn. mình đang nghiên cứu thuật tóan này, bạn có thể share full code c# cho mình được ko
    thank bạn nhiều
    quoccuong012007@yahoo.com

  5. #7 by Quang Sơn on Tháng Mười Hai 6, 2011 - 20:31

    chào bạn. mình đang làm đồ án các thuật tóan này, nhưng viết bằng VB.Net bạn có thể share full code cho mình tham khảo được ko za??
    cám ơn bạn nhiều lắm!!
    sonnq.sp@gmail.com

  6. #8 by Nguyen on Tháng Mười Hai 8, 2011 - 08:59

    Mình đang làm BTL về mấy thuật toán AT,AKT, A*. Bạn có thể cho mình xin code của thuật toán này ko(cả 3 thì càng tốt). thank bạn nhiều.

  7. #9 by Nguyen on Tháng Mười Hai 8, 2011 - 09:00

    email của mình: saucaca@gmail.com

  8. #10 by may bay on Tháng Mười Một 8, 2012 - 21:43

    Bạn có thể cho mình xin code ví dụ được không mình cũng chưa hiểu lắm tại sao ra 18 nữa, xin cảm ơn bạn, Email: quyendpt.dhth5@gmail.com

  9. #11 by Lương Thanh Cường on Tháng Mười Một 12, 2012 - 19:21

    ban oi cho hoi sao chon duoc duong 1-3-6-10 la duong cuc tieu z?

  10. #12 by minh tuấn on Tháng Mười Một 13, 2012 - 00:39

    Cho mình xin mail source code nha bạn trantuan500@gmail.com

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: