Sắp xếp danh sách các số có chi phí sửa đổi

Question

Đầu tiên, đây là một trong bốn vấn đề chúng tôi phải giải quyết trong một dự án vào năm ngoái và tôi không thể tìm được thuật toán phù hợp để xử lý trong giải pháp bạo lực.

Sự cố: Các số nằm trong danh sách không được sắp xếp và chỉ hỗ trợ một loại hoạt động. Hoạt động được xác định như sau:

Cho vị trí i và vị trí j thao tác di chuyển số ở vị trí i đến vị trí j mà không thay đổi thứ tự tương đối của các số khác. Nếu i> j, vị trí của các số giữa các vị trí j và i - 1 tăng thêm 1, nếu không, nếu i < j vị trí của các số giữa các vị trí i + 1 và j giảm đi 1. Thao tác này yêu cầu tôi thực hiện các bước để tìm số để di chuyển và các bước j để xác định vị trí mà bạn muốn di chuyển nó. Sau đó, số bước cần thiết để di chuyển một số vị trí i đến vị trí j là i + j.

Chúng tôi cần thiết kế một thuật toán đưa ra một danh sách các số, xác định chuỗi di chuyển tối ưu (về chi phí) để sắp xếp lại chuỗi.

Nỗ lực: Một phần của cuộc điều tra của chúng tôi là khoảng NP-đầy đủ, chúng tôi làm cho nó là một vấn đề quyết định và cố gắng tìm một sự thay đổi phù hợp với bất kỳ trong những vấn đề được liệt kê trong Garey và Johnson của cuốn sách: Máy vi tính và không thể trị được không có kết quả . Cũng không có tài liệu tham khảo trực tiếp (từ quan điểm của chúng tôi) về loại biến thể này trong cuốn sách của Donald E. Knuth: Nghệ thuật lập trình máy tính Vol. 3 Sắp xếp và Tìm kiếm. Chúng tôi cũng đã phân tích các thuật toán để sắp xếp các danh sách được liên kết nhưng không có thuật toán nào trong số chúng đưa ra một ý tưởng hay để tìm ra chuỗi chuyển động tối ưu. Lưu ý rằng ý tưởng không phải là tìm thuật toán sắp xếp thứ tự, mà là để cho tôi biết chuỗi chuyển động tối ưu về chi phí tổ chức trình tự, bạn có thể tạo bản sao và sắp xếp để phân tích vị trí của các phần tử nếu bạn muốn, trên thực tế chúng ta có thể giả định rằng danh sách chứa các số từ 1 đến n, vì vậy chúng tôi biết nơi chúng tôi muốn đặt từng số, chúng tôi chỉ quan tâm đến việc giảm thiểu tổng chi phí của các bước.

Chúng tôi đã thử nghiệm một số cách tiếp cận tham lam nhưng tất cả đều thất bại, phân chia và chinh phục các thuật toán sắp xếp không thể sử dụng được vì chúng trao đổi không có phần chi phí trong danh sách và phương pháp lập trình động của chúng tôi phải xem xét nhiều trường hợp.

Thuật toán đệ quy vũ phu có tất cả các kết hợp có thể của các chuyển động từ i đến j và sau đó một lần nữa tất cả các khoảnh khắc có thể của phần còn lại của phần tử, cuối cùng nó trả về chuỗi với tổng chi phí thấp hơn sắp xếp danh sách, như bạn có thể tưởng tượng chi phí của thuật toán này là tàn bạo và làm cho nó không thể thực hiện được hơn 8 phần tử.

quan sát của chúng tôi:

• n phong trào không nhất thiết phải là rẻ hơn so với n + 1 phong trào (không giống như giao dịch hoán đổi trong mảng đó là O (1)). Về cơ bản có hai cách di chuyển một phần tử từ vị trí i sang j: một là di chuyển nó trực tiếp và phần còn lại là di chuyển các phần tử khác xung quanh i theo cách nó đạt đến vị trí j.

• Tối đa, bạn thực hiện các chuyển động n-1 (phần tử không ảnh hưởng chỉ đến vị trí của nó).

• Nếu đó là chuỗi chuyển động tối ưu thì bạn không di chuyển cùng một phần tử hai lần.

Answer 1

Vấn đề này trông giống như một ứng cử viên tốt cho số approximation algorithm nhưng điều đó sẽ chỉ cung cấp cho chúng tôi câu trả lời đủ tốt. Vì bạn muốn câu trả lời tối ưu, đây là những gì tôi muốn làm để cải thiện phương pháp tiếp cận vũ phu.

Thay vì mù quáng thử mọi hoán vị, tôi sẽ sử dụng phương pháp backtracking để duy trì giải pháp tốt nhất được tìm thấy và cắt tỉa bất kỳ chi nhánh nào vượt quá chi phí giải pháp tốt nhất của chúng tôi. Tôi cũng sẽ thêm một transposition table để tránh làm lại các tìm kiếm trên các tiểu bang mà các nhánh trước đó đã đạt được bằng cách sử dụng các hoán vị chuyển động khác nhau.

Tôi cũng sẽ thêm một vài chẩn đoán để khám phá các di chuyển có nhiều khả năng đạt được kết quả tốt hơn trước bất kỳ động thái nào khác. Ví dụ: trước tiên, hãy ưu tiên các di chuyển có chi phí nhỏ. Tôi cần phải thử nghiệm trước khi tôi có thể cho biết heuristics sẽ làm việc tốt nhất nếu có.

Tôi cũng sẽ cố gắng tìm số longest increasing subsequence of numbers trong mảng ban đầu. Điều này sẽ cung cấp cho chúng tôi một chuỗi các số không cần phải di chuyển, điều này sẽ làm giảm đáng kể số lượng chi nhánh mà chúng tôi cần khám phá. Điều này cũng giúp tăng tốc các tìm kiếm trên danh sách gần như được sắp xếp.

Tôi mong đợi những cải tiến này để có thể xử lý các danh sách lớn hơn 8 nhưng khi xử lý các danh sách số ngẫu nhiên lớn, tôi thích một thuật toán xấp xỉ.

---

Nhu cầu phổ biến (1 người), đây là những gì tôi muốn làm để giải quyết điều này với một genetic algorithm (meta-heuristique Tôi quen thuộc nhất với).

Trước tiên, tôi bắt đầu bằng cách tính toán chuỗi số tăng dần dài nhất (xem ở trên). Mỗi mục không phải là một phần của bộ đó phải được di chuyển. Tất cả những gì chúng ta cần biết bây giờ là theo thứ tự nào.

Bộ gen được sử dụng làm đầu vào cho thuật toán di truyền, đơn giản là một mảng trong đó mỗi phần tử đại diện cho một mục cần di chuyển. Thứ tự các mục hiển thị trong mảng đại diện cho thứ tự mà chúng phải được di chuyển. Chức năng thể dục sẽ là tính toán chi phí được mô tả trong câu hỏi gốc.

Hiện tại, chúng tôi có tất cả các yếu tố cần thiết để kết nối vấn đề trong thuật toán di truyền chuẩn. Phần còn lại chỉ là tinh chỉnh. Rất nhiều và rất nhiều tinh chỉnh.