Đề Xuất 5/2022 # Bài Toán Người Bán Hàng – Là Gì Wiki # Top Like

Xem 13,068

Cập nhật nội dung chi tiết về Bài Toán Người Bán Hàng – Là Gì Wiki mới nhất ngày 21/05/2022 trên website Tuvanduhocsing.com. Hy vọng thông tin trong bài viết sẽ đáp ứng được nhu cầu ngoài mong đợi của bạn, chúng tôi sẽ làm việc thường xuyên để cập nhật nội dung mới nhằm giúp bạn nhận được thông tin nhanh chóng và chính xác nhất. Cho đến nay, bài viết này đã thu hút được 13,068 lượt xem.

--- Bài mới hơn ---

  • Giới Thiệu Về Phú Quốc Đảo Ngọc
  • Kinh Nghiệm Du Lịch Phú Quốc Siêu Tiết Kiệm
  • Mua Balo The North Face Giá Rẻ Ở Đâu Tại Đà Nẵng?
  • Túi Du Lịch Giá Rẻ Tại Hà Nội. Gia Công Balo – Túi Xách – Đồng Phục Chỉ 65K
  • Balo Du Lịch Hải Phòng Giá Rẻ. Tnbags.vn
  • Bài toán người bán hàng (tiếng Anh: travelling salesman problemTSP) là một bài toán NP-khó thuộc thể loại tối ưu rời rạc hay tổ hợp được nghiên cứu trong vận trù học hoặc lý thuyết khoa học máy tính. Bài toán được phát biểu như sau. Cho trước một danh sách các thành phố và khoảng cách giữa chúng, tìm chu trình ngắn nhất thăm mỗi thành phố đúng một lần.

    Bài toán được nêu ra lần đầu tiên năm 1930 và là một trong những bài toán được nghiên cứu sâu nhất trong tối ưu hóa. Nó thường được dùng làm thước đo cho nhiều phương pháp tối ưu hóa. Mặc dù bài toán rất khó giải trong trường hợp tổng quát, có nhiều phương pháp giải chính xác cũng như heuristic đã được tìm ra để giải quyết một số trường hợp có tới hàng chục nghìn thành phố.

    Ngay trong hình thức phát biểu đơn giản nhất, bài toán TSP đã có nhiều ứng dụng trong lập kế hoạch, hậu cần, cũng như thiết kế vi mạch.

    Trong lý thuyết độ phức tạp tính toán, phiên bản quyết định của TSP (cho trước độ dài L, xác định xem có tồn tại hay không một chu trình đi qua mỗi đỉnh đúng một lần và có độ dài nhỏ hơn L) thuộc lớp NP-đầy đủ. Do đó, có nhiều khả năng là thời gian xấu nhất của bất kì thuật toán nào cho TSP đều tăng theo cấp số nhân với số thành phố.

    TSP có một vài ứng dụng thậm chí trong dạng thức nguyên thuỷ của nó như lập kế hoạch, logistic, và sản xuất các microchip. Thay đổi đi chút ít nó xuất hiện như một bài toán con trong rất nhiều lĩnh vực như việc phân tích gen trong sinh học. Trong những ứng dụng này, khái niệm thành phố có thể thay đổi thành khách hàng, các điểm hàn trên bảng mạch, các mảnh DNA trong gen, và khái niệm khoảng cách có thể biểu diễn bởi thời gian du lịch hay giá thành, hay giống như sự so sánh giữa các mảnh DNA với nhau. Trong nhiều ứng dụng, các hạn chế truyền thống như giới hạn tài nguyên hay giới hạn thời gian thậm chí còn làm cho bài toán trở nên khó hơn.

    Trong lý thuyết của độ phức tạp tính toán, phiên bản quyết định của bài toán TSP thuộc lớp NP-đầy đủ. Vì vậy không có giải thuật hiệu quả nào cho việc giải bài toán TSP. Hay nói cách khác, giống như thời gian chạy xấu nhất cho bất ký giải thuật nào cho bài toán TSP tăng theo hàm mũ với số lượng thành phố, vì vậy thậm chí nhiều trường hợp với vài trăm thành phố cũng đã mất vài năm CPU để giải một cách chính xác.

    Lịch sử

    Nguồn gốc của bài toán người bán hàng vẫn chưa được biết rõ. Một cuốn sổ tay dành cho người bán hàng xuất bản năm 1832 có đề cập đến bài toán này và có ví dụ cho chu trình trong nước Đức và Thụy Sĩ, nhưng không chứa bất kì nội dung toán học nào.

    Bài toán người bán hàng được định nghĩa trong thế kỉ 19 bởi nhà toán học Ireland William Rowan Hamilton và nhà toán học Anh Thomas Kirkman. Trò chơi Icosa của Hamilton là một trò chơi giải trí dựa trên việc tìm kiếm chu trình Hamilton. Trường hợp tổng quát của TSP có thể được nghiên cứu lần đầu tiên bởi các nhà toán học ở Vienna và Harvard trong những năm 1930, đặc biệt là Karl Menger, người đã định nghĩa bài toán, xem xét thuật toán hiển nhiên nhất cho bài toán, và phát hiện ra thuật toán láng giềng gần nhất là không tối ưu.

    Hassler Whitney ở đại học Princeton đưa ra tên bài toán người bán hàng ngay sau đó.

    Trong những năm 1950 và 1960, bài toán trở nên phổ biến trong giới nghiên cứu khoa học ở châu Âu và Mỹ. George Dantzig, Delbert Ray Fulkerson và Selmer M. Johnson ở công ty RAND tại Santa Monica đã có đóng góp quan trọng cho bài toán này, biểu diễn bài toán dưới dạng quy hoạch nguyên và đưa ra phương pháp mặt phẳng cắt để tìm ra lời giải. Với phương pháp mới này, họ đã giải được tối ưu một trường hợp có 49 thành phố bằng cách xây dựng một chu trình và chứng minh rằng không có chu trình nào ngắn hơn. Trong những thập niên tiếp theo, bài toán được nghiên cứu bởi nhiều nhà nghiên cứu trong các lĩnh vực toán học, khoa học máy tính, hóa học, vật lý, và các ngành khác.

    Năm 1972, Richard M. Karp chứng minh rằng bài toán chu trình Hamilton là NP-đầy đủ, kéo theo bài toán TSP cũng là NP-đầy đủ. Đây là một lý giải toán học cho sự khó khăn trong việc tìm kiếm chu trình ngắn nhất.

    Một bước tiến lớn được thực hiện cuối thập niên 1970 và 1980 khi Grötschel, Padberg, Rinaldi và cộng sự đã giải được những trường hợp lên tới 2392 thành phố, sử dụng phương pháp mặt phẳng cắt và nhánh cận.

    Trong thập niên 1990, Applegate, Bixby, Chvátal, và Cook phát triển một chương trình mang tên Concorde giải được nhiều trường hợp có độ lớn kỉ lục hiện nay. Gerhard Reinelt xuất bản một bộ dữ liệu các trường hợp có độ khó khác nhau mang tên TSPLIB năm 1991, và nó đã được sử dụng bởi nhiều nhóm nghiên cứu để so sánh kết quả. Năm 2005, Cook và cộng sự đã giải được một trường hợp có 33810 thành phố, xuất phát từ một bài toán thiết kế vi mạch. Đây là trường hợp lớn nhất đã được giải trong TSPLIB. Trong nhiều trường hợp khác với hàng triệu thành phố, người ta đã tìm được lời giải với sai số không quá 1% so với lời giải tối ưu.

    Phát biểu

    Có một người giao hàng cần đi giao hàng tại n thành phố. Anh ta xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, và khoảng cách từ một thành phố đến các thành phố khác đã được biết trước. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất.

    Dưới dạng đồ thị

    Bài toán người bán hàng có thể được mô hình hoá như một đồ thị vô hướng có trọng số, trong đó mỗi thành phố là một đỉnh của đồ thị còn đường đi giữa các thành phố là mỗi cách. Khoảng cách giữa hai thành phố là độ dài cạnh. Đây là vấn đề cực tiểu hoá với điểm đầu và điểm cuối là cùng một đỉnh sau khi thăm hết các đỉnh còn lại đúng một lần. Mô hình này thường là một đồ thị đầy đủ (giữa mỗi cặp đỉnh đều có cạnh). Nếu không có đường giữa hai thành phố thì có thể thêm một cạnh với độ dài đủ lớn vào đồ thị mà không ảnh hưởng đến kết quả tối ưu sau cùng.

    Đối xứng và bất đối xứng

    Trong bài toán TSP đối xứng, khoảng cách giữa hai thành phố là không đổi dù đi theo chiều nào. Như vậy đồ thị trong bài toán này là đồ thị vô hướng. Việc đối xứng này làm giảm đi một nửa số lời giải có thể. Trong khi đó, với bài toán TSP bất đối xứng thì đường đi giữa hai thành phố có thể chỉ một chiều hoặc có độ dài khác nhau giữa mỗi chiều, tạo nên đồ thị có hướng. Các tai nạn giao thông, đường một chiều hay phí hàng không giữa các thành phố với phí điểm xuất phát và điểm đến khác nhau là những ví dụ về sự bất đối xứng.

    Tìm kiếm lời giải

    Cũng như các bài toán NP-khó khác, có các hướng sau đây để tiếp cận bài toán người bán hàng.

    • Thiết kế thuật toán tìm kiếm lời giải tối ưu (thường hoạt động hiệu quả cho những trường hợp nhỏ).
    • Thiết kế thuật toán heuristic để tìm những lời giải tốt nhưng không nhất thiết tối ưu.
    • Thiết kế thuật toán xấp xỉ để tìm những lời giải không quá lớn so với lời giải tối ưu.
    • Giải quyết các trường hợp đặc biệt.

    Ví dụ minh họa

    Sử dụng thuật toán láng giềng gần nhất (tiếng Anh: nearest neighbour algorithm)

    Các bước của thuật toán:

    • Bước 1: Chọn một đỉnh bắt đầu V.
    • Bước 2: Từ đỉnh hiện hành chọn cạnh nối có chiều dài nhỏ nhất đến các đỉnh chưa đến. Đánh dấu đã đến đỉnh vừa chọn.
    • Bước 3: Nếu còn đỉnh chưa đến thì quay lại bước 2.
    • Bước 4: Quay lại đỉnh V.

    Bài toán có năm thành phố với khoảng cách giữa các thành phố được tính bằng km. Sử dụng thuật toán láng giềng gần nhất, bắt đầu lần lượt từ mỗi đỉnh, tìm đường đi thích hợp cho người bán hàng, cửa hàng đặt tại A và cần đi qua tất cả thành phố còn lại.

    Bắt đầu với đỉnh A

    • Từ A, đỉnh gần nhất là C, chiều dài AC = 8
    • Từ C, đỉnh chưa viếng thăm gần nhất là E, CE = 4
    • Từ E, đỉnh chưa viếng thăm gần nhất là B, EB = 15
    • Từ B, đỉnh chưa viếng thăm gần nhất là D, BD = 10
    • Không còn đỉnh chưa viếng thăm, vì vậy quay về A, DA = 14

    Tổng chi phí ACEBDA là 8 + 4 + 15 + 10 + 14 = 51

    Lặp lại bắt đầu với những đỉnh khác:

    Đỉnh bắt đầu

    Đường đi

    Tổng chiều dài

    A

    ACEBDA

    51

    B

    BACEDB

    50

    C

    CEABDC

    45

    D

    DCEABD

    45

    E

    ECABDE

    50

    E

    ECDBAE

    45

    Có ba đường đi có chiều dài 45 km là giống nhau. Một nhân viên bán hàng có cửa hàng tại A, đường đi tốt nhất tìm ra bởi thuật toán láng giềng gần nhất là ABDCEA = 45 km

    Công thức

    Công thức: Bước đầu tiên để giải quyết trường hợp của TSPs lớn phải để tìm một công thức toán học tốt của vấn đề. Trong trường hợp của các vấn đề nhân viên bán hàng đi du lịch, các cấu trúc toán học là một đồ thị, ở mỗi thành phố được biểu thị bằng một điểm (hoặc nút) và dòng được rút ra kết nối hai nút (gọi là vòng cung hoặc cạnh). Liên kết với mỗi dòng là một khoảng cách (hoặc chi phí). Khi nhân viên bán hàng có thể nhận được từ mỗi thành phố để mọi thành phố khác trực tiếp, sau đó đồ thị được cho là hoàn chỉnh. Một chuyến đi vòng quanh những thành phố tương ứng với một số tập hợp con của các dòng, và được gọi là một tour du lịch hoặc một chu trình Hamilton (Đường đi Hamilton) trong lý thuyết đồ thị. Chiều dài của một tour du lịch là tổng độ dài của các đường trong chuyến đi vòng quanh.

    Tùy thuộc vào có hay không sự chỉ đạo, trong đó một cạnh của đồ thị là đi qua các vấn đề, ​​một trong những phân biệt đối xứng từ đối xứng đi vấn đề nhân viên bán hàng. Xây dựng các bất đối xứng TSP trên m thành phố, một trong những giới thiệu không-một biến

    và do thực tế là tất cả các nút của đồ thị phải có đúng một cạnh chỉ tay về phía nó và một trong những chỉ đi từ nó, có được một vấn đề chuyển nhượng cổ điển. Những khó khăn này một mình là không đủ vì công thức này sẽ cho phép “subtours”, có nghĩa là, nó sẽ cho phép các vòng phân chia xảy ra. Vì lý do này, một mô hình thích hợp của các vấn đề đi du lịch nhân viên bán hàng không đối xứng phải loại bỏ những subtours từ xem xét việc bổ sung “subtour loại bỏ” hạn chế. Vấn đề sau đó trở thành

    nơi mà K là bất kỳ tập hợp con thích hợp khác rỗng trong những thành phố 1,…, m. Chi phí c ij được phép khác với chi phí c ji. Lưu ý rằng có m (m-1) không-một biến trong công thức này.

    Xây dựng các đối xứng đi vấn đề nhân viên bán hàng, người ta ghi nhận rằng hướng đi qua là không đáng kể, do đó c ij = c ji. Từ hướng không quan trọng bây giờ, người ta có thể xem xét các đồ thị, nơi chỉ có một vòng cung (vô hướng) giữa hai nút. Vì vậy, chúng tôi cho x j e { 0,1 } là biến quyết định nơi j chạy qua tất cả các cạnh E của đồ thị vô hướng và c j là chi phí đi cạnh đó. Để tìm một tour du lịch trong biểu đồ này, người ta phải chọn một tập hợp con của các cạnh như vậy mà tất cả các nút được chứa trong hai chính xác của các cạnh được lựa chọn. Như vậy, vấn đề có thể được xây dựng như một vấn đề 2 khớp trong đồ thị G v có m (m-1) / 2 không-một biến, tức là một nửa số lượng các công tác xây dựng trước đó. Như trong trường hợp bất đối xứng, subtours phải được loại bỏ thông qua hạn chế loại bỏ subtour. Vấn đề do đó có thể được xây dựng như:

    Các thuật toán

    Để biết về sự gần gũi của các ràng buộc trên với giá trị tối ưu, người ta cũng phải biết một thấp hơn ràng buộc về giá trị tối ưu. Nếu trên và giới hạn dưới trùng, một bằng chứng của tối ưu là đạt được. Nếu không, một ước tính bảo thủ của sai số tương đối thực sự của các ràng buộc trên được cung cấp bởi sự khác biệt của phần trên và phần dưới bị ràng buộc chia cho ràng buộc thấp hơn. Do đó, cần cả trên và kỹ thuật ranh giới thấp hơn để tìm thể chứng minh giải pháp tối ưu cho các vấn đề tổ hợp khó khăn hoặc thậm chí để có được các giải pháp đáp ứng một sự đảm bảo chất lượng.

    Vì vậy, làm thế nào để có được và cải thiện thấp hơn ràng buộc? Một thư giãn của một vấn đề tối ưu hóa là một vấn đề tối ưu hóa mà bộ các giải pháp khả thi đúng có chứa tất cả các giải pháp khả thi của vấn đề ban đầu và có giá trị hàm mục tiêu nhỏ hơn hoặc bằng với đúng giá trị hàm mục tiêu cho các điểm khả thi cho vấn đề ban đầu. Do đó chúng tôi thay thế các “true” vấn đề bằng một với một khu vực có tính khả thi hơn đó là khả năng giải quyết dễ dàng hơn. Thư giãn này được tiếp tục tinh chế để thắt chặt các khu vực có tính khả thi để nó đại diện cho chặt chẽ hơn vấn đề thực sự. Các kỹ thuật tiêu chuẩn để đạt được giới hạn thấp hơn trên các vấn đề TSP là sử dụng một thư giãn mà là dễ dàng hơn để giải quyết hơn vấn đề ban đầu. Những nới lỏng có thể có một trong hai bộ khả thi rời rạc hay liên tục. Một số nới lỏng đã được xem xét cho TSP. Trong số đó là thư giãn n-đường dẫn, thư giãn chuyển nhượng, thư giãn 2 phù hợp, thư giãn 1-cây, và các chương trình thư giãn tuyến tính. Để tạo ra một cách ngẫu nhiên TSPs không đối xứng, vấn đề có đến 7500 thành phố đã được giải quyết bằng cách sử dụng thư giãn khoán, trong đó cho biết thêm subtours trong một khuôn khổ chi nhánh và ràng buộc và trong đó sử dụng một phỏng đoán ranh giới trên dựa trên subtour vá, (Miller và Pekny, 1991) và nó nhằm mục đích để giải quyết vấn đề nhân viên bán hàng đi du lịch, trong đó mục đích là để tìm ngắn chuyến đi vòng quanh để liên kết một loạt các thành phố. Các thuật toán chung là tương đối đơn giản và dựa trên một tập hợp các kiến, mỗi người làm của vòng các chuyến đi có thể cùng các thành phố. Ở mỗi giai đoạn, các kiến lựa chọn để di chuyển từ một thành phố khác theo một số quy tắc:

    1. Nó phải đến mỗi thành phố đúng một lần.

    2. Một thành phố xa xôi có ít cơ hội được lựa chọn (khả năng hiển thị.

    3. Cường độ cao hơn đường mòn pheromone đặt ra trên một cạnh giữa hai thành phố, lớn hơn xác suất mà cạnh đó sẽ được chọn.

    4. Đã hoàn thành cuộc hành trình của nó, là kiến ​​gia gửi pheromone hơn trên tất cả các cạnh nó đi qua, nếu cuộc hành trình ngắn.

    5. Sau mỗi lần lặp, những con đường mòn các kích thích tố bay hơi.

    Độ phức tạp tính toán

    Phiên bản quyết định của bài toán người bán hàng là NP-đầy đủ. Ngay cả khi khoảng cách giữa các thành phố là khoảng cách Euclide, bài toán vẫn là NP-khó.

    – Với n thành phố thì có: 1/2 × (n − 1)! đường đi.

    Độ phức tạp của tính xấp xỉ

    Trong trường hợp tổng quát, bài toán người bán hàng là NPO-đầy đủ. Khi các khoảng cách thỏa mãn bất đẳng thức tam giác và đối xứng, bài toán là APX-đầy đủ và thuật toán Christofides có thể tìm lời giải xấp xỉ không quá 1,5 lần lời giải tối ưu.

    Các trường hợp đặc biệt

    Cải thiện ngẫu nhiên

    Tối ưu hóa chuỗi Markov thuật toán sử dụng để phát tìm kiếm địa phương phụ các thuật toán có thể tìm thấy một con đường rất gần với các tuyến đường tối ưu cho 700 đến 800 thành phố.

    TSP là một chuẩn mực cho nhiều chẩn đoán chung đưa ra để tối ưu hóa tổ hợp như các thuật toán di truyền, tìm kiếm Tabu, kiến thuộc địa tối ưu hóa và các phương pháp entropy chéo.

    Không gian Euclide

    Ghi chú

    Liên kết ngoài

    Template:Thể loại Commons

    Tiếng Anh:

    Thể loại:Lý thuyết đồ thị

    Thể loại:Vận trù học

    Thể loại:Bài toán NP-đủ

    Thể loại:Giải thuật lý thuyết đồ thị

    Thể loại:Lý thuyết đồ thị trong các bài toán tính toán

    --- Bài cũ hơn ---

  • Chuyên Trang Của Báo Kinh Tế & Đô Thị
  • Văn Hóa Du Lịch Việt Nam – Đa Dạng Màu Sắc Văn Hóa
  • Tổng Quan Ngành Du Lịch Việt Nam – Tiềm Năng Phát Triển Nhks
  • / Khoa Học Tự Nhiên / Địa Lý
  • Tour Du Lịch Camping Là Gì? Các Điểm Thích Hợp Cắm Trại Tại Đà Nẵng
  • Bạn đang đọc nội dung bài viết Bài Toán Người Bán Hàng – Là Gì Wiki trên website Tuvanduhocsing.com. Hy vọng một phần nào đó những thông tin mà chúng tôi đã cung cấp là rất hữu ích với bạn. Nếu nội dung bài viết hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất. Chúc bạn một ngày tốt lành!

  • Web hay
  • Links hay
  • Push
  • Chủ đề top 10
  • Chủ đề top 20
  • Chủ đề top 30
  • Chủ đề top 40
  • Chủ đề top 50
  • Chủ đề top 60
  • Chủ đề top 70
  • Chủ đề top 80
  • Chủ đề top 90
  • Chủ đề top 100
  • Bài viết top 10
  • Bài viết top 20
  • Bài viết top 30
  • Bài viết top 40
  • Bài viết top 50
  • Bài viết top 60
  • Bài viết top 70
  • Bài viết top 80
  • Bài viết top 90
  • Bài viết top 100