PDA

View Full Version : Co ai ranh ve thuat toan nhanh can khong?



hoangtu04
12-03-2004, 02:03
Tui dang bi voi thuat toan nhanh can de giai bai toan nguoi du lich , ai biet thi giup tui voi.( Sao tui ko go duoc Tieng Viet?). Cam on nhieu lam!!!!!!!

Vui lòng gửi bài viết bằng tiếng Việt có dấu - vikhoa

songok
12-03-2004, 02:52
Minh khong ro lam ve bai toan nguoi du lich , ban co the dua yeu cau cua de bai duoc khong ?

Vui lòng gửi bài viết bằng tiếng Việt có dấu - vikhoa

hoangtu04
13-03-2004, 23:12
Có một người muốn đi du lịch qua n thành phố, mỗi thành phố qua đúng 1 lần rồi sau dó quay về thành phố xuất phát. Giả sử C[i,j] là chi phí để đi từ thành phố i đến thành phố j. Hãy tim cách đi cho người du lịch để chi phí là nhỏ nhất.
Dữ liệu vào cho trong file văn bản THANHPHO.INP. Dòng đầu ghi 1 số là số thành phố, n dòng tiếp theo , mõi dong ghi n số là chi phí đi từ tp i đến thành phố j.
VD:
4
0 12 2 9
12 0 5 9
2 5 0 11
9 9 11 0
Dữ liệu ra cho vào file THANHPHO.OUT gồm 1 dòng ghi n số là thứ tự hành trình qua các thành phố đó.

hoangtu04
13-03-2004, 23:14
Ai rành về thuật toán này thì giúp tui với nhé!

jiSh@n
15-03-2004, 08:42
Bạn đọc trong cuốn Toán rời rạc......

Srono
15-03-2004, 09:31
Lên google search Traveling Saleman Problem (TSP), đọc cả ngày không hết.

moibelgal
15-03-2004, 21:44
Hic , ebook thì không thằng nào không biết Search, chủ yếu là giải thích rõ ràng ngay lúc này.
Còn về thuật toán nhánh cận thì đây là thuật toán rất cơ bản trong Lí thuyết đồ thị , nếu bạn yêu thích thuật toán thì bạn cần những quyển như Cẩm nang thuật toán ( Robert Segewick - sách dịch , 2t) hay các quyển Cấu trúc dữ liệu , Lí thuyết đồ thị đều có thuật toán này. Nếu không muốn mua sách , bạn có thể tìm thấy nó trên www.thnt.com.vn( tôi quên nó nằm số báo nào rồi , bạn tự tìm nhé ! )

ngthanhbinh
15-03-2004, 22:43
Minh lam thuat toan nay roi. Minh se goi vao lan sau.

Vui lòng gửi bài viết bằng tiếng Việt có dấu - vikhoa

kickme!
19-03-2004, 22:18
Thuật toán này trong trí tuệ nhân tạo gọi là GTS,thuật toán này có 2 loại GTS1 và GTS2.GTS1 thì chỉ tìm được 1 đường đi thôi còn GTS2 có thể tìm được đường đi ngắn nhất:Thụât toán GTS1 nói chung là như vầy:Đầu tiên chọn thành phố xuất phát,tìm đường đi đến TP gần nhất,lưu vào mảng đường đi và cộng dồn chi phí và loại TP vừa đi đến ra khỏi mảng ban đầu,sau đó lại tìm đường đến các TP gần với TP vừa tìm được.
Còn GTS2 thì chọn n TP ban đàu,sau đó ứng với mỗi TP ban đầu đó ta gọi GTS1,cuối cùng so sánh chi phí để chọn đường đi ngắn nhất.