Chủ đề này có 3 trả lời

[Anhmaster Ci5]

Mình có bài toán như thế này:
[size="3"]Sử dụng phương pháp đồ thị để giải bài toán dân gian (Bài toán 2).

Đặc tả đề tài:
Có hai cha con người nông dân đi mua vé tàu hoả.Người bán vé hỏi: ìChú bé này bao nhiêu tuổi ?”. Ông cha trả lời: ìCon trai tôi gấp 5 lần tuổi em gái nó, mẹ nó gấp 6 lần tuổi nó. Tuổi tôi thì bằng tuổi của vợ và hai con tôi cộng lại. Còn mẹ tôi thì bằng tuổi của cả gia đình chúng tôi cộng laị ì. Người bán vé tàu nói. ìThôi đủ rồi! con ông được miễn vé”.
Dựa vào đâu mà người bán vé tàu miễn vé cho chú bé? . Biết rằng, theo luật đường sắt thì trẻ em dưới 6 tuổi đi cùng người lớn sẽ được miễn vé.

Yêu cầu của đề .
-Minh hoạ bài toán bằng đồ thị.
-Thiết lập thuật toán.[/size]

Tôi được hướng dẫn là sử dụng phương pháp "VÉT CẠN " để giải mà tôi thì hôk có tài liệu.Ai có cách giải bài này hay EBOOK về thuật toán thì giúp tôi với.

[toanhoc]

Vét cạn là thử tất cả các khả năng có thể. Cái này thực ra không hẳn là thuật toán. Tuy nhiên, có 1 số cách vét cạn thông minh như Heuristics, hay greedy method

[Magus]

Tôi được hướng dẫn là sử dụng phương pháp "VÉT CẠN " để giải mà tôi thì hôk có tài liệu.Ai có cách giải bài này hay EBOOK về thuật toán thì giúp tôi với.

Thuật toán vét cạn:

http://en.wikipedia....te-force_search

Bạn có thể tham khảo sách "Phương pháp giải các bài toán trong tin học" của tác giả Trần Đức Huyên

Vét cạn là một trong những thuật toán giải bài toán tối ưu. Thuật toán vét cạn là thuật toán tìm phương án tối ưu của bài toán bằng cách lựa chọn một phương án trong tập hợp tất cả các phương án của bài toán để tìm ra phương án tối ưu. Trong nhiều bài toán, không gian các phương án quá lớn. Do vậy, khi áp dụng thuật toán vét cạn không đảm bảo về thời gian cũng như kĩ thuật. Vấn đề đặt ra là phải cải tiến thuật toán vét cạn như thế nào để giải quyết các yếu điểm đó. ở đây tôi giới thiệu với các bạn phương pháp đánh giá nhánh cận. Đây là phương pháp có thể hạn chế số phương án phải duyệt của bài toán. Trong quá trình duyệt ta luôn giữ lại 1 phương án là phương án mẫu, phương án mẫu là phương án có giá nhỏ nhất tại thời điểm đó. Phương pháp đánh giá nhánh cận là phương pháp tính giá của phương án ngay trong quá trình xây dựng các thành phần của phương án, có nghĩa là ta sẽ tính xem việc xây dựng phương án theo hướng đó có thể có thể tốt hơn phương án mẫu hay không. Nếu không tốt hơn ta lựa chọn hướng khác. Bằng cách này ta đã hạn chế được nhiều phương án mà chắc rằng trong đó không chứa phương án tối ưu. Một yêu cầu đặt ra là tính toán đặt nhánh cận như thế nào, để có thể hạn chế tối đa các phương án phải duyệt.

Bài toán áp dụng (Bài toán người du lịch):

Cho một mạng lưới gồm n thành phố. Một người muốn đi du lịch khắp các thành phố, mỗi thành phố đi qua đúng một lần và sau đó quay về thành phố xuất phát. Giả sử biết chi phí đi lại giữa các thành phố (0<a[i,j]). Hãy lập trình tìm phương án với tổng chi phí ít nhất.

Phương án của bài toán là x[1], x[2].. x[n], x[1]. Trong đó x[1] là đỉnh xuất phát, x là đỉnh thứ i trong hành trình của người du lịch. Lúc đó tổng chi phí S được tính như sau:

S = a[x[1],x[2]]+ a[x[2],x[3]]+...+ a[x[n-1],x[n]]+ a[x[n],x[1]].

Trong quá trình xây dựng các thành phần của phương án ta tiến hành đặt nhánh cận như sau:

Xây dựng thành phần thứ i của phương án (x) ta có tổng chi phí S của i-1 thành phần đã được xây dựng. Thành phần thứ i của phương án phải thoả mãn biểu thức sau:

S + a[x[i-1], x]+(n-i)*Amin +X1min < Min.

Trong đó: + Amin là chí phí nhỏ nhất trong bảng chi phí a[i,j].

+ X1min là chi phí nhỏ nhất từ x[1] đến các thành phố còn lại.

+ Min là chi phí của phương án mẫu.

Chương trình.

Các biến trong chương trình:

a:array[1..100,1..100] of integer; chứa bảng chi phí.

x,y:array[1..100]of 1..100 ; chứa phương án trong quá trình duyệt

chuaxet:array[1..100]of boolean;chứa trạng thái các thành phố. Nếu thành phố i đã nằm trong phương án đang duyệt->chuaxet=false. ngược lại chuaxet=true. Ban đầu các giá trị của chuaxet được khởi tạo =true.

Procedure Choice(S,i:integer);

Var j,k:integer;

Begin

for j:= 1 to n do

if (chuaxet[j]) then

begin

k:=S+ a[x[i-1],j];

if (k + (n-i)*Amin +X1min) < Min then

begin

chuaxet[j]:=false;

x:=j;

S:=S+ a[x[i-1],j];

if i = n then

begin

if S + a[x[n],x[1]]<Min then

begin

y:=x;

Min:=S+a[x[n],x[1]]

end;

end

else Choice(S,i+1);

chuaxet[j]:=true;

end;

end;

end;

Việc đặt nhánh cận như ví dụ trên tuy chưa thực sự tốt nhất, song nó cũng mô phỏng cho chúng ta cách đặt nhánh cận là như thế nào. Việc nắm bắt giải thuật là một chuyện, nhưng vấn đề làm sao ứng dụng giải thuật vào các vấn đề cụ thể lại là chuyện khác. Với phương pháp "đánh giá nhánh cận" ta phải tính toán sao cho việc đặt nhánh cận là sát nhất, để có thể cắt được càng nhiều trường hợp không phải xét càng tốt.

[toanhoc]

1 ví dụ của Greedy method. TSP là super bad NP since the approximation problem is also NP. Có 1 nhánh hay của algorithms là các approximation algorithms. Còn nhiều hơn nữa là combinatorial optimization. Anh Ngô Quang Hưng dạy môn này, có lecture notes hay, bạn vào website của anh ấy down về mà xem. OCW cũng có lecture notes về môn này thì phải, còn không mò vào Giga thì chắc ra cả đống. Tôi đã không đụng đến mấy thứ này từ nhiều năm nên giờ mòn rồi, ko cập nhật. Các bạn có món gì hay vác lên đây cho vui.