गैर-ओवरलैपिंग खरीद का इष्टतम अनुक्रम

Question

मुझे लगता है कि यह एक शेड्यूलिंग समस्या है, लेकिन मुझे इस पर भी यकीन नहीं है! मैं जो चाहता हूं वह गैर-ओवरलैपिंग खरीद निर्णयों के इष्टतम अनुक्रम को ढूंढना है, जब मुझे उनके मूल्य का पूरा ज्ञान हो और भविष्य में कौन से अवसर आ रहे हैं।

कल्पना करें कि एक थोक व्यापारी जो विभिन्न वस्तुओं को बेचता है जिन्हें मैं अपनी दुकान के लिए खरीदना चाहता हूं। किसी भी समय उनके पास कई विशेष ऑफ़र चल सकते हैं; मैं पूरी कीमत पर बेचूंगा, इसलिए उनकी छूट मेरा लाभ है।

मैं लाभ को अधिकतम करना चाहता हूं, लेकिन पकड़ यह है कि मैं एक समय में केवल एक ही चीज़ खरीद सकता हूं, और क्रेडिट जैसी कोई चीज़ नहीं, और बदतर, डिलीवरी देरी होती है। अच्छी खबर यह है कि जैसे ही उन्हें वितरित किया जाता है, मैं वस्तुओं को बेच दूंगा, और फिर मैं अपना पैसा फिर से खर्च कर सकता हूं। तो, सभी विकल्पों के माध्यम से एक रास्ता हो सकता है: मैं सोमवार को 100 किलो सेब खरीदता हूं, उन्हें मंगलवार को वितरित किया जाता है। मैं फिर रविवार को 20 नन वेशभूषा, उचित रूप से पर्याप्त, खरीदता हूं। मैं कुछ दिनों तक छोड़ देता हूं, जैसा कि मुझे पता है कि बुधवार को उन्हें भारी छूट पर फेरारी मिलेगी। इसलिए मैं उनमें से एक खरीदता हूं, इसे निम्नलिखित मंगलवार को दिया जाता है। और इसी तरह।

आप लाभदायक लाभ पर विचार कर सकते हैं या नहीं। एल्गोरिदम आज के विशेष प्रस्तावों में से किसी एक को चुनने, या एक दिन का इंतजार करने के बीच प्रत्येक चरण में एक निर्णय के लिए आता है क्योंकि कल कुछ बेहतर आ रहा है।

चलिए अमूर्त है कि थोड़ा सा। खरीदें और डिलीवरी दिन-बाद-युग बन जाते हैं। लाभ खरीद मूल्य द्वारा विभाजित बिक्री मूल्य के रूप में लिखा जाता है। अर्थात। 1.00 का मतलब तोड़ना भी है, 1.10 का मतलब 10% लाभ है, 2.0 का मतलब है कि मैंने अपना पैसा दोगुना कर दिया।

buy delivery profit 
    1  2  1.10 Apples 
    1  3  1.15 Viagra 
    2  3  1.15 Notebooks 
    3  7  1.30 Nun costumes 
    4  7  1.28 Priest costumes 
    6  7  1.09 Oranges 
    6  8  1.11 Pears 
    7  9  1.16 Yellow shoes 
    8  10  1.15 Red shoes 
    10  15  1.50 Red Ferrari 
    11  15  1.40 Yellow Ferrari 
    13  16  1.25 Organic grapes 
    14  19  1.30 Organic wine 

नोट: अवसरों खरीद दिन पर केवल मौजूद हैं (यदि कोई उन्हें खरीदता है जैसे कार्बनिक अंगूर शराब में बनाया हो!), और मैं प्रसव के रूप में एक ही दिन में बेचने के लिए मिलता है, लेकिन मेरी नहीं खरीद सकते हैं अगले दिन तक अगले आइटम। इसलिए मैं अपने नन वेशभूषा टी = 7 पर नहीं बेच सकता और तुरंत टी = 7 पर पीले जूते खरीद सकता हूं।

मुझे उम्मीद थी कि वहां एक ज्ञात सर्वश्रेष्ठ एल्गोरिदम मौजूद है, और इसके लिए पहले से ही एक आर मॉड्यूल है, लेकिन एल्गोरिदम या अकादमिक साहित्य भी अच्छा होगा, जैसा कि किसी भी अन्य भाषा में कुछ भी होगा। गति मायने रखती है, लेकिन मुख्य रूप से जब डेटा बड़ा हो जाता है, तो मैं जानना चाहता हूं कि यह ओ (एन) है, या जो भी हो।

वैसे, क्या अधिकतम संभव वितरण विलंब होने पर सबसे अच्छा एल्गोरिदम बदलता है? जैसे

buy,delivery,profit,item 
1,2,1.10,Apples 
1,3,1.15,Viagra 
2,3,1.15,Notebooks 
3,7,1.30,Nun costumes 
4,7,1.28,Priest costumes 
6,7,1.09,Oranges 
6,8,1.11,Pears 
7,9,1.16,Yellow shoes 
8,10,1.15,Red shoes 
10,15,1.50,Red Ferrari 
11,15,1.40,Yellow Ferrari 
13,16,1.25,Organic grapes 
14,19,1.30,Organic wine 

या JSON के रूप में:

{"headers":["buy","delivery","profit","item"],"data":[[1,2,1.1,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.3,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.5,"Red Ferrari"],[11,15,1.4,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.3,"Organic wine"]]} 

या एक अनुसंधान डेटा फ्रेम के रूप में:

structure(list(buy = c(1L, 1L, 2L, 3L, 4L, 6L, 6L, 7L, 8L, 10L, 
11L, 13L, 14L), delivery = c(2L, 3L, 3L, 7L, 7L, 7L, 8L, 9L, 
10L, 15L, 15L, 16L, 19L), profit = c(1.1, 1.15, 1.15, 1.3, 1.28, 
1.09, 1.11, 1.16, 1.15, 1.5, 1.4, 1.25, 1.3), item = c("Apples", 
"Viagra", "Notebooks", "Nun costumes", "Priest costumes", "Oranges", 
"Pears", "Yellow shoes", "Red shoes", "Red Ferrari", "Yellow Ferrari", 
"Organic grapes", "Organic wine")), .Names = c("buy", "delivery", 
"profit", "item"), row.names = c(NA, -13L), class = "data.frame") 

लिंक

अगर delivery - buy <= 7

यहाँ सीएसवी के रूप में उपरोक्त डेटा है

Are there any R Packages for Graphs (shortest path, etc.)? (igraph एक shortest.paths समारोह प्रदान करता है और सी पुस्तकालय के अलावा, एक R package और एक अजगर इंटरफ़ेस है)

Answer 1

इस समस्या के बारे में सोचने का सबसे आसान तरीका shortest-path problem के समान है (हालांकि इसे maximum flow problem के रूप में व्यवहार करना संभवतः तकनीकी रूप से बेहतर है)। दिन संख्या, 1 ... 1 9, नोड नाम के रूप में इस्तेमाल किया जा सकता है; प्रत्येक नोड जे नोड के लिए एक लिंक है j + 1 सूची में वजन 1, और प्रत्येक उत्पाद (बी, डी, जी, पी) के साथ ख को दिन d + 1 दिन से एक लिंक जोड़ता है वजन जी के साथ। जैसे-जैसे हम पथ-खोज करते समय नोड्स के माध्यम से प्रगति करते हैं, हम प्रत्येक नोड पर अब तक देखे गए सर्वोत्तम गुणा मूल्यों का ट्रैक रखते हैं।

नीचे दिखाया गया पायथन कोड ओ (वी + ई) में चलाता है जहां वी शिखर (या दिन) की संख्या है, और ई किनारों की संख्या है। इस कार्यान्वयन में, ई = वी + उत्पादों की संख्या बेची जा रही है। जोड़ा गया नोट: लूप i, t in enumerate (graf): प्रत्येक चरम पर एक बार व्यवहार करता है। उस लूप में, ई किनारों में ई के लिए: वर्तमान वर्टेक्स से प्रत्येक बार किनारों का इलाज करता है। इस प्रकार, किसी किनारे को एक से अधिक बार इलाज नहीं किया जाता है, इसलिए प्रदर्शन ओ (वी + ई) है।

संपादित नोट 2: क्रजंपानी ने दावा किया कि ओ (वी + ई) ओ (एन लॉग एन) से धीमा है, जहां एन उत्पादों की संख्या है। हालांकि, दो आदेश तुलनीय नहीं हैं जब तक कि हम विचार किए गए दिनों की संख्या के बारे में धारणा नहीं करते। ध्यान दें कि यदि डिलीवरी देरी बाध्य होती है और उत्पाद की तारीख ओवरलैप होती है, तो दिनों की संख्या ओ (एन) कहां से है (वी + ई) = ओ (एन), जो ओ (एन लॉग एन) से तेज है।

हालांकि, धारणाओं के एक निर्धारित सेट के तहत मेरी विधि और क्रजंपानी के रन टाइम ऑर्डर समान हो सकते हैं: बड़ी संख्या में दिनों के लिए, x के क्रमबद्ध संघ में दिनों के लिए ग्राफ नोड्स बनाने के लिए मेरी विधि बदलें ] और एक्स [1] मान, और i-1 और i + 1 के बजाय दिन [i-1] और दिन [i + 1] के लिंक का उपयोग कर। दिनों की छोटी संख्या के लिए, ओ (एन) गिनती प्रकार का उपयोग करने के लिए क्रजंपानी की विधि बदलें।

कार्यक्रम के उत्पादन की तरह लग रहा है:

16 : 2.36992 [11, 15, 1.4, 'Yellow Ferrari'] 
11 : 1.6928 [8, 10, 1.15, 'Red shoes'] 
8 : 1.472 [4, 7, 1.28, 'Priest costumes'] 
4 : 1.15 [1, 3, 1.15, 'Viagra'] 

जो इंगित करता है कि हम, २.३६९९२ की गोटा लाभ के साथ 16 दिन पर पहुंचे बेचने के बाद पीले फेरारी के 15 दिन पर; रेड जूते बेचने के बाद 1.6 9 28 के मुनाफे के साथ 11 वें दिन पहुंचे; इत्यादि। नोट, उत्पादों की सूची की शुरुआत में डमी प्रविष्टि, और संख्याओं के चारों ओर उद्धरण हटाने, जेएसओएन डेटा बनाम मुख्य मतभेद हैं। सूची तत्व graf[j] में प्रविष्टि [1, j-1, 0, [[j+1,1,0]]] के रूप में शुरू होती है, जो कि है [सर्वोत्तम मूल्य-दूर-दूर, सर्वोत्तम-से-नोड #, सर्वोत्तम-उत्पाद-कुंजी, एज-सूची]। प्रत्येक एज-लिस्ट सूचियों की एक सूची है जिसमें फॉर्म [अगली-नोड #, एज-वेट, उत्पाद-कुंजी] है। उत्पाद 0 होने के कारण एक डमी उत्पाद प्रारंभिकीकरण को सरल बनाता है।

products = [[0,0,0,""],[1,2,1.10,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.30,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.50,"Red Ferrari"],[11,15,1.40,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.30,"Organic wine"]] 
hiDay = max([x[1] for x in products]) 
graf = [[1, i-1, 0, [[i+1,1,0]]] for i in range(2+hiDay)] 

for i, x in enumerate(products): 
    b, d, g, p = x[:] 
    graf[b][3] += [[d+1, g, i]] # Add an edge for each product 

for i, t in enumerate(graf): 
    if i > hiDay: break 
    valu = t[0]     # Best value of path to current node 
    edges = t[3]    # List of edges out of current node 
    for e in edges: 
     link, gain, prod = e[:] 
     v = valu * gain; 
     if v > graf[link][0]: 
      graf[link][0:3] = [v, i, prod] 

day = hiDay 
while day > 0: 
    if graf[day][2] > 0: 
     print day, ":\t", graf[day][0], products[graf[day][2]] 
    day = graf[day][1] 

Answer 2

यह एक गतिशील प्रोग्रामिंग समस्या है। समग्र इष्टतम विकल्प बनाने के लिए केवल प्रत्येक चरण में इष्टतम विकल्प बनाना आवश्यक है। आप एक सारणी बना सकते हैं जो पिछले राज्य के आधार पर प्रत्येक चरण में इष्टतम विकल्प का वर्णन करती है और उस राज्य से विभिन्न कदम उठाने का लाभ।आप संभावित रूप से गैर-इष्टतम होने वाली संभावनाओं को दूर कर एक छोटे से सेट में संभावित संभावनाओं का एक बड़ा सेट पतन कर सकते हैं।

आपकी समस्या में, केवल एक ही स्थिति जो विकल्पों को प्रभावित करती है वह वितरण तिथि है। उदाहरण के लिए, पहले दिन, आपके पास तीन विकल्प हैं: आप सेब खरीद सकते हैं, अपना लाभ 1.10 पर सेट कर सकते हैं, और अपनी डिलीवरी तिथि 2 तक सेट कर सकते हैं; वियाग्रा खरीदें, अपना लाभ 1.15 पर सेट करें, और अपनी डिलीवरी तिथि 3 पर सेट करें; या 2. के लिए कुछ भी खरीद सकते हैं, शून्य करने के लिए अपने लाभ निर्धारित करते हैं, और सेट अपने डिलीवरी की तारीख हम इस तरह इन विकल्पों का प्रतिनिधित्व कर सकते हैं:

(choices=[apples], delivery=2, profit=1.10) or 
(choices=[viagra], delivery=3, profit=1.15) or 
(choices=[wait], delivery=2, profit=0.00) 

यह है कि क्या आप वियाग्रा खरीदने के कोई फर्क या पर कुछ भी नहीं खरीदने के लिए नहीं जा रहा है भविष्य के फैसले बनाने के पहले दिन। किसी भी तरह से, अगले दिन आप खरीद कर सकते हैं दिन दो है, इसलिए लाभ कम होने के बाद आप एक विकल्प के रूप में प्रतीक्षा को समाप्त कर सकते हैं। हालांकि, अगर आप सेब खरीदते हैं, तो भविष्य में फैसले को अलग-अलग प्रभावित करेंगे अगर आप वियाग्रा खरीदते हैं या इंतजार करते हैं, तो यह एक अलग विकल्प है जिसे आपको विचार करना है। यह आपको पहले दिन के अंत में इन विकल्पों के साथ छोड़ देता है।

(choices=[apples], delivery=2, profit=1.10) or 
(choices=[viagra], delivery=3, profit=1.15) 

दो दिन के लिए, आपको अपने विकल्पों पर विचार करना होगा कि विकल्प किस दिन थे।

(choices=[apples,notebooks], delivery=3, profit=2.25) or 
(choices=[apples,wait],  delivery=3, profit=1.10) or 
(choices=[viagra,wait],  delivery=3, profit=1.15) 

इन विकल्पों के सभी तीन आप एक ही राज्य में जहाँ तक भविष्य के निर्णयों पर विचार कर रहे हैं, क्योंकि वे सभी 3 पर डिलीवरी की तारीख डाल दिया, रख सकते हैं ताकि आप बस अधिकतम लाभ के साथ एक चुनें: यह तीन possibilties का उत्पादन :

(choices=[apples,notebooks], delivery=3, profit=2.25) 

तीन दिन के लिए पर जा रहे हैं, तो आप दो विकल्प

(choices=[apples,notebooks,wait],   delivery=4, profit=2.25) 
(choices=[apples,notebooks,nun costumes], delivery=7, profit=3.55) 

इन विकल्पों के दोनों

रखा जाना है है, क्योंकि वे में भविष्य के निर्णयों को प्रभावित करेगा विभिन्न तरीके।

ध्यान दें कि हम केवल वितरण तिथि और लाभ के आधार पर भविष्य के निर्णय ले रहे हैं। हम विकल्पों का ट्रैक रखते हैं ताकि हम अंत में विकल्पों के सर्वोत्तम सेट की रिपोर्ट कर सकें।

अब शायद आप पैटर्न देख सकते हैं। आपके पास विकल्पों का एक सेट है, और जब भी आपके पास एक ही डिलीवरी तिथि होती है, तो आप केवल अधिकतम लाभ वाले व्यक्ति को चुनते हैं और दूसरों को खत्म करते हैं। आपके विकल्पों को ध्वस्त करने की यह प्रक्रिया समस्या को तेजी से बढ़ने से रोकती है, जिससे इसे कुशलतापूर्वक हल किया जा सकता है।

Answer 3

आप इसे linear programming समस्या के रूप में हल कर सकते हैं। रसद समस्याओं को हल करने के लिए यह मानक दृष्टिकोण है, जैसे कि एयरलाइंस और निगमों द्वारा सामना किए जाने वाले लोगों के साथ, आपकी तुलना में बहुत बड़ी समस्याएं हैं। मैं औपचारिक रूप से यहां आपकी समस्या को परिभाषित नहीं करूंगा, लेकिन व्यापक रूप से: आपका उद्देश्य कार्य लाभ का अधिकतमकरण है। आप खरीद दिनों का प्रतिनिधित्व कर सकते हैं, और रैखिक बाधाओं के रूप में "प्रति दिन केवल एक खरीद" का प्रतिनिधित्व कर सकते हैं।

मानक रैखिक प्रोग्रामिंग एल्गोरिदम simplex method है। यद्यपि इसका घातीय मामला व्यवहार है, व्यावहारिक रूप से, यह वास्तविक समस्याओं पर बहुत ही कुशल है। बहुत अच्छे स्वतंत्र रूप से उपलब्ध कार्यान्वयन हैं। मेरा पसंदीदा GNU Linear Programming Kit है। आर an interface to GLPK है। Lp_solve एक अन्य प्रसिद्ध परियोजना है, जिसमें R interface भी है। प्रत्येक मामले में मूल दृष्टिकोण औपचारिक रूप से आपकी समस्या को परिभाषित करना है, फिर तीसरे पक्ष के सॉल्वर को अपनी बात करने के लिए हाथ दें।

और जानने के लिए, मैं आपको Algorithm Design Manual पर एक नज़र डालने की सलाह देता हूं, जो आपको ऑनलाइन शोध करने के लिए पर्याप्त पृष्ठभूमि देनी चाहिए। पी।412 आगे रैखिक प्रोग्रामिंग और इसकी विविधता का एक संपूर्ण सारांश है (उदाहरण के लिए पूर्णांक प्रोग्रामिंग यदि आपके पास अभिन्नता बाधाएं हैं)।

यदि आपने पहले कभी रैखिक प्रोग्रामिंग के बारे में नहीं सुना है, तो आप कुछ उदाहरणों को देख सकते हैं कि इसका उपयोग कैसे किया जा सकता है। मुझे पाइथन में यह simple set of tutorial problems पसंद है। उनमें बिल्ली के भोजन के टिन पर अधिकतम लाभ, और सुडोकू समस्या को हल करना शामिल है।

Answer 4

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

समस्या को निम्न प्रकार O(n log n) में हल किया जा सकता है। अंतराल को अपने अंतिम बिंदुओं से क्रमबद्ध करें (आकृति देखें)। हम क्रमबद्ध सूची में प्रत्येक अंतराल i के माध्यम से यात्रा करते हैं और क्रमबद्ध सूची में 1...i से अंतराल वाले उपप्रवाह के लिए इष्टतम समाधान की गणना करते हैं।

1. The optimal solution of the problem for intervals `1...(i-1)` in the 
    sorted list or 

2. Weight of interval `i` + the optimal solution of the problem for intervals 
    `1...j`, where j is the last interval in the sorted list whose end-point 
    is less than the start-point of `i`. 

ध्यान दें कि यह एल्गोरिथ्म O(n log n) में चलता है और क्रमबद्ध सूची के हर उपसर्ग के लिए इष्टतम समाधान के मूल्य की गणना करता है: अंतराल 1...i के लिए समस्या का इष्टतम समाधान का अधिकतम है। हम इस एल्गोरिदम को चलाने के बाद, हम क्रमबद्ध क्रम में क्रमबद्ध सूची के माध्यम से यात्रा कर सकते हैं और प्रत्येक उपसर्ग के लिए गणना मूल्यों के आधार पर इष्टतम समाधान में मौजूद अंतराल पा सकते हैं।

संपादित करें:

इस सही ढंग से अंतराल के वजन काम करने के लिए इसी वस्तुओं के वास्तविक लाभ होना चाहिए के लिए (जैसे sell_price होना चाहिए - buy_price)।

अद्यतन 2: चल रहा है समय

Let दिनों की संख्या (jwpat7 के संकेतन के बाद) हो V। यदि VO(n log n) से बहुत छोटा है, तो हम O(n + V) समय में अंतराल को सॉर्ट करने के लिए गिनती सॉर्ट का उपयोग कर सकते हैं और subproblems के समाधान रिकॉर्ड करने के लिए V आकार की सरणी का उपयोग कर सकते हैं। इस दृष्टिकोण के परिणामस्वरूप की जटिलता होती है। तो एल्गोरिदम का चलने का समय min(O(V+n), O(n log n)) है।