Problème intéressant (arbitrage de Devises)

Arbitrage est le processus d'utilisation des écarts de change, des valeurs de gagner des bénéfices.
Considérer une personne qui commence avec une certaine quantité de la monnaie X, passe par une série d'échanges, et enfin se termine avec plus de quantité de X(qu'il avait d'abord).
Étant donné n de devises et un tableau (nxn) des taux de change, de concevoir un algorithme qui une personne doit utiliser pour profiter au maximum des bénéfices en supposant qu'il n'a pas d'effectuer un échange de plus d'une fois.

J'ai pensé à une solution comme ceci:

  1. Utiliser la modification de l'algorithme de Dijkstra pour trouver la source unique la plus longue du produit chemin.
  2. Cela donne plus longue du produit chemin de la source de change pour chaque devise autre.
  3. Maintenant, itérer sur chaque devise autre et de se multiplier au maximum du produit jusqu'à présent, w(curr,source)(poids de bord à la source).
  4. Sélectionnez le maximum de tous ces chemins.

Si cela semble bon, j'ai encore le doute de la justesse de cet algorithme et de la complétude du problème.(j'.e Est le problème NP-Complet?) comme il ressemble un peu à de la problème du voyageur de commerce.

La recherche de vos commentaires et de meilleures solutions(le cas échéant) pour ce problème.

Grâce.

EDIT:
Recherche Google pour ce sujet qui m'a pris à ce ici, où l'arbitrage de détection a été abordée, mais les échanges pour un maximum d'arbitrage n'est pas.Ce qui pourrait servir de référence.

Est-ce devoirs? Je sais pour un fait que c'est un problème dans le manuel pour les algorithmes sûr, j'ai TA ed il y a quelques années.
Devoirs? _____
Ouais, c'est à partir de Dasgupta, les Algorithmes de (ne pas dire que c'est le seul endroit où ça vient). Et je ne vois aucun lien de voyageur de commerce. Vous n'êtes pas essayez de visiter toutes les devises.
Certainement devoirs. Aussi le sujet n'est pas utile.
Par produit, il signifie que le poids du chemin est le produit de son arête de poids au lieu de la (d'habitude), en somme.

OriginalL'auteur sud03r | 2010-02-17

Leave a Reply

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *