Yêu cầu:

Viết chương trình cho các thuật toán đã phân tích và xây dựng

(Theo ngôn ngữ C)

1.Bài toán tìm đường trong mê cung:

Xét mê cung như một đồ thị bao gồm các nút và các cạnh nối biểu hiện các đường đi giữa các nút.

Tìm đường đi từ nút A đến nút B

M = (Mij)

m(ij) = 1 Nếu có cạnh nối từ i đến j

m (ij) = 0 nếu ngược laj

Bộ nghiệm đường đi cần xác định dãy v1...vn

Với v1=A;vn=B;vi=1...n(vi A,B)

Thuật toán:

Try(i)

For(vi=1...n)

If(m v = 1 and Daqua[v ] = False)

x = v

Daqua[v] = True

If(xi=B)( là trạng thái kết thúc thì in ra nghiệm x1,...,xi)

Else Try(i+1)

Daqua[i] = False

End

2. Bài toán liệt kê dãy nhị phân chiều dài n:

( Áp dụng giải thuật quay lui)

Liệt kê các cấu hình nghiệm: x1...xn;

Thuật toán:

x

Try(i)

For(v=0,1)

x =v;

if(i=n)

<In nghiệm (x1,...,xn)>

Else

Try (i+1)

End

3.Bài toán người bán hàng: (TSP)

Có n thành phố,được nối với nhau bởi các con đường có độ dài

d = Độ dài đường đi từ i đến j

d = Nếu không có đường đi

x = (x ,...,x ) x (1,m)

Thuật toán:

Vét cạn:

Sinh hoán vị n đỉnh

Mỗi hoán vị tính tổng chiều dài

Tìm hoán vị có tổng min

Quay lại:

Sinh phần tử i là đỉnh xi

Sinh tiếp phần tử i+1 là x nếu d

Tìm được 1 nghiệm, tính tổng chiều dài.

So sánh với tổng chiều dài ngắn nhất hiện có.

Cập nhật lại nếu cần

Thuật toán:

Try(i,s)

For(v=1...n)

If(Daqua[v] = false and d v )

T = S + d v

If(T < BestCost)

x = v

Daqua[v] = True

If( x = A and i = n+1)

< In nghiệm (x1,..,xn)>

<Chấp nhận BestCost)>

Else

Try(i+1,T)

Daqua[v] = False

End if

End if

End for.

Lời gọi ban đầu của thuật toán:

Daqua[v=1...n] = False

BestCost =

Try ( A,0);