tailieunhanh - Một số vấn đề về thuật toán part 8

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ả | Bài toán đường đi của người bán đượ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 .