套利交易（Bellman-Ford算法）

在交易所进行交易通常会带来风险。对于大多数交易策略而言，这绝对是正确的。在这些情况下贸易的成功仅取决于正确评估和管理风险的能力。但并非所有交易策略都是如此。有无风险策略，尤其包括仲裁。本文将解释什么是仲裁以及如何使用经典的图形算法（例如Bellman-Ford算法）来实现仲裁。

什么是仲裁？

仲裁是一些逻辑上相关的交易，旨在从不同市场同时（空间仲裁）或同一市场不同时间点（临时仲裁）的相同或相关资产的价格差异获利。

举一个简单的例子，考虑空间套利。在纽约和伦敦，可以达成以欧元购买美元和以美元购买欧元的交易。在纽约，可以按4美元的汇率兑换3欧元，在伦敦，可以按5美元的汇率兑换3欧元。费率的这种差异开辟了空间仲裁的可能性。



在纽约只要花4美元，就可以买到3欧元。之后，在伦敦以3欧元5美元的价格购买。如您所见，如此简单的交易序列每投资4美元就会带来1美元的利润。因此，如果最初有400万美元，那么利润将已经是100万美元。

当同一货币对的汇率（我们不考虑价差）不同时，实施套利策略所需的交易顺序非常简单。如果一个货币对的汇率是固定的，但是几个货币对可以并行交易，那么仲裁也是可能的，但是交易的顺序已经很重要了。例如，您可以以5美元购买4欧元，以4欧元购买3英镑，然后以3英镑购买6美元。从这样的一系列交易中获得的利润为每投资5美元可获得1美元。



数百种货币对可以在交易所交易，汇率不断变化。如果没有算法解决方案，就不可能理解交易的哪些顺序将带来利润。

过渡到算法问题

想象一下算法形式（即图形形式）的潜在货币兑换交易。该图中的顶点表示货币，并且边缘是潜在交易。肋骨的长度对应于可以完成交易的汇率。


下一个问题是如何在将带来利润的列中查找一系列交易。显然，由于序列的开头和结尾处的货币必须相同，因此序列必须与给定图中的循环相对应。接下来，如果不是直接通过某种第三种货币（或任意数量的中间操作）进行交换，则需要确定两种货币之间的汇率是如何计算的。这里的一切也很简单。该汇率将作为中间交易汇率的乘积来计算。如果该产品的价值小于一个，则交易的获利顺序将变为有利。换句话说，如果可以购买的货币单位少于相同货币的单位。


经典图算法不太适合处理边长的乘积。此类算法主要用于查找定义为这些长度之和的路径。但是，为了规避此限制，有一种数学方法可以将乘积求和。这种方式是对数。如果乘积出现在对数下，则可以将这种对数转换为对数之和。在此等式的右侧，所需的数字小于1，这意味着该数字的对数应小于零。




通过这种简单的数学技巧，您可以从搜索边缘长度乘积小于1的循环到查找边缘长度总和小于零的循环。经典图形算法（更确切地说是Bellman-Ford算法）已经可以解决此类任务。

Bellman-福特算法

Bellman – Ford 算法通常用于查找从给定顶点到图形的所有其他顶点的距离，但是对它的修改允许找到负长度的循环。

该算法的基本操作是边缘松弛。该操作的实质如下。假设有一条边缘$$$a \rightarrow b$以及先前计算的到峰的距离的初步值是已知的 $$$a$和 $$$b$。要执行边缘松弛，必须计算到顶部的距离是多少$$$b$如果路径经过顶部 $$$a$和肋骨 $$$a \rightarrow b$。该距离计算为到顶部的距离之和。$$$a$ 和肋骨长度 $$$a \rightarrow b$。此外，如果此距离小于当前的初步距离，则$$$a$那么这是到的距离 $$$a$对应并采用新的，刚刚计算的值。

该算法的其余部分也不复杂。必要$$$N$ 次（$$$N$是图的顶点数）绕过边缘列表，对每轮应用松弛操作。得到算法的复杂度$$$N*M$ （哪里 $$$N$-顶点数，以及 $$$M$-肋骨数量）。对于没有负周期的图，进一步的边松弛不会导致到顶点的距离发生变化。同时，对于包含负周期的图，松弛会减少到顶点的距离，并且$$$N$绕道而行。此属性可用于找到所需的循环。

上面在Kotlin上描述的算法的以下小实现应该可以帮助那些更熟悉整理代码的人。

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$。这意味着周期已经结束。剩下的就是颠倒顺序，因为在迭代过程中，迭代是通过与先前顶点的链接进行的。

上面的算法假设存在一些初始顶点，根据该顶点可以计算距离。这种顶点的存在对于算法起作用不是必需的，但是它在更大程度上被引入以匹配原始的Bellman-Ford算法。如果感兴趣的主题是负长度的循环，那么我们可以假定给定图的所有顶点都是初始的。换句话说，到所有顶点的距离最初为零。

结论

在套利交易问题中使用Bellman-Ford算法是经典算法如何解决实际业务问题（尤其是在金融领域）的一个很好的例子。算法的渐近复杂度，等于$$$N^3$对于完全连接的图，它可能会变得很大。这确实需要记住。但是，在许多情况下，例如货币兑换，由于图中的节点数量相对较少，因此这种复杂性不会产生任何问题。