आर्बिट्रेज ट्रेडिंग (बेलमैन-फोर्ड एल्गोरिथम)

एक्सचेंज पर ट्रेडिंग आमतौर पर जोखिमों से जुड़ी होती है। यह अधिकांश व्यापारिक रणनीतियों के लिए बिल्कुल सही है। इन मामलों में व्यापार की सफलता केवल जोखिमों का सही आकलन करने और उन्हें प्रबंधित करने की क्षमता से निर्धारित होती है। लेकिन सभी व्यापारिक रणनीतियाँ नहीं हैं। जोखिम-मुक्त रणनीतियां हैं, जिनमें शामिल हैं, विशेष रूप से, मध्यस्थता। यह आलेख बताएगा कि बेलमैन-फोर्ड एल्गोरिथम के रूप में इस तरह के शास्त्रीय ग्राफ़ एल्गोरिथ्म का उपयोग करके मध्यस्थता क्या है और इसे कैसे लागू किया जाए।

मध्यस्थता क्या है?

मध्यस्थता कुछ तार्किक रूप से संबंधित लेनदेन है जिसका उद्देश्य विभिन्न बाजारों (एक स्थानिक मध्यस्थता) में एक ही समय में एक ही या संबंधित परिसंपत्तियों के लिए कीमतों में अंतर से लाभ होता है, या एक ही बाजार में अलग-अलग समय पर (अस्थायी मध्यस्थता) ।

एक सरल उदाहरण के रूप में, स्थानिक मध्यस्थता पर विचार करें। न्यूयॉर्क और लंदन में, डॉलर के लिए यूरो और यूरो के लिए डॉलर खरीदने के लिए सौदे किए जा सकते हैं। न्यूयॉर्क में, यह 3 यूरो के लिए 4 डॉलर की दर से किया जा सकता है, और लंदन में - 3 यूरो के लिए 5 डॉलर की दर से। दरों में यह अंतर स्थानिक मध्यस्थता की संभावना को खोलता है।



4 डॉलर के साथ, न्यूयॉर्क में आप 3 यूरो खरीद सकते हैं। उसके बाद, लंदन में, इन 3 यूरो 5 डॉलर में खरीदें। जैसा कि आप देख सकते हैं, लेनदेन का ऐसा सरल अनुक्रम निवेशित प्रत्येक 4 डॉलर के लिए 1 डॉलर का लाभ लाता है। तदनुसार, अगर शुरू में $ 4 मिलियन है, तो लाभ पहले से ही एक मिलियन में होगा।

जब एक ही मुद्रा जोड़ी के लिए विनिमय दर (हम प्रसार का विचार नहीं करते हैं) भिन्न होते हैं, तो मध्यस्थता की रणनीति को लागू करने के लिए आवश्यक लेनदेन का क्रम बहुत सरल है। यदि एक मुद्रा जोड़ी के लिए विनिमय दर निश्चित है, लेकिन कई मुद्रा जोड़े समानांतर में कारोबार करते हैं, तो मध्यस्थता भी संभव है, लेकिन लेनदेन का क्रम पहले से ही निर्विवाद होगा। उदाहरण के लिए, आप 5 यूरो में 4 यूरो, 4 पाउंड के लिए 3 पाउंड और फिर 3 पाउंड के लिए 6 डॉलर खरीद सकते हैं। निवेश के हर 5 डॉलर के लिए इस तरह के लेनदेन से लाभ $ 1 होगा।



एक्सचेंज पर सैकड़ों मुद्रा जोड़े का कारोबार किया जा सकता है, और विनिमय दरों में लगातार बदलाव हो रहा है। यह समझना पहले से ही असंभव है कि लेनदेन का कौन सा क्रम एल्गोरिदम समाधान के बिना लाभ लाएगा।

एल्गोरिथम समस्या के लिए संक्रमण

एक एल्गोरिदम के रूप में संभावित मुद्रा विनिमय लेनदेन की कल्पना करें, अर्थात् एक ग्राफ के रूप में। इस ग्राफ में स्थितियाँ मुद्राओं का प्रतिनिधित्व करती हैं, और किनारे संभावित ट्रेड हैं। रिब की लंबाई विनिमय दर से मेल खाती है जिस पर लेनदेन का निष्कर्ष निकाला जा सकता है।


अगला सवाल यह है कि ऐसे कॉलम में लेन-देन का क्रम कैसे खोजा जाए जो लाभ लाए। जाहिर है, अनुक्रम की शुरुआत में और अंत में यह एक ही मुद्रा होनी चाहिए, अनुक्रम को दिए गए ग्राफ में चक्र के अनुरूप होना चाहिए। इसके बाद, आपको यह निर्धारित करने की आवश्यकता है कि दो मुद्राओं के बीच विनिमय दर की गणना कैसे की जाती है, अगर उन्हें सीधे विनिमय नहीं किया जाता है, लेकिन एक निश्चित तीसरी मुद्रा (या मध्यवर्ती संचालन की एक मनमानी संख्या) के माध्यम से। यहां सब कुछ काफी सरल भी है। इस तरह की विनिमय दर की गणना मध्यवर्ती लेनदेन की विनिमय दरों के उत्पाद के रूप में की जाएगी। लेनदेन का एक लाभदायक अनुक्रम बन जाता है यदि यह उत्पाद एक से कम मूल्य लेता है। दूसरे शब्दों में, यदि मुद्रा की एक इकाई को उसी मुद्रा की एक इकाई से कम खरीदा जा सकता है।


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




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

बेलमैन - फोर्ड एल्गोरिथम

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

इस एल्गोरिथ्म का मूल संचालन एज रिलैक्सेशन है । इस ऑपरेशन का सार इस प्रकार है। मान लीजिए कि एक बढ़त है$$$a \rightarrow b$, और चोटियों के लिए दूरी की पहले से गणना प्रारंभिक मूल्यों को भी जाना जाता है $$$a$तथा $$$b$। किनारे पर विश्राम करने के लिए, यह गणना करना आवश्यक है कि शीर्ष की दूरी क्या होगी$$$b$अगर रास्ता ऊपर से होकर गुजरे $$$a$और रिब $$$a \rightarrow b$। इस दूरी की गणना शीर्ष तक की दूरी के योग के रूप में की जाती है।$$$a$ और रिब लंबाई $$$a \rightarrow b$। इसके अलावा, अगर यह दूरी मौजूदा प्रारंभिक दूरी से कम है$$$a$तब यह बहुत दूरी है $$$a$पत्राचार और एक नया, बस गणना, मूल्य लेता है।

बाकी एल्गोरिथ्म भी सरल है। ज़रूरी$$$N$ समय ($$$N$क्या ग्राफ के कोने की संख्या है) किनारों की सूची को बायपास करें, प्रत्येक दौर के लिए एक विश्राम ऑपरेशन लागू करें। एल्गोरिथ्म की जटिलता प्राप्त की जाती है$$$N*M$ (कहाँ पे $$$N$- कोने की संख्या, और $$$M$- पसलियों की संख्या)। नकारात्मक चक्रों के बिना एक ग्राफ के लिए, आगे की शिथिलता से दूरी के कोने में बदलाव नहीं होगा। एक ही समय में, एक नकारात्मक चक्र वाले ग्राफ के लिए, विश्राम से दूरी और उसके बाद की दूरी कम हो जाएगी$$$N$मार्ग-परिवर्तन। इस संपत्ति का उपयोग वांछित चक्र को खोजने के लिए किया जा सकता है।

कोटलिन पर ऊपर वर्णित एल्गोरिथ्म के निम्नलिखित छोटे कार्यान्वयन को उन लोगों की मदद करनी चाहिए जो कोड को छांटने से अधिक परिचित हैं।

fun findNegativeCycle(nodes: Int, edges: Array<Edge>, source: Int): List<Int>? {
    // Initialize distances and prev arrays. All distances but the distance to
    // the source node are infinite, distance to the source node is zero.
    val distances = DoubleArray(nodes) { if (it == source) 0.0 else INFINITY }
    val prev = IntArray(nodes) { -1 }

    // Relax all edges N times where N is the number of nodes.
    repeat(nodes) {
        edges.forEach { it.relax(distances, prev) }
    }

    // Try to relax at least one more edge. If it's possible memorize the node,
    // otherwise return from the method.
    val firstRelaxedEdge = edges.firstOrNull { it.relax(distances, prev) }
    var node = firstRelaxedEdge?.to ?: return null

    // Step back N times where N is the number of nodes. As a result, the node will
    // be in the loop for sure.
    repeat(nodes) {
        node = prev[node]
    }

    // Recover the loop by the node that is inside it and prev links.
    val lastNode = node
    return buildList {
        do {
            add(node)
            node = prev[node]
        } while (node != lastNode)

        reverse()
    }
}

// Edge DTO with implemented relaxation operation.
data class Edge(val from: Int, val to: Int, val length: Double) {

    fun relax(distances: DoubleArray, prev: IntArray): Boolean {
        if (distances[from] + length >= distances[to]) {
            return false
        }

        distances[to] = distances[from] + length
        prev[to] = from
        return true
    }
}

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

तो, पहले आपको प्रारंभिक समान अनंत को छोड़कर सभी कोने की दूरी निर्धारित करके कोने को इनिशियलाइज़ करना होगा। प्रारंभिक शीर्ष के लिए, शून्य की दूरी निर्धारित की जाती है।


सभी पसलियों का पहला दौर अनुसरण करता है और उनके विश्राम का प्रदर्शन किया जाता है। लगभग सभी छूट रिब विश्राम को छोड़कर कोई परिणाम नहीं देते हैं$$$a \rightarrow b$। इस रिब के आराम से आप दूरी को अपडेट कर सकते हैं$$$b$।


इसके बाद ग्राफ के सभी किनारों का दूसरा राउंड और उसके बाद विश्राम होता है। इस बार, परिणाम पसलियों की छूट है।$$$b \rightarrow c$, तथा $$$b \rightarrow d$। चोटियों के लिए दूरी अद्यतन कर रहे हैं।$$$c$ तथा $$$d$। यहां यह ध्यान दिया जाना चाहिए कि परिणाम उस क्रम पर निर्भर करता है जिसमें किनारों का पता लगाया जाता है।


पसलियों के तीसरे दौर में, पहले से ही तीन पसलियों, अर्थात् पसलियों को सफलतापूर्वक आराम करना संभव है $$$\rightarrow d$, $$$d \rightarrow e$, $$$d \rightarrow b$। इस मामले में, जब पसलियों को आराम दिया जाता है$$$\rightarrow d$ तथा $$$d \rightarrow b$पहले से ही दर्ज की गई दूरी $$$d$तथा $$$b$, साथ ही पिछले कोने के लिए इसी लिंक।


चौथे दौर में, रिब छूट संचालन सफलतापूर्वक पूरा किया जाता है। $$$b \rightarrow c$तथा $$$b \rightarrow a$। इस मामले में, पहले से ही चोटियों के लिए दूरी के रिकॉर्ड किए गए मान फिर से अपडेट किए गए हैं।$$$a$ तथा $$$c$, साथ ही पिछले कोने के लिए इसी लिंक।


पांचवा दौर आखिरी है। इस वॉक के दौरान पसलियों को आराम मिलता है$$$\rightarrow d$, $$$d \rightarrow b$, $$$d \rightarrow e$। यहां आप देख सकते हैं कि नकारात्मक लंबाई के एक चक्र की उपस्थिति पहले से ही चोटियों के लिए दूरी के मूल्यों के लिए कुछ समायोजन करती है।


इस दौरे के बाद, यदि ग्राफ़ में ऋणात्मक लंबाई का चक्र नहीं था, तो एल्गोरिथ्म पूरा हो जाएगा, क्योंकि किसी भी किनारे की छूट से कोई बदलाव नहीं होगा। हालांकि, इस ग्राफ के लिए, नकारात्मक लंबाई के एक चक्र की उपस्थिति के कारण, कोई अभी भी एक किनारे पा सकता है जिसकी छूट दूरी को एक कोने में अपडेट करेगी।


एक किनारा जिसकी छूट शिखर तक की दूरी को अपडेट करती है। यह नकारात्मक लंबाई के एक चक्र की उपस्थिति की पुष्टि करता है। अब आपको यह चक्र स्वयं खोजने की आवश्यकता है। यह महत्वपूर्ण है कि शीर्ष, जो दूरी अब अपडेट की गई है, वह चक्र के अंदर और उसके बाहर दोनों हो सकती है। उदाहरण में, यह शीर्ष है$$$e$और वह चक्र से बाहर है। अगला, आपको पिछले कोने के लिंक को संदर्भित करने की आवश्यकता है, जो एल्गोरिथ्म के सभी चरणों में सावधानीपूर्वक अपडेट किए गए थे। चक्र में जाने की गारंटी देने के लिए, आपको पीछे हटना चाहिए$$$N$इन कड़ियों का उपयोग करके चोटियाँ।

इस उदाहरण में, संक्रमण निम्नानुसार होंगे:$$$e \rightarrow d \rightarrow c \rightarrow b \rightarrow d \rightarrow c$। तो सबसे ऊपर स्थित है$$$c$, जो नकारात्मक लंबाई के चक्र में झूठ बोलने की गारंटी है।


इसके अलावा, प्रौद्योगिकी का मामला है। वांछित चक्र को वापस करने के लिए, आपको पिछले कोने के लिंक का उपयोग करके फिर से पुनरावृति करने की आवश्यकता है जब तक कि शीर्ष फिर से नहीं मिलता है$$$c$। इसका मतलब यह होगा कि चक्र बंद हो गया है। पिछले अवशेषों के लिंक पर पुनरावृत्तियों के दौरान पुनरावृत्ति उलट गई थी, क्योंकि यह सब शेष है, आदेश को उल्टा करना है।

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

निष्कर्ष

आर्बिट्राज ट्रेडिंग समस्या में बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग करना एक उत्कृष्ट उदाहरण है कि शास्त्रीय एल्गोरिदम वास्तविक व्यावसायिक समस्याओं को कैसे हल कर सकते हैं, विशेष रूप से, वित्तीय क्षेत्र में। एल्गोरिथ्म की असममित जटिलता, के बराबर$$$N^3$एक पूरी तरह से जुड़ा हुआ ग्राफ के लिए, यह पता बारी काफी बड़ी हो सकता है। यह वास्तव में याद किया जाना चाहिए। हालाँकि, मुद्रा विनिमय जैसे कई मामलों में, यह जटिलता ग्राफ़ में अपेक्षाकृत कम संख्या में नोड्स के कारण कोई समस्या पैदा नहीं करती है ।