Tôi đang làm việc trên một công cụ gọi là Quickfort cho trò chơi Dwarf Fortress. Quickfort biến các bảng tính thành định dạng csv/xls thành một loạt lệnh cho Dwarf Fortress để thực hiện để vẽ một "bản thiết kế" trong trò chơi.Tìm tập hợp các hình chữ nhật tiếp giáp lớn nhất để che phủ nhiều khu vực
Tôi hiện đang cố gắng giải quyết tối ưu vấn đề về âm mưu khu vực cho bản phát hành 2.0 của công cụ này.
Hãy xem xét "kế hoạch chi tiết" sau đây xác định các lệnh vẽ sơ đồ cho lưới 2 chiều. Mỗi ô trong lưới nên được đào ra ("d"), được chuyển kênh ("c") hoặc bị bỏ sót ("."). Bất kỳ số lượng các lệnh vẽ âm mưu khác nhau có thể có mặt trong việc sử dụng thực tế.
. d . d c c
d d d d c c
. d d d . c
d d d d d c
. d . d d c
Để giảm thiểu số lượng hướng dẫn mà cần phải được gửi đến Fortress Dwarf, tôi muốn tìm các thiết lập của hình chữ nhật tiếp giáp lớn nhất có thể được thành lập để bù đắp hoàn toàn, hoặc "âm mưu", tất cả các plottable ô. Để hợp lệ, tất cả các ô của hình chữ nhật đã cho phải chứa cùng một lệnh.
Đây là cách tiếp cận nhanh hơn Quickfort 1.0: vẽ từng ô riêng lẻ dưới dạng hình chữ nhật 1x1. This video cho thấy sự khác biệt hiệu suất giữa hai phiên bản.
Đối với các kế hoạch chi tiết ở trên, giải pháp trông như thế này:
. 9 . 0 3 2
8 1 1 1 3 2
. 1 1 1 . 2
7 1 1 1 4 2
. 6 . 5 4 2
Mỗi hình chữ nhật cùng đánh số trên biểu thị một hình chữ nhật liền kề. Các hình chữ nhật lớn nhất được ưu tiên hơn các hình chữ nhật nhỏ hơn cũng có thể được hình thành trong khu vực của chúng. Thứ tự của số/hình chữ nhật là không quan trọng.
My current approach là lặp lại. Trong mỗi lần lặp lại, tôi xây dựng một danh sách các hình chữ nhật lớn nhất có thể được hình thành từ mỗi ô có thể vẽ bằng lưới bằng cách mở rộng trong tất cả 4 hướng từ ô. Sau khi sắp xếp danh sách lớn nhất trước tiên, tôi bắt đầu với hình chữ nhật lớn nhất được tìm thấy, đánh dấu các ô bên dưới của nó là "được vẽ" và ghi lại hình chữ nhật trong danh sách. Trước khi vẽ từng hình chữ nhật, các ô bên dưới của nó được kiểm tra để đảm bảo chúng chưa được vẽ (chồng lên một ô trước đó). Sau đó chúng tôi bắt đầu lại, tìm các hình chữ nhật còn lại lớn nhất có thể được hình thành và vẽ chúng cho đến khi tất cả các ô được vẽ như một phần của một số hình chữ nhật.
Tôi xem xét phương pháp này được tối ưu hóa hơn một chút so với tìm kiếm bạo lực câm, nhưng tôi lãng phí rất nhiều chu kỳ (lại) tính toán hình chữ nhật lớn nhất của ô và kiểm tra trạng thái của ô bên dưới.
Hiện tại, thói quen khám phá hình chữ nhật này chiếm tỷ trọng của tổng thời gian chạy của công cụ, đặc biệt là đối với các bản thiết kế lớn. Tôi đã hy sinh một số độ chính xác vì lợi ích của tốc độ bằng cách chỉ xem xét hình chữ nhật từ các tế bào xuất hiện để tạo thành một góc hình chữ nhật (được xác định bằng cách sử dụng một số chẩn đoán tế bào lân cận không phải lúc nào cũng chính xác). Do 'tối ưu hóa' này, mã hiện tại của tôi không thực sự tạo ra giải pháp trên một cách chính xác, nhưng nó đủ gần.
Nói chung, tôi xem xét mục tiêu của hình chữ nhật lớn nhất đầu tiên là phương pháp "đủ tốt" cho ứng dụng này.Tuy nhiên tôi nhận thấy rằng nếu mục tiêu là thay vì để tìm tối thiểu (số ít nhất) của hình chữ nhật hoàn toàn bao gồm nhiều lĩnh vực, giải pháp sẽ trông như thế thay vì điều này:
. 3 . 5 6 8
1 3 4 5 6 8
. 3 4 5 . 8
2 3 4 5 7 8
. 3 . 5 7 8
mục tiêu thứ hai này thực sự đại diện cho một hơn giải pháp tối ưu cho vấn đề, vì ít hình chữ nhật hơn thường có nghĩa là ít lệnh được gửi tới Dwarf Fortress hơn. Tuy nhiên, cách tiếp cận này đánh tôi gần hơn với NP-Hard, dựa trên kiến thức toán học hạn chế của tôi.
Xem the video nếu bạn muốn hiểu rõ hơn về chiến lược tổng thể; Tôi đã không giải quyết các khía cạnh khác của quá trình của Quickfort, chẳng hạn như tìm đường dẫn con trỏ ngắn nhất vẽ tất cả các hình chữ nhật. Có thể có một giải pháp cho vấn đề này kết hợp chặt chẽ các chiến lược này.
Trợ giúp của bất kỳ biểu mẫu nào sẽ được đánh giá cao.
Bạn đã thử một thuật toán di truyền chưa? Nghe có vẻ thích hợp cho vấn đề này. – marcog