प्रोग्रामिंग पहेली: बोर्ड को कैसे पेंट करें?

Question

एक N x M बोर्ड है जिसे हमें पेंट करना चाहिए। हम या तो एक पूरी पंक्ति या एक पूरे कॉलम को एक साथ पेंट कर सकते हैं। सभी बोर्ड कोशिकाओं के रंगों के N x M मैट्रिक्स को देखते हुए बोर्ड को पेंट करने के लिए चित्रकला संचालन की न्यूनतम संख्या मिलती है।

उदाहरण के लिए: हम एक 3 x 3 बोर्ड पेंट चाहिए के रूप में (आर - लाल, बी - नीले, जी - हरा) इस प्रकार है:

बी, बी, बी
बी, आर, आर
बी , जी, जी

चित्रकला आपरेशन की न्यूनतम संख्या 4:

• पेंट पंक्ति 0 ब्लू
• पेंट पंक्ति 1 के साथ लाल
साथ
• पेंट पंक्ति 2 ब्लू

साथ ग्रीन

पेंट स्तंभ 0 के साथ आप इसे कैसे हल होगा?

Answer 1

स्टार्टर्स के लिए, आप को संपूर्ण खोज सूचित करने का प्रयास कर सकते हैं।

अपने राज्यों को ग्राफ होने दें: G=(V,E) जहां V = {all possible boards} और E = {(u,v) | you can move from board u to v within a single operation}।

• ध्यान दें कि यदि आप पहले से ग्राफ उत्पन्न करने के लिए की जरूरत नहीं है - एक successors(board) समारोह, कि दिए गए बोर्ड के सभी उत्तराधिकारियों लौटने का उपयोग कर आप मक्खी पर उत्पन्न कर सकते हैं,।

तुम भी h:V->R की आवश्यकता होगी - एक admissible heuristic function कि बोर्ड मूल्यांकन करता है।

अब, आप A*, या bi-directional बीएफएस खोज [या दोनों का संयोजन] चला सकते हैं, आपका स्रोत एक श्वेत बोर्ड होगा, और आपका लक्ष्य अनुरोधित बोर्ड है। चूंकि हम स्वीकार्य हेरिस्टिक फ़ंक्शन का उपयोग करते हैं - ए * complete दोनों (हमेशा मौजूद होने पर समाधान ढूंढता है) और optimal (सबसे छोटा समाधान पाता है), यह सबसे अच्छा समाधान मिलेगा। [वही द्वि-दिशात्मक बीएफएस के लिए जाता है]।

कमियां:

• हालांकि एल्गोरिथ्म सूचित किया जाता है, यह घातीय व्यवहार करना होगा। लेकिन यदि यह एक साक्षात्कार प्रश्न है, तो मेरा मानना ​​है कि एक गैर-कुशल समाधान बेहतर है तो कोई समाधान नहीं है।
• हालांकि पूर्ण और इष्टतम - यदि कोई समाधान नहीं है - एल्गोरिदम एक अनंत लूप में फंस सकता है, या बहुत कम लूप को कम से कम तब तक महसूस किया जा सकता है जब तक यह महसूस न हो कि यह सभी संभावनाओं को दूर कर चुका है।

(1) स्वीकार्य अनुमानी के लिए उदाहरण h(board) = #(miscolored_squares)/max{m,n}

Answer 2

यह एक मजेदार समस्या की तरह लग रहा है। मुझे कुछ छद्म कोड के साथ एक शॉट लेने दो।

Function MinPaints(Matrix) Returns Integer 
    If the matrix is empty return 0 
    Find all rows and columns which have a single color 
    If there are none, return infinity, since there is no solution 
    Set the current minimum to infinity 
    For each row or column with single color: 
     Remove the row/column from the matrix 
     Call MinPaints with the new matrix 
     If the result is less than the current minimum, set the current minimum to the result 
    End loop 
    Return the current minimum + 1 
End Function 

मुझे लगता है कि आपकी समस्या का समाधान होगा, लेकिन मैंने किसी भी अनुकूलन या कुछ भी कोशिश नहीं की। हालांकि यह पर्याप्त तेज़ नहीं हो सकता है, मुझे नहीं पता। मुझे संदेह है कि यह समस्या उप-घातीय समय में हल करने योग्य है।

BBB 
BRR 
BGG 
| 
+---BRR 
| BGG 
| | 
| +---RR 
| | GG 
| | | 
| | +---GG 
| | | | 
| | | +---[] 
| | | | | 
| | | | Solvable in 0 
| | | | 
| | | Solvable in 1 
| | | 
| | +---RR 
| | | | 
| | | +---[] 
| | | | | 
| | | | Solvable in 0 
| | | | 
| | | Solvable in 1 
| | | 
| | Solvable in 2 
| | 
| Solvable in 3 
|      BB 
+---Another branch with RR ... 
|      GG 
Solvable in 4