Rate this post

Giả sử một nhân viên bán hàng muốn đến thăm một số thành phố nhất định được giao cho anh ta. Anh ta biết khoảng cách của cuộc hành trình giữa mọi cặp thành phố. Vấn đề 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ố chính xá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 tìm một đoạn mạch Hamilton có độ dài nhỏ nhất. Nếu chúng ta biểu diễn các thành phố bằng các đỉnh và đường nối hai cạnh của các thành phố, chúng ta sẽ có được một đồ thị có trọng số trong đó, với mỗi cạnh ei một số wi (trọng số) được liên kết.

Các bài viết liên quan:

Một cách giải thích vật lý của phần tóm tắt trên là: coi đồ thị G như một bản đồ gồm n thành phố trong đó w (i, j) là khoảng cách giữa các thành phố i và j. Một nhân viên bán hàng muốn có chuyến tham quan các thành phố bắt đầu và kết thúc tại cùng một thành phố bao gồm việc đến thăm từng thành phố còn lại một lần và chỉ một lần.

Trong đồ thị, nếu chúng ta có n đỉnh (thành phố), thì có (n-1)! Các cạnh (tuyến đường) và tổng số mạch Hamilton trong một complete graph gồm n đỉnh sẽ là Bài toán Người bán hàng làm du lịch.

Phương pháp Nearest Neighbour

Thủ tục này mang lại kết quả hợp lý tốt cho vấn đề nhân viên bán hàng đi du lịch. Phương pháp như sau:

Bước 1: Chọn một đỉnh tùy ý và tìm đỉnh gần với đỉnh bắt đầu nhất để tạo thành đường đi ban đầu của một cạnh.

Bước 2: Gọi v là đỉnh mới nhất được thêm vào đường dẫn. Bây giờ, trong số kết quả của các đỉnh không nằm trong đường dẫn, hãy chọn đỉnh gần nhất với v và thêm đường dẫn, đường nối cạnh v và đỉnh này. Lặp lại bước này cho đến khi tất cả các đỉnh của đồ thị G được đưa vào đường dẫn.

Bước 3: Nối đỉnh bắt đầu và đỉnh cuối cùng bằng một cạnh và tạo thành mạch.

Ví dụ: Sử dụng phương pháp hàng xóm gần nhất để giải bài toán TSP sau đây, cho đồ thị được hiển thị trong hình bắt đầu từ đỉnh v1.

Giải pháp: Chúng ta phải bắt đầu với đỉnh v1. Bằng cách sử dụng phương pháp lân cận gần nhất, việc xây dựng đỉnh bằng đỉnh của chuyến tham quan hoặc mạch Hamilton được thể hiện trong hình:

Tổng khoảng cách của tuyến đường này là 18.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now