Chương trình phát hiện cơ hội arbitrage tỷ giá hối đoái trong Python

Cho ma trận N x N tỷ giá hối đoái: matrix[i][j] = số tiền tệ j mua được bằng 1 đơn vị tiền tệ i. Kiểm tra có chu kỳ arbitrage (bắt đầu tiền tệ nào đó, giao dịch vòng, cuối lại có nhiều hơn ban đầu) hay không.

Ví dụ ma trận 3x3 (USD, CAD, EUR) → True (có arbitrage).

Giải thuật (Bellman-Ford trên log tỷ giá)

1. Biến đổi: weight = -log2(rate). Arbitrage ⇔ tổng trọng lượng chu kỳ < 0 ⇔ chu kỳ âm.
2. Chạy Floyd-Warshall (hoặc Bellman-Ford) tìm đường đi ngắn nhất mọi cặp.
3. Nếu đường chéo dist[i][i] < 0 → có chu kỳ âm → arbitrage.

Ví dụ minh họa

import math

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        # Chuyển tỷ giá thành trọng số -log2
        for i in range(n):
            for j in range(n):
                matrix[i][j] = -math.log(matrix[i][j], 2)
        # Floyd-Warshall
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if matrix[i][j] > matrix[i][k] + matrix[k][j]:
                        matrix[i][j] = matrix[i][k] + matrix[k][j]
        # Kiểm tra đường chéo âm
        return any(matrix[i][i] < 0 for i in range(n))

ob = Solution()
matrix = [[1, 1.28, 0.82], [0.78, 1, 0.65], [1.21, 1.55, 1]]
print(ob.solve(matrix))  # Output: True

Đầu vào / Đầu ra

Input: ma trận 3x3 tỷ giá

Output: True