PDA

View Full Version : Xin hoi chut ve chu trinh



songok
04-07-2004, 09:28
Yeu cau la cho mot do thi vo huong co n dinh, ta tim mot duong di co tong trong so ngan nhat ma qua tat cac cac dinh ( giong nhu duong di Hamilton vay nhung co them tong trong so ) thi minh lam nhu sau : liet ke tat cac cac duong di Hamilton roi so sanh trong so xem trong so nao nho nhat thi lay . Khong biet cach nao co kha thi khogn ? Xin chi giup

Hay la ta phoi hop giua Dijsktra + Hamilton de lam

vokeo
08-07-2004, 20:18
bài này có thuật tóan đấy chứ đây là bài tìm chu trình halminton ngắn nhất , bài này có trong các sách lý thuyết đồ thị mà bạn thử tìm xem nếu hôm nào có thời gian tui post thuật toán lên cho,thuật toán đơn gian nhưng nói ra thì hơi dài dòng bạn cứ tìm truớc đi nếu ko có thì nói tui post lên

songok
11-07-2004, 08:29
mình có xem rồi bài này là bài toán du lịch, tìm chu trình Hamilton với tổng trọgn số là nho nhất nhưng giải bằng thuật toán rẻ nhánh, mình thấy cũng khó cài nhưng nếu bạn có thể cài bằng thuật toán nào dơn giản hơn xin gửi cho mình
Cám ơn nhiều

thailehuy
13-07-2004, 02:51
Tui thấy thuật toán rẽ nhánh là đơn giản nhất rồi còn gì, chỉ việc dùng vài cái Set lưu lại các cạnh, đỉnh cùng trọng số là được mà

jiSh@n
13-07-2004, 09:09
NẾu tìm tất cả các chu trình Hamilton thì rất chậm, trong khi bài toán này có thuật toán giải là nhánh-cận (bounce and branch) cơ mà.

thailehuy
14-07-2004, 02:30
Cái nhánh cận đó cũng tương tự như là rẽ nhánh, chỉ khác là thay vì tìm đỉnh kế tiếp để có trọng số nhỏ nhất thì ta tìm cạnh liền kề có trọng số nhỏ nhất

snow_white
03-09-2004, 14:07
bài này có thuật tóan đấy chứ đây là bài tìm chu trình halminton ngắn nhất , bài này có trong các sách lý thuyết đồ thị mà bạn thử tìm xem nếu hôm nào có thời gian tui post thuật toán lên cho,thuật toán đơn gian nhưng nói ra thì hơi dài dòng bạn cứ tìm truớc đi nếu ko có thì nói tui post lên

Chắc bạn nhầm chứ bài này làm gì có thuật toán tốt? Chỉ riêng tìm đường cho nó đã la NP rồi, lại còn tìm đường ngắn nhât nữa? Bài này chỉ giải được băng quay lui thôi. Nhưng còn tuỳ vào dữ liệu sẽ có được cách giải hay hơn đấy.