Xử lý đồ thị khổng lồ - Nhân viên bán hàng du lịch

Question

Tôi tự dạy cách lập trình các thuật toán liên quan đến TSP (Djikstra, Kruskal) và tôi đang tìm kiếm một số lời khuyên khởi động. Tôi đang làm việc với C# và SQL. Lý tưởng nhất tôi muốn để có thể làm điều này đúng trong SQL tuy nhiên tôi không chắc chắn nếu đó là có thể (Tôi giả sử thời gian chạy sẽ là khủng khiếp sau 50 đỉnh).

Vì vậy, tôi đoán câu hỏi là, tôi có thể làm điều này chỉ là SQL và nếu vậy cách tiếp cận tốt nhất là gì? Nếu không, và tôi phải có được C# liên quan đến những gì sẽ là cách tiếp cận tốt nhất ở đó?

Answer 1

Chỉ nên thực hiện các phép tính đơn giản trong SQL, như tính toán tổng. Số tiền nhanh hơn trong SQL, bởi vì chỉ tổng được trả về thay vì tất cả các bản ghi. Các thuật toán phức tạp giống như những thuật toán bạn có trong tâm trí phải được thực hiện trong mã C# của bạn! Thứ nhất, ngôn ngữ SQL không thích hợp cho các vấn đề như vậy, thứ hai nó được tối ưu hóa cho các truy cập db, làm cho nó rất chậm đối với các kiểu sử dụng khác.

Đọc dữ liệu của bạn từ db của bạn với SQL vào một cấu trúc dữ liệu thích hợp vào chương trình C# của bạn. Làm tất cả các logic liên quan đến TSP ở đó và, nếu bạn muốn, lưu trữ kết quả trong db, khi kết thúc.

Answer 2

Vâng, tôi không chắc liệu SQL có phải là tùy chọn tốt nhất để thực hiện việc này hay không, nhưng bạn có thể thử sử dụng ma trận kề cho đầu vào. Nhiều thuật toán được xuất bản được thiết kế cho loại đầu vào này và sau đó vấn đề duy nhất là đặt mã giả vào C#. Hãy xem điều này: http://en.wikipedia.org/wiki/Adjacency_matrix.

Bạn sẽ sử dụng mảng hai chiều để biểu diễn ma trận.

Answer 3

Tôi sẽ kêu gọi trong SQL. Mặc dù nó không thực sự là lựa chọn đầu tiên của tôi để làm việc trên TSP - nó vẫn có thể dễ dàng làm điều này - giả sử tất nhiên là mô hình dữ liệu là tối ưu cho những nỗ lực của bạn.

Công việc đầu tiên là xác định mô hình dữ liệu chứa thông tin mà thuật toán của bạn cần, sau đó điền một số dữ liệu mẫu, sau đó tìm ra truy vấn có thể truy xuất mảng khi cần.

cuối cùng bạn có thể quyết định xem một số SQL đơn giản trong truy vấn đó có phù hợp với bạn hay có thể là phần mở rộng dưới dạng thủ tục được lưu trữ.

cuối cùng, bạn có thể chọn để kéo nó ra ngôn ngữ lựa chọn thay thế của bạn.