Giả sử một nhân viên bán sản phẩm muốn mang lại thăm một số thành phố khăng khăng được giao cho anh ta. Anh ta biết khoảng cách của cuộc hành trình giữa rất nhiều cặp thành phố. Sự việc của anh ta là chọn một con đường bắt đầu từ thành phố quê hương của anh ta, đi qua mỗi thành phố đúng mực một lần và trở về thành phố quê hương của anh ta một khoảng cách ngắn nhất có thể. Bài toán này liên quan mật thiết đến việc đào bới tìm kiếm một đoạn mạch Hamilton bao gồm độ dài bé dại nhất. Nếu bọn họ biểu diễn các thành phố bằng các đỉnh và con đường nối nhị cạnh của các thành phố, chúng ta sẽ đã có được một đồ thị gồm trọng số vào đó, với mỗi cạnh ei một trong những wi (trọng số) được liên kết.
Bạn đang xem: Bài toán người bán hàng
Một cách phân tích và lý giải vật lý của phần bắt tắt trên là: coi thiết bị thị G như một bản đồ tất cả n thành phố trong các số ấy w (i, j) là khoảng cách giữa những thành phố i cùng j. Một nhân viên bán hàng muốn tất cả chuyến tham quan những thành phố bước đầu và kết thúc tại và một thành phố bao hàm việc mang đến thăm từng thành phố sót lại một lần và có một lần.
Trong đồ vật thị, nếu chúng ta có n đỉnh (thành phố), thì gồm (n-1)! những cạnh (tuyến đường) với tổng số mạch Hamilton vào một complete graph gồm n đỉnh đã là vấn đề Người bán hàng làm du lịch.
Cách giải Travelling Salesman Problem
Traveling Salesman Problem (TSP) là trong số những bài toán danh tiếng trong nghành nghề tối ưu hóa tài chính và thứ tính. Việc yêu mong tìm một đường đi qua mỗi điểm vào một tập đúng theo các vị trí du lịch (hay những thành phố) một lần độc nhất vô nhị và kết thúc tại điểm xuất phát làm sao cho tổng ngân sách chi tiêu của lối đi là nhỏ nhất.
Hiện nay vẫn không có cách thức nào để xử lý bài toán TSP một cách trọn vẹn tối ưu vào thời gian đồng ý được. Tuy nhiên, những thuật toán heuristics cùng metaheuristics rất có thể được sử dụng để tìm phương án gần đúng.
Các cách thức giải quyết việc TSP bao gồm:
Brute Force: tính toán tất cả những hoán vị của những điểm và chọn hoán vị về tối ưu. Tuy nhiên, phương thức này không thực tiễn cho những bài toán bự vì con số hoán vị là hết sức lớn.Nearest Neighbor: bước đầu từ một điểm bất kỳ, search điểm gần nhất và dịch chuyển đến nó, tiếp đến tìm điểm sớm nhất với điểm đang đứng với tiếp tục cho đến khi toàn bộ các điểm được lép thăm. Phương thức này dễ triển khai và hay được sử dụng cho các bài toán nhỏ.Christofides Algorithm: phối hợp giữa Nearest Neighbor và Minimum Spanning Tree nhằm tìm một lời giải gần đúng với xác suất gần 3/2 đối với giải về tối ưu. Cách thức này được sử dụng cho những bài toán lớn.Simulated Annealing: Một phương thức metaheuristics, nó tạo thành một lời giải bắt đầu ngẫu nhiên cùng sau đó cố gắng tìm một lời giải xuất sắc hơn bằng phương pháp di chuyển hẳn qua các lời giải khác theo một quy trình tựa như như quá trình làm mát trong hàn.Genetic Algorithm: Một thuật toán tối ưu hóa được lấy xúc cảm từ các quy trình tiến hóa vào tự nhiên. Thuật toán này áp dụng một quần thể các giải mã và thực hiện các phép lai ghép, tự dưng biến nhằm tìm ra lời giải giỏi hơn.Phương pháp Nearest Neighbour
Thủ tục này mang lại hiệu quả hợp lý xuất sắc cho vụ việc nhân viên bán sản phẩm đi du lịch. Phương thức như sau:
Bước 1: chọn 1 đỉnh tùy ý với tìm đỉnh ngay gần với đỉnh ban đầu nhất để sinh sản thành mặt đường đi lúc đầu của một cạnh.
Bước 2: call v là đỉnh mới nhất được phân phối đường dẫn. Bây giờ, vào số kết quả của các đỉnh không bên trong đường dẫn, hãy chọn đỉnh gần nhất với v và thêm mặt đường dẫn, con đường nối cạnh v cùng đỉnh này. Lặp lại bước này cho đến khi toàn bộ các đỉnh của đồ gia dụng thị G được chuyển vào con đường dẫn.
Bước 3: Nối đỉnh bước đầu và đỉnh cuối cùng bằng một cạnh và tạo ra thành mạch.
Ví dụ: Sử dụng cách thức hàng xóm sớm nhất để giải vấn đề TSP sau đây, cho đồ thị được hiển thị vào hình bắt đầu từ đỉnh v1.
Các thuật toán xử lý bài toán
Có nhiều phương pháp tiếp cận để giải bài toán người bán sản phẩm tuy nhiên bao gồm hai giải mã phổ biến dùng để giải việc này là giải mã di truyền và giải thuật lũ kiến (Ant Colony).
Xem thêm: Cấu hình poco x3 pro nfc 8gb, cấu hình xiaomi poco x3 pro nfc 2021
2.2.1 lời giải di truyềnlời giải di truyền thường dùng làm giải cho các lớp bài toán và giải mã này cũng có thể dùng nhằm giải cho việc người chào bán hàng, tuy nhiên khi sử dụng giải thuật này và tiến hành trên laptop thì thời hạn chạy chương trình khá lâu vì chưng việc màn biểu diễn nhiễm nhan sắc thể mang đến n tp mà người bán sản phẩm đi qua là khá nặng nề khăn, vì chưng ta bao gồm n thành phố, nếu cần sử dụng chuỗi nhị phân để trình diễn nhiễm sắc đẹp thể mang đến n thành phố đó thì ta tốn là n*log2(n) bit với mỗi thành phố ta cần màn biểu diễn log2(n) bit. Từ bỏ đó không khí tìm kiếm rất lớn và phức hợp nên bắt buộc fan lập trình phải vận dụng thuật toán Greedy(thuật toán tham lam) những lần vày vậy công tác chạy hơi chậm.
2.2.2. Giải mã AntColony
việc người bán hàng hoàn toàn rất có thể giải bằng giải mã Ant
Colony, thuật toán này có thể áp dụng cho các lớp bài toán. Để có thể hiểu hơn về thuật toán này bạn có thể tìm hiểu quánh điểm chuyển động trong tự nhiên và thoải mái của bọn kiến cùng từ đó rất có thể hiểu rộng về thuật toán Ant
Colony.
Hình 1: Sơ đồ hoạt động của các con kiến
Quy luật dịch chuyển của bọn kiến trong tự nhiên là: con kiến là con vật có tổ chức triển khai cao, cho nên vì thế mỗi khi di chuyển chúng thường còn lại mùi riêng của nó để các con kiến trong lũ có thể nhấn diện ra lối dịch chuyển của chúng, mùi của kiến nhằm lại trên phố đi kia thì ta thường hotline là pheromone. Đây là yếu tố giúp lũ kiến ghi lại và trao đổi thông tin với nhau khi chúng đi tìm nguồn thức ăn. Khi tìm thấy nguồn thức ăn, mỗi nhỏ kiến sẽ dịch rời từ tổ cho tới nơi bao gồm nguồn thức ăn theo đường đi đã search thấy. Bởi vì từ tổ kiến đến nơi tất cả thức nạp năng lượng sẽ có nhiều đường đi. Bởi vì thế lúc đầu các chú kiến vẫn đi tình cờ theo những con đường từ điểm xuất xứ đến đích. Mặc dù trong quá trình dịch chuyển chúng đã trao đổi tin tức với nhau, với sau một thời hạn nhất định các chú kiến trong bọn sẽ tìm thấy và dịch rời theo tuyến phố ngắn tuyệt nhất từ tổ tới nguồn thức ăn. Sau khi quan cạnh bên và nghiên cứu hoạt động của bầy kiến trong tự nhiên, bọn họ nhận thấy rằng quá trình tìm đuờng đi ngắn tuyệt nhất từ tổ tới nguồn thức nạp năng lượng dựa trên những quy khí cụ sau:
· sử dụng phoremone để trao đổi tin tức với nhau trong quá trình dịch rời nhằm mục đích tìm kiếm được đường đi ngắn tốt nhất từ tổ đến nguồn thức ăn. Mỗi khi dịch rời chúng để lại một lượng tin tức mùi (phoremone) của chúng trên đường chúng đi qua.
· Khi triển khai tìm đường đi, những con loài kiến đi sau vẫn xác lý thuyết đi bởi các thông tin hương thơm (pheromone) đã làm được để lại trên đường đi bởi các con kiến dịch chuyển trước đó
. · các con loài kiến sẽ di chuyển một cách bỗng dưng khi không tồn tại mùi nhằm lại trên đường đi. Lượng mùi để lại cũng bi cất cánh hơi theo thời gian.
· những đường đi bao gồm lượng thông tin mùi (pheomone) còn lại càng các thì xác suất được những con kiến chọn càng cao. Ngược lại những đoạn đường gồm lượng thông tin mùi (pheromone) càng thấp thì phần trăm được lựa chọn càng thấp.
Từ vấn đề quan gần cạnh cơ chế chuyển động của bầy kiến trong thoải mái và tự nhiên mà thuật toán Ant
Colony sẽ ra đời.
Thuật toán Ant
Colony mô phỏng hoạt động của bọn kiến tự tạo như sau: Thuật toán thực hiện một lũ kiến tự tạo (Artificial Ants) để mô bỏng lại các vận động trong tự nhiên và thoải mái của lũ kiến. Cùng có một trong những điều chỉnh về mặt hoạt động so với bầy kiến từ bỏ nhiên nhằm mục tiêu tăng tính tác dụng của thuật toán. Trong lời giải này đa phần mô tả chuyển động tìm đường đi ngắn nhất của những con loài kiến nhân tạo dựa vào lượng mùi để lại trong quá trình dịch rời của lũ kiến. Cụ thể về hoạt động của bầy kiến nhân tạo được trình diễn như sau:
Cho một đồ vật thị rất đầy đủ gồm những đỉnh với cạnh trong số đó đỉnh là nơi kiến sẽ trải qua và những cạnh là những đoạn đường. Nút lúc đầu cho lối đi của mỗi nhỏ kiến được chọn 1 cách bất chợt và thông tin mùi (pheromone) được thống kê giám sát và để trên mỗi đoạn đường. Mỗi bé kiến sẽ chọn lối đi theo những nguyên tắc:
+ nhờ vào thông tin mùi hương để lại có trên các đoạn đường để tính tỷ lệ chọn đoạn đường tiếp sau và làm đường đi cho con kiến.
+ Đường đi có tương đối nhiều lượng mùi (pheromone) nhiều hơn thế thì sẽ được gán một xác suất lớn hơn. Ngược lại các đoạn lối đi có lượng thông tin mùi rẻ hơn đang có tỷ lệ được lựa chọn thấp hơn. Nhỏ kiến vẫn tìm con đường đi cho tới khi xong một đường đi của nó (thỏa mãn đk dừng của con kiến).
+ Một đường đi không hề thiếu và hoàn chỉnh được gọi là một trong lời giải chuẩn cho bài toán để ra. Các đường đi tìm được sẽ tiến hành phân tích, đối chiếu và reviews để search phương án tối ưu nhất có thể. Đó là lời giải tối ưu của bài bác toán.
+ sau khi con tất cả kiến trong bọn hoàn thành việc tìm đường đi của nó, ta đã tiến hành cập nhật thông tin mùi cho những cung. Con số của mùi sẽ được giám sát và đo lường và kiểm soát và điều chỉnh để tìm kiếm được phương án tối ưu xuất sắc hơn.
· Các giải mã có con đường đi ngắn lại hơn sẽ có cân nặng pheromone to hơn để để lên trên các cung đã có đi qua. Ngược lại, các lời giải cho đường đi dài thêm hơn nữa sẽ có cân nặng pheromone bé hơn.
· con kiến đã chọn đường đi có lượng mùi to hơn và tỷ lệ chọn con đường đi này cũng cao hơn. Quá trình này được lặp đi đi lặp lại cho tới khi hầu như các nhỏ kiến trong lũ kiến tự tạo chọn thuộc một mặt đường đi, và đây đó là lời giải của bài xích toán.
