07/05/2024
Trước giờ chắc mọi người vẫn đang thắc mắc tranh mình vẽ thế nào đúng không. Dễ lắm để ad chỉ cho :D
🎨 Thuật toán TSP (Traveling Salesman Problem) là một bài toán tối ưu hóa tổ hợp trong lĩnh vực khoa học máy tính và toán học. Bài toán đặt ra câu hỏi: "Nếu một người bán hàng cần đi qua một số thành phố để bán hàng và trở về thành phố xuất phát, thì phải đi qua các thành phố theo thứ tự nào để quãng đường di chuyển là ngắn nhất?"
🎨 Cụ thể, trong bài toán TSP, ta có một tập hợp các điểm (thành phố) và khoảng cách giữa mỗi cặp điểm. Mục tiêu là tìm ra một chuỗi con của các điểm sao cho mỗi điểm chỉ được đi qua một lần, bắt đầu và kết thúc tại cùng một điểm, và tổng khoảng cách di chuyển là nhỏ nhất có thể.
🎨 Thuật toán TSP có thể được giải quyết bằng nhiều cách, bao gồm các phương pháp cơ bản như duyệt mọi trường hợp, phương pháp nhánh cận, hoặc các phương pháp tối ưu hóa như lập kế hoạch động hoặc thuật toán di truyền.
🎨 Mặc dù bài toán TSP không dễ giải quyết do tồn tại số lượng kết hợp lớn, nhưng nó lại có nhiều ứng dụng thực tế, bao gồm lập lịch sản xuất, định tuyến hệ thống giao thông, quản lý tài nguyên và nhiều lĩnh vực khác.
🎨 Trong ngữ cảnh vẽ tranh, bạn có thể sử dụng TSP để tạo ra các đường cong hoặc mô hình trong tranh, tùy thuộc vào cách bạn ánh xạ điểm và cạnh của đồ thị.
Tham khảo:
- https://www2.oberlin.edu/math/faculty/bosch/tspart-page.html
- https://drububu.com/illustration/tsp/index.html