Khám phá một thuật toán để tìm chuỗi tối thiểu chứa một số mặt hàng nhất định

Question

Rất tiếc, tôi không thể đưa ra tên của thuật toán hoặc sự cố cho thuật toán sau. Tôi sẽ tuyên bố vấn đề và sau đó những gì tôi đã cố gắng và có lẽ ai đó có thể chỉ cho tôi đi đúng hướng.

Hãy tưởng tượng bạn có một túi vật phẩm (không có thứ tự, các bản sao được phép). Trong thực tế túi có thể chứa 2-20 mặt hàng trong trường hợp thư giãn này giúp.

Mục đích là tìm chuỗi dài tối thiểu (danh sách liên kết được đặt hàng trong trường hợp chúng tôi có khái niệm khác nhau của một chuỗi) chứa tất cả các mục trong túi theo thứ tự bất kỳ.

Một chuỗi bao gồm mã thông báo bắt đầu (không có trong túi), sau đó là bất kỳ số lượng mục nào được theo sau bởi mã thông báo kết thúc (cũng không có trong túi).

Chuỗi được hình thành bằng cách ghép các n-tuples lại với nhau (thứ tự quan trọng) và như một sự thư giãn hơn nữa, chúng ta hãy nói giá trị n là như nhau đối với tất cả các bộ dữ liệu. Trong thực tế, tôi đang làm việc với n = 3. Chuỗi có thể được "trộn" trái ngược với nối nếu chúng có các phần tử chồng chéo. Ví dụ, hãy xem xét (a, b, c) và (c, d, e). Có thể được tham gia như (a, b, c, d, e). Tương tự như vậy, (a, b, c) và (b, c, d) có thể được nối với nhau (a, b, c, d). Một số bộ dữ liệu có thể có mã thông báo bắt đầu ở vị trí đầu tiên và một số mã thông báo có mã thông báo cuối ở vị trí cuối cùng, tất nhiên cho phép có giải pháp cho vấn đề.

Vì vậy, có vẻ như với tôi rằng giải pháp chính xác cho vấn đề không thể xử lý nói chung. Một số loại thuật toán tối ưu hóa sẽ là cần thiết để có được một giải pháp "tốt" cho vấn đề. Giải pháp "tốt" tôi có thể sống cùng.

Những gì tôi đã bắt đầu với là một cách tiếp cận tham lam khi vượt qua lần đầu tiên bạn tìm thấy tuple chứa số lượng phần tử nhất trong túi, tùy ý phá vỡ các mối quan hệ. Tạo một cấu trúc dữ liệu chứa chuỗi mà chúng tôi đã tạo cho đến nay và dán vào bộ dữ liệu được chọn vào cấu trúc dữ liệu này. Tách vấn đề thành 2 vấn đề con, bên mã thông báo bắt đầu và bên mã thông báo kết thúc. Cho đến khi mã thông báo đầu tiên của cấu trúc dữ liệu của subproblem 1 là một token bắt đầu và token cuối cùng của subproblem 2 là mã thông báo kết thúc, hãy phát triển chuỗi sao cho chúng tôi đang cố gắng tìm điều kiện dừng càng sớm càng tốt về vấn đề con) trong khi cũng cố gắng loại bỏ lượng chứa trong túi càng sớm càng tốt. Điều này có thể không tốt bởi vì mỗi tiểu dự án phải liên lạc với nhau về số lượng vật phẩm còn lại trong túi cần được bao gồm.

Bất kỳ ai nhìn thấy sự cố này ở bất kỳ đâu? Bất kỳ suy nghĩ như làm thế nào để cải thiện (hoặc nhận được để làm việc một cách chính xác) thuật toán này? Đây là một vấn đề thực sự tôi giải quyết mà là một phần thông minh của một hệ thống lớn hơn nhiều và không phải là một vấn đề đồ chơi hoặc một vấn đề bài tập về nhà.

EDIT

Xin lỗi tất cả những gì được ra khỏi máy tính ngày nay. Tôi sẽ cố gắng để gửi một giải pháp ví dụ mà không phải là quá tầm thường, nhưng không quá phức tạp để xem.

Given:

1. Bag = {A, B, C, D} (tôi làm cho nó một bộ vì lợi ích của ví dụ, nhưng mỗi mặt hàng có thể xuất hiện nhiều hơn một lần)
2. / = Start Token
3. \ = End Token

4. 3-Tuples (Bộ ba): Tôi gắn nhãn chúng ag cho sự đơn giản trong đặt tên. Các chữ thường không có chức năng thực sự trong vấn đề.

   (/,A, E) a 
   (/,C, D) b 
   (/,G, H) c 
   (D,B, A) d 
   (C,G, H) e 
   (B,A, \) f 
   (G,H, \) g 
   

Giải pháp: Nếu chúng ta chuỗi lại với nhau b, d và f chúng tôi nhận (/,C,D,B,A,\).
Đây là chuỗi ngắn nhất có thể chứa tất cả các phần tử trong túi có chiều dài 6 nếu bạn đếm cả mã thông báo bắt đầu và kết thúc. Nói chung, con đường ngắn nhất có thể có chiều dài | BAG | + 2, nếu thực tế tồn tại. Tôi hy vọng tuyên bố vấn đề của tôi có ý nghĩa hơn bây giờ.

Answer 1

Vì bạn chỉ có tối đa 20 mục, tôi nghĩ bạn có thể tính toán giải pháp chính xác trong một khoảng thời gian hợp lý (ví dụ: dưới một phút).

Một cách tiếp cận sẽ được sử dụng lập trình năng động, nơi nhà nước được cho bởi:???

A) a 20 bit number m (which will represent which items have been visited so far) 
B) a number b in the range 1..20 
C) a number c in the range 1..20 

Trạng thái này sẽ tương ứng với một chuỗi trông như Start,,,, ...,, b , c. tức là b và c là 2 phần tử gần đây nhất.

Số m là một trường bit thể hiện các yếu tố khác đã được truy cập trong chuỗi. Nói cách khác, bit i của m là 1 nếu và chỉ khi chuỗi bao gồm phần tử thứ i trong túi.

Các thuật toán để tìm ra chuỗi ngắn nhất sau đó sẽ là:

1. Hãy S = tập các trạng thái bao gồm tất cả các bộ mà có dấu hiệu bắt đầu. (Tất cả các trạng thái này sẽ có cùng chiều dài chuỗi là 2)
2. Đối với mỗi chiều dài chuỗi y từ 3 trở lên, hãy đi qua tất cả các trạng thái trong S và thử mở rộng trạng thái để có độ dài y bằng cách sử dụng bộ túp thích hợp. Nếu điều này là có thể, hãy thêm trạng thái mở rộng để đặt S.
3. Chỉ cho phép các bộ tuples có mã thông báo cuối được thêm vào nếu bit m sẽ kết thúc bằng tất cả các bit được đặt.

Nếu bạn quản lý thêm một bộ chứa trạng thái kết thúc thì bạn đã tìm thấy chuỗi ngắn nhất chứa tất cả các phần tử.

Đối với N mục trong túi, có khoảng 2^N.N.N các trạng thái nên chỉ là về quản lý được.