使用Python实现贝尔曼-福德算法

Question

使用Python实现贝尔曼-福德算法

pythonalgorithmmathgraph-algorithmbellman-ford

4

我正在尝试将Python中的Bellman-Ford图算法调整到我的需求上。

我已经解析了来自json文件的部分内容。

这是我在github上找到的Bellman Ford代码： https://github.com/rosshochwert/arbitrage/blob/master/arbitrage.py

这是我从中改编的代码：

import math, urllib2, json, re


def download():
    graph = {}
    page = urllib2.urlopen("https://bittrex.com/api/v1.1/public/getmarketsummaries")
    jsrates = json.loads(page.read())

    result_list = jsrates["result"]
    for result_index, result in enumerate(result_list):
        ask = result["Ask"]
        market = result["MarketName"]
        pattern = re.compile("([A-Z0-9]*)-([A-Z0-9]*)")
        matches = pattern.match(market)
        if (float(ask != 0)):
            conversion_rate = -math.log(float(ask))
            if matches:
                from_rate = matches.group(1).encode('ascii','ignore')
                to_rate = matches.group(2).encode('ascii','ignore')
                if from_rate != to_rate:
                    if from_rate not in graph:
                        graph[from_rate] = {}
                    graph[from_rate][to_rate] = float(conversion_rate)
    return graph

# Step 1: For each node prepare the destination and predecessor
def initialize(graph, source):
    d = {} # Stands for destination
    p = {} # Stands for predecessor
    for node in graph:
        d[node] = float('Inf') # We start admiting that the rest of nodes are very very far
        p[node] = None
    d[source] = 0 # For the source we know how to reach
    return d, p

def relax(node, neighbour, graph, d, p):
    # If the distance between the node and the neighbour is lower than the one I have now
    if d[neighbour] > d[node] + graph[node][neighbour]:
        # Record this lower distance
        d[neighbour]  = d[node] + graph[node][neighbour]
        p[neighbour] = node

def retrace_negative_loop(p, start):
    arbitrageLoop = [start]
    next_node = start
    while True:
        next_node = p[next_node]
        if next_node not in arbitrageLoop:
            arbitrageLoop.append(next_node)
        else:
            arbitrageLoop.append(next_node)
            arbitrageLoop = arbitrageLoop[arbitrageLoop.index(next_node):]
            return arbitrageLoop


def bellman_ford(graph, source):
    d, p = initialize(graph, source)
    for i in range(len(graph)-1): #Run this until is converges
        for u in graph:
            for v in graph[u]: #For each neighbour of u
                relax(u, v, graph, d, p) #Lets relax it


    # Step 3: check for negative-weight cycles
    for u in graph:
        for v in graph[u]:
            if d[v] < d[u] + graph[u][v]:
                return(retrace_negative_loop(p, source))
    return None

paths = []

graph = download()

print graph

for ask in graph:
    path = bellman_ford(graph, ask)
    if path not in paths and not None:
        paths.append(path)

for path in paths:
    if path == None:
        print("No opportunity here :(")
    else:
        money = 100
        print "Starting with %(money)i in %(currency)s" % {"money":money,"currency":path[0]}

        for i,value in enumerate(path):
            if i+1 < len(path):
                start = path[i]
                end = path[i+1]
                rate = math.exp(-graph[start][end])
                money *= rate
                print "%(start)s to %(end)s at %(rate)f = %(money)f" % {"start":start,"end":end,"rate":rate,"money":money}
    print "\n"

错误：

Traceback (most recent call last):
  File "belltestbit.py", line 78, in <module>
    path = bellman_ford(graph, ask)
  File "belltestbit.py", line 61, in bellman_ford
    relax(u, v, graph, d, p) #Lets relax it
  File "belltestbit.py", line 38, in relax
    if d[neighbour] > d[node] + graph[node][neighbour]:
KeyError: 'LTC'

当我打印图表时，我得到了所需的一切。它是“LTC”，因为它是列表中的第一个。我尝试执行和过滤LTC，但它给我带来了与图表上出现的第一个名称相同的错误：

Traceback (most recent call last):
  File "belltestbit.py", line 78, in <module>
    path = bellman_ford(graph, ask)
  File "belltestbit.py", line 61, in bellman_ford
    relax(u, v, graph, d, p) #Lets relax it
  File "belltestbit.py", line 38, in relax
    if d[neighbour] > d[node] + graph[node][neighbour]:
KeyError: 'NEO'

我不知道如何解决这个问题。谢谢大家。 PS：似乎有一个回答被删除了，我是 SO 的新手，所以不知道发生了什么。我编辑了帖子，因为答案帮助我进步 :)

- mescu

很遗憾我没有时间帮助你，但我添加了一些标签，希望这个问题能够引起关注。此外，“解释”一行代码在SO上有点模糊不清，因此最好能够引用具体的预期输出来确保安全。 - errantlinguist

谢谢@errantlinguist，已经注意到了。 - mescu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SergGr · Accepted Answer

免责声明：请注意，虽然您可以通过这种方式找到“低效率”，但您真正赚钱的机会非常低。最有可能的是，您实际上会亏损一些钱。根据我在测试期间看到的数据，这些“低效率”来自于交换率在几分钟内的波动比买卖价差更大。因此，您所看到的低效率可能只是旧数据，而您无法快速执行所有所需订单，以使汇率足够稳定以赚钱。因此，请注意，如果您尝试将此应用程序用于任何超出好奇心的目的，您可能会损失您的钱财。

现在进入正题：

您的数据格式与原始代码设计的格式不同。典型的数据片段如下：

{
    "MarketName": "BTC-ETH",
    "High": 0.05076884,
    "Low": 0.04818392,
    "Volume": 77969.61816991,
    "Last": 0.04978511,
    "BaseVolume": 3875.47491925,
    "TimeStamp": "2017-12-29T05:45:10.18",
    "Bid": 0.04978511,
    "Ask": 0.04986673,
    "OpenBuyOrders": 4805,
    "OpenSellOrders": 8184,
    "PrevDay": 0.04955001,
    "Created": "2015-08-14T09:02:24.817"
}

你感兴趣的是 MarketName、Bid 和 Ask。你需要了解 Bid 和 Ask 的含义。粗略地说，Ask 值表示如果你想用汇率 0.04986673 BTC 兑换 1 ETH，有（或者不久前曾经有）一个愿意以这个价格购买你的 BTC 的买家。同样地，Bid 值表示如果你想用汇率 0.04978511 BTC 兑换 1 ETH，有（曾经有）一个愿意以这个价格购买你的 ETH 的买家。请注意，这种结构意味着你将不会在记录中看到 "MarketName": "ETH-BTC"，因为它没有提供额外的数据。

因此，知道你可以用相应速率的对数来填充graph的适当距离。此外，我认为你的代码中还有另一个错误：由于retrace_negative_loop的参数p实际上是前任节点的字典，retrace_negative_loop以相反的顺序返回负循环。而且，由于你的图是有向的，同一条循环在一个方向上可能是正的，在另一个方向上可能是负的。

import math, urllib2, json, re


def download():
    graph = {}
    page = urllib2.urlopen("https://bittrex.com/api/v1.1/public/getmarketsummaries")
    data = page.read()
    jsrates = json.loads(data)

    result_list = jsrates["result"]
    for result_index, result in enumerate(result_list):
        ask = result["Ask"]
        bid = result["Bid"]
        market = result["MarketName"]
        pattern = re.compile("([A-Z0-9]*)-([A-Z0-9]*)")
        matches = pattern.match(market)
        if matches:
            from_rate = matches.group(1).encode('ascii', 'ignore')
            to_rate = matches.group(2).encode('ascii', 'ignore')

            # different sign of log is effectively 1/x
            if ask != 0:
                if from_rate not in graph:
                    graph[from_rate] = {}
                graph[from_rate][to_rate] = math.log(float(ask))
            if bid != 0:
                if to_rate not in graph:
                    graph[to_rate] = {}
                graph[to_rate][from_rate] = -math.log(float(bid))

    return graph  # Step 1: For each node prepare the destination and predecessor


def initialize(graph, source):
    d = {}  # Stands for destination
    p = {}  # Stands for predecessor
    for node in graph:
        d[node] = float('Inf')  # We start admiting that the rest of nodes are very very far
        p[node] = None
    d[source] = 0  # For the source we know how to reach
    return d, p


def relax(node, neighbour, graph, d, p):
    # If the distance between the node and the neighbour is lower than the one I have now
    dist = graph[node][neighbour]
    if d[neighbour] > d[node] + dist:
        # Record this lower distance
        d[neighbour] = d[node] + dist
        p[neighbour] = node


def retrace_negative_loop(p, start):
    arbitrageLoop = [start]
    prev_node = start
    while True:
        prev_node = p[prev_node]
        if prev_node not in arbitrageLoop:
            arbitrageLoop.append(prev_node)
        else:
            arbitrageLoop.append(prev_node)
            arbitrageLoop = arbitrageLoop[arbitrageLoop.index(prev_node):]
            # return arbitrageLoop
            return list(reversed(arbitrageLoop))


def bellman_ford(graph, source):
    d, p = initialize(graph, source)
    for i in range(len(graph) - 1):  # Run this until is converges
        for u in graph:
            for v in graph[u]:  # For each neighbour of u
                relax(u, v, graph, d, p)  # Lets relax it

    # Step 3: check for negative-weight cycles
    for u in graph:
        for v in graph[u]:
            if d[v] < d[u] + graph[u][v]:
                return retrace_negative_loop(p, v)
    return None




graph = download()

# print graph
for k, v in graph.iteritems():
    print "{0} => {1}".format(k, v)
print "-------------------------------"

paths = []
for currency in graph:
    path = bellman_ford(graph, currency)
    if path not in paths and not None:
        paths.append(path)

for path in paths:
    if path == None:
        print("No opportunity here :(")
    else:
        money = 100
        print "Starting with %(money)i in %(currency)s" % {"money": money, "currency": path[0]}

        for i, value in enumerate(path):
            if i + 1 < len(path):
                start = path[i]
                end = path[i + 1]
                rate = math.exp(-graph[start][end])
                money *= rate
                print "%(start)s to %(end)s at %(rate)f = %(money)f" % {"start": start, "end": end, "rate": rate,
                                                                        "money": money}

    print "\n"

同时，检查if path not in paths and not None:可能不够，因为它没有过滤掉仅是彼此旋转的path，但我也没有费心去修复它。