कवरेज को अधिकतम करने के लिए एल्गोरिदम, आइटम उपयोग को कम करें?

Question

मुझे एक परिदृश्य मिला है जिसे आप इस तरह से कल्पना कर सकते हैं:

एक छवि के साथ शुरू करें जो 100 पिक्सेल चौड़े 1000 पिक्सेल लंबा है। उस छवि के अतिरिक्त, आपके पास उस छवि के फसल वाले अनुभागों का एक सेट है। प्रत्येक खंड 100 पिक्सल लंबा 100 पिक्सेल लंबा है। खंड में निहित छवि का हिस्सा भिन्न होता है। उदाहरण के लिए, आपके पास एक ऐसा हो सकता है जो बहुत ऊपर (पिक्सेल 0) से शुरू होता है, फिर एक लंबवत पिक्सेल 3 पर, फिर एक लंबवत पिक्सेल 9 पर और इसी तरह से।

मुझे क्या करना है, मुझे छोटी तस्वीरों के सेट को देखने का एक तरीका ढूंढना है और उन अनुभागों की सबसे छोटी संख्या चुनना है जो मुझे मूल छवि का सबसे अधिक कवरेज प्रदान करेंगे।

कुछ नोट:

1. छवि की सामग्री वास्तव में कोई फर्क नहीं पड़ता। यह वास्तव में महत्वपूर्ण निर्देशांक से मेल खाता है।
2. पुनर्निर्मित होने पर छवि में अंतराल कभी नहीं होगा, लेकिन वहां नीचे पहुंचने के लिए पर्याप्त टुकड़े नहीं हो सकते हैं।
3. अनुभागों के बीच बहुत अधिक ओवरलैप होगा। वास्तव में, ऐसे मामले होंगे जहां दो वर्गों के बीच केवल एक पिक्सेल या दो (लंबवत) अंतर होगा।

क्या कोई मुझे सही दिशा में इंगित कर सकता है? मैं इस प्रकार की क्रूर बल कर सकता हूं ... लेकिन मुझे लगता है कि एक बेहतर तरीका है।

Answer 1

मुझे खेद है, लेकिन मैं यह देखने में असफल रहा कि यह समस्या एनपी-हार्ड क्यों है।

सामान्य विचार है कि आप "सर्वश्रेष्ठ" अनुभाग का चयन करके अपनी छवि के iteratively नीचे भागों से हटा देंगे है, वह यह है कि

• सबसे बड़ी अनुभाग कि छवि
• यदि आप के तल को शामिल किया गया एक खोजने में विफल (क्योंकि कोई भी अनुभाग पिक्सल की अंतिम पंक्ति को कवर नहीं करता है) बस नीचे के सबसे नज़दीक को ले जाएं।
• रिंस और दोहराने

वर्गों छँटाई के द्वारा शुरू करो। आपको कुछ ऐसा मिलेगा (0,1,3,10, ..., 988,999) जहां 0 शीर्ष पिक्सेल पर शुरू होने वाले अनुभाग से मेल खाता है। (और 99 9 के अनुरूप एक केवल एक पंक्ति को कवर करता है)

मान लीजिए कि आपकी मूल छवि 100xN है। प्रारंभ में, एन = 1000।

एन छवि की अनुक्रमणिका बनें जो मूल छवि के अंत को सबसे अच्छी तरह से कवर करती है: i.e n उस सूची में सबसे छोटी संख्या है जैसे कि एन + 100> = एन। यदि ऐसी कोई संख्या नहीं है, तो एन बस सबसे बड़ी संख्या है।

अपने क्रमबद्ध सूची है (0,1, ... 899, 900, 901, .., 999) के बाद n = 900

यदि आपका क्रमबद्ध सूची है (0,1, ... 899 , 905, 910, .., 999) तो एन = 905

यदि आपका क्रमबद्ध सूची है (0,1, ..., 888,898,) तो एन = 898

फिर एन के साथ = n शुरू (आपने मूल छवि के निचले हिस्से को हटा दिया है) (बेशक, क्रमबद्ध सूची से हटाएं "> = n")

मुझे लगता है कि निश्चित-ऊंचाई अनुभाग (100 पाई xels) एनपी कठोरता को हटा देता है।

Answer 2

मुझे लगता है कि यह http://en.wikipedia.org/wiki/Maximum_coverage_problem है - सेट के तत्व पिक्सेल हैं (आप कोड लिख सकते हैं जैसे कि यह चीजों को पिक्सेल-बाय-पिक्सेल से निपटता नहीं है)।

क्योंकि यह 100x1000 है, समस्या अब एनपी-हार्ड नहीं है, शायद पी में भी। एक लालची दृष्टिकोण काम नहीं करेगा, लेकिन एक गतिशील प्रोग्रामिंग समाधान निम्नानुसार है, जो लगभग O(N) समय में पर्याप्त रूप से फैलता है, अन्यथा O(N * max_overlap_#)। यह चाल "आगे और पीछे की ओर" जाना है।

input: 
    [      ] to fill 
    [ (] ) { ([}) ] ([) ] 
return: 
    Result set of squares which maximize cover, secondarily 
    minimizing the size of the Result set if covered areas are equal 

the score of the leftmost element is {area:100^2, num:1} 
for each square S in order, left->right: 
    (Assuming you pick S in Result...) 
    let Candidates = {all squares which overlap S and are left of S} 
        + {first non-overlapping square left of S} 
    for each candidate C: 
     let score(S) = score(C) + {area:new_area_covered_by_S, num:1} 
     pick candidate BestC which maximizes score(S) 
     draw a line between S and BestC 

Take the square with the best score, and work your way backwards 
along the chain of best-picks, returning only those squares. 

यह आपको एक अतिरिक्त वर्ग भी एक अतिरिक्त 0.0001% कवरेज के लिए, उदाहरण के लिए "हर बिंदु पर, अगर यह एक वर्ग के साथ कवर करने के लिए संभव है, यह एक वर्ग के साथ कवर किया जाना चाहिए" जोड़ देगा मान लिया गया है। उचित रूप से व्यापार करने के लिए आप इस एल्गोरिदम को संशोधित कर सकते हैं।

यह आगे मानता है कि यह लगभग ऐसा नहीं है कि लगभग सभी वर्ग एक-दूसरे बिंदु पर एक दूसरे को ओवरलैप कर रहे हैं (वे कुछ हद तक फैल गए हैं लेकिन फिर भी ओवरलैप हो सकते हैं); अन्यथा इसमें काफी समय लग सकता है।

यह भी ध्यान दें कि जब भी आपके पास एक वर्ग द्वारा निष्कासित ब्रेक होता है तो आप समस्या को उपप्रोबल में विभाजित कर सकते हैं।

Answer 3

यह सटीक समस्या algorithmist द्वारा कवर की गई है।

एक लालची sweep line शैली एल्गोरिदम एल्गोरिदम आपकी समस्या को बेहतर तरीके से हल करेगा।

मान लीजिए कि आप पहले जितना संभव हो उतना गैर-विवादित क्षेत्र को कवर करना चाहते हैं, और दूसरी बार पहली बाधा को देखते हुए सबसे कम संख्या वाले अनुभागों का उपयोग करना चाहते हैं, तो यह एल्गोरिदम ओ (एन^2) समय में आपके लिए समस्या का समाधान करेगा।

मूल विचार शीर्ष से नीचे तक क्रम में जाना है, और जब आप 'नग्न' होते हैं तो केवल एक अनुभाग लेते हैं, यानी, दिए गए खंड को शामिल नहीं किया गया है। जब आपको एक सेक्शन लेने के लिए मजबूर किया जाता है, तो वह व्यक्ति लें जो आपको सबसे अधिक 'भविष्य' में शामिल करेगा। यह कार्यान्वयन ओ (एन^2) है, लेकिन आप इसे बेहतर तरीके से प्रबंधित करके ओ (एन लॉग (एन)) बना सकते हैं।

#!/usr/bin/python 

START_EVENT, END_EVENT = 0, 1 # handle starts before ends at same point 

def max_future(cands): 
    return max(cands, key=lambda c: (c[1], c)[1]) 

def cover_max_segment_min(intervals): 
    events = [] 
    for interval in intervals: 
    events.append((interval[0], START_EVENT, interval)) 
    events.append((interval[1], END_EVENT, interval)) 
    cands = [] 
    outputs = [] 
    alive = None 
    # Handle events by 
    # event time, 
    # starts before ends, 
    # longer endings before shorter endings 
    events.sort(key=lambda x: (x[0], x[1], -x[2][1])) 
    for k, event_type, interval in events: 
    if event_type == START_EVENT: 
     cands.append(interval) 
    if event_type == END_EVENT: 
     cands.remove(interval) 
     if interval is alive: 
      alive = None 
    if not alive and cands: 
     outputs.append(max_future(cands)) 
     alive = outputs[-1] 
    return outputs 

assert cover_max_segment_min([(0, 3), (1, 4), (3, 5)]) == \ 
    [(0, 3), (3, 5)] 
assert cover_max_segment_min([(0, 3), (3, 5), (1, 4)]) == \ 
    [(0, 3), (3, 5)] 
assert cover_max_segment_min([(0, 3)]) == [(0, 3)] 
assert cover_max_segment_min([]) == [] 
assert cover_max_segment_min([(-10, 10), (1, 2), (3, 5)]) == [(-10, 10)] 
assert cover_max_segment_min([(1, 2), (2, 3), (3, 4)]) == \ 
    [(1, 2), (2, 3), (3, 4)] 
assert cover_max_segment_min([(1, 4), (1, 2), (3, 3)]) == \ 
    [(1, 4)]