Đóng gói tối đa các hình chữ nhật trong một vòng tròn

Question

Tôi làm việc tại một phòng thí nghiệm công nghệ nanô, nơi tôi thực hiện chế tạo silicon wafer. (Các wafer thấy cắt chỉ đường song song) Chúng tôi, tất nhiên, cố gắng để tối đa hóa sản lượng của cái chết chúng tôi cắt. Tất cả những cái chết sẽ có kích thước bằng nhau, hoặc là hình chữ nhật hoặc hình vuông, và cái chết đều được cắt từ một wafer tròn. Về cơ bản, tôi đang cố gắng để đóng gói hình chữ nhật tối đa thành một vòng tròn.

Tôi chỉ có một sự hiểu biết khá cơ bản về MATLAB và hiểu biết trung gian về phép tính. Có cách nào (tương đối) đơn giản để làm điều này, hay là tôi trên đầu của tôi?

Answer 1

Đóng gói hình chữ nhật tùy ý vào vòng tròn để đáp ứng mục tiêu hiệu quả không gian là tối ưu hóa không lồi (NP-Hard) nói chung. Điều này có nghĩa là sẽ không có giải pháp thanh lịch hoặc đơn giản nào sẽ giải quyết vấn đề này một cách tối ưu. Các phương pháp giải pháp tất cả sẽ phụ thuộc vào bất kỳ kiến ​​thức miền cụ thể nào mà bạn có thể sử dụng để cắt tỉa cây tìm kiếm hoặc phát triển các chẩn đoán. Nếu bạn không có kinh nghiệm trong loại vấn đề này, bạn nên tham khảo ý kiến ​​của một chuyên gia.

Answer 2

Go từ đây, và may mắn:

http://en.wikipedia.org/wiki/Knapsack_problem

và nhận được ở đây:

http://www-sop.inria.fr/mascotte/WorkshopScheduling/2Dpacking.pdf

Ít nhất bạn sẽ có một số ý tưởng những gì bạn đang giải quyết ở đây.

Answer 3

không giống với vấn đề của Gauss? Xem http://mathworld.wolfram.com/GausssCircleProblem.html

hay, đây có thể được xem như là một "vấn đề bao bì" http://en.wikipedia.org/wiki/Packing_problem#Squares_in_circle

Answer 4

tôi đã bị cuốn hút để đọc câu hỏi của bạn vì tôi đã làm một dự án về vấn đề này cho đào tạo của tôi như là một giáo viên Toán. Tôi cũng khá vui khi biết rằng nó được cho là một vấn đề NP, bởi vì dự án của tôi đã dẫn tôi đến cùng một kết luận.

Bằng cách sử dụng phép tính cơ bản, tôi đã tính toán vài 'thế hệ' đầu tiên của hình chữ nhật có kích thước tối đa, nhưng nó phức tạp khá nhanh.

Bạn có thể đọc dự án của tôi ở đây:

Beckett, R. Bưu kiện của Pi: Một vấn đề đường cong-đóng gói. Bath Spa MEC. 2009.

• Pages 1 - 15
• Pages 16 - 30

Tôi hy vọng rằng một số những phát hiện của tôi là hữu ích cho bạn hoặc ít nhất là thú vị. Tôi nghĩ rằng việc áp dụng ý tưởng này rất có thể sẽ là công nghệ nano máy tính.

Trân trọng.