Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Một số vấn đề về thuật toán part 8
Đang chuẩn bị liên kết để tải về tài liệu:
Một số vấn đề về thuật toán part 8
Minh Hùng
75
24
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tham khảo tài liệu 'một số vấn đề về thuật toán part 8', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 5.6 Bài toán đường đi của người bán hàng.169 được vì bài toán đường đi của người bán hàng thuộc lớp những bài toán khó NP khó ta tin rằng không có thuật toán có độ phức tạp đa thức nào dành cho nó. Bài toán đường đi người bán hàng tương dương với việc tìm giá nhỏ nhât của chu trinh Hamilton trong một đồ thị định hướng trọng lượng G. Ta có thể giả thiết mà không mất tính tổng quát rằng G là một đổ thị định hướng đầy đủ kn V Ể ỏ dây IVI . n và Ê bao gổm tất cả những cặp đỉnh khác nhau u v M v V. Cho một đồ thị định hướng trọng lượng G V E ta đơn thuần mở rộng trọng lượng c cho kn bằng cách đặt c m v với mọi cạnh n v E. Khi đó bài toán đường đi người bán hàng với đồ thị đầy đủ không định hướng Kn với -giá trọng lượng c là trường hợp đặc biệt của bài toán đường đi người bán hàng cho đồ thị định hướng kn Vối mỗi cạnh e của Kn ta gán đồng thời hai chiều e và e của kn tương ứng với e trọng lượng c e . Ta xét chu trình Hamilton H của k không mất tính tổng quát ta giả sử đỉnh 1 khỏi đầu và kết thúc của H. Kí hiệu ì là đỉnh đầu tiên mà H tới sau khi dời đỉnh 1 vấ kí hiệu Hi là đường con của H từ đỉnh i tới đỉnh 1 mà nó đi qua mỗi đỉnh của kn một lần đường như vậy gọi là đường Hamilton . Nếu H là chu trình Hamilton giá nhồ nhất thì Hi phải là đường ngắn nhất từ i tới 1 mà những đỉnh trong của nó bao gổm tập hợp V 1 í một đường ngắn nhất p nối hai đỉnh i và j là đường có cực tiểu cost p ịồ đây cost p là tổng tất cả giá chi phí trên mọi cạnh của p . Bây giờ ta xét tập con bât kì Ư của V. Với ì là đỉnh không thuộc ư ta kí hiệu mincost i ự là giá chi phí của đường ngắn nhất chi phí tối thiểu p từ ì đèn 1 mà những đỉnh trong của nó nằm trong tập í . Chú ý rằng vì p là đường ngắn nhất p phải đi qua mỗi đỉnh của lỉ một lần. Cũng chú ý rằng minccst 1 V 1 là chi phí nhỏ nhất của chu trình Hamilton mà nó chính là đường đi tối ưu của người bán hàng. Một lời giải của bài toán là tìm đường ngắn nhất p ÍV1. Vp 1 từ đỉnh ì đến đỉnh I ở đây V1 . Vp e u. Nó có thể biểu diễn như dãy những .
TÀI LIỆU LIÊN QUAN
Ebook Một số vấn đề về thuật toán - Nguyễn Hữu Điền
Giáo trình Một số vấn đề về thuật toán - Nguyễn Hữu Điển
Đề cương Luận văn Thạc sĩ Kỹ thuật: Nghiên cứu đánh giá thực trạng và đề xuất một số giải pháp nâng cao mức độ đảm bảo an toàn và vệ sinh môi trường cho các công trình xây dựng dân dụng tại thành phố mới Bình Dương
Luận văn Thạc sĩ Kỹ thuật: Phân tích thực trạng và đề xuất một số giải pháp hoàn thiện hệ thống quản lý an toàn vệ sinh lao động tại công ty TNHH điện Stanley Việt Nam
Giáo trình - Một số vấn đề về thuật toán - chương 7
Giáo trình - Một số vấn đề về thuật toán - chương 1
Giáo trình - Một số vấn đề về thuật toán - chương 2
Giáo trình - Một số vấn đề về thuật toán - chương 3
Giáo trình - Một số vấn đề về thuật toán - chương 4
Giáo trình - Một số vấn đề về thuật toán - chương 5
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.