Téléportation Traveler, Profit optimal au fil du temps problème

StackOverflow https://stackoverflow.com/questions/2256589

Question

Je suis nouveau à tout le problème du voyageur de commerce, ainsi que stackoverflow alors laissez-moi savoir si je dis quelque chose qui est pas tout à fait raison.

Intro:

Je suis en train de coder un algorithme multiple commercial bénéfice / optimisé le temps pour un jeu qui implique plusieurs villes (nœuds) dans plusieurs pays (régions), où:

  • Le temps physique qu'il faut pour voyager entre les deux villes connectées est toujours le même;
  • Les villes ne sont pas linéairement connectés (vous pouvez vous téléporter entre certaines villes dans le même temps);
  • Certains pays (régions) ont des itinéraires de téléportation qui rendent le chemin le plus court disponible dans d'autres pays.
  • Le voyageur (ou commerçant) a une limite sur son porte-monnaie, le poids de ses produits, et la quantité d'une certaine négociables route commerciale. La route commerciale peut couvrir plusieurs villes.

Paramètres Question:

Il existe déjà une base de données en mémoire (python: sqlite) qui détient les métiers en fonction de leur ville d'origine et leur ville de destination, les villes plus court chemin inbetween comme un tableau et le montant, et le facteur limitant son% de rendement sur le total capital (ou dans le cas où aucun des facteurs limitent, alors que la méthode qui donne le meilleur rendement sur le capital total).

  • Je suis en train de trouver le bénéfice optimal pour une certaine partie de temps prédéfini (à savoir 30 minutes)
  • L'acte de passage dans une nouvelle ville est en fait simultanée
  • Il faut généralement la même quantité de temps définie pour voyager à travers le plan de la ville (à savoir 2 minutes)
  • L'acte d'ouverture de la première ou de tout nouveau métier prend en même temps que la traversée d'un plan de la ville (à savoir 2 minutes)
  • Mon point de départ pourrait ne pas avoir fait un métier valide (je dois rendre à la première / le plus proche / meilleur)

pseudo-solution So Far

Optimisation

D'abord, je me rends compte que parce que j'ai une limite sur le temps qu'il faut, et je sais combien de temps chaque saut prend (y compris -1 pour le commerce initiant), je peux limiter le graphique pour tous les métiers dont le houblon ou sous égale à max_hops=int(max_time/route_time) -1. Je coupe des éléments de la base de données de commerce qui ne tombent pas dans ce délai, la taille des villes qui ont le plus court chemin longueurs supérieures à max_hops.

Je fais une autre entrée dans la base de données métiers qui inclut les chemins les plus courts entre ma ville actuelle et les villes à partir de tous les métiers existants qui ne sont pas ma ville actuelle, et leur donne un rendement de 0%. Je limiter ces où le nombre de la ville du houblon est inférieure à max_hops, et je voudrais aussi calculer si la ville actuelle à la ville de départ, plus que les métiers du houblon-chemin le plus court serait excede max_hops et supprimer ceux qui ont dépassé cette limite.

Ensuite, je prends les métiers restants qui ne sont pas (current_city->starting_city) et ajouter des routes commerciales avec retour de 0% entre toutes les destinations et villes de départ wheres le houblon ne pas max_hops excede

Alors je fais une dernière pruneau pour toutes les villes qui ne sont pas dans la base de données métiers soit comme une ville de départ, la ville de destination, ou une partie des plus courts tableaux de la ville de chemin.

Graph Recherche Je suis parti avec un (beaucoup) plus petit graphique des métiers possibles dans la limite de temps (à savoir 30 minutes).

Parce que tous les noeuds connectés sont adjacents, les connexions sont par défaut tous pondérée 1. Je divise le retour% par rapport au nombre de sauts dans le commerce puis prendre l'inverse et ajouter + 1 (cela signifie un poids de 1,01 pour une voie de retour de 100%). Dans le cas où le retour est 0%, ajouter ... 2?

Il doit ensuite retourner l'itinéraire le plus rentable ...

Question:

La plupart du temps,

  1. Comment puis-je ajouter la possibilité de prendre plusieurs routes quand je l'ai laissé de l'argent ou de l'espace et de garder la route à trouver par le chemin discrete aux routes commerciales simples? En raison de la nature des produits vendus à des prix multiples et les quantités dans la ville, il y aurait beaucoup de routes qui se chevauchent.

  2. Comment puis-je lancer une nouvelle pénalise route commerciale?

  3. est la recherche graphique même utile dans cette situation?

Sur une note latérale,

  1. Quels types de pruneaux / optimisations au graphique dois-je (ou devrais-je pas) faire?
  2. est ma méthode de pondération correcte? Je sens qu'il me donnera des poids disproportionnels. Dois-je utiliser le rendement réel au lieu de pourcentage de rendement?
  3. Si je suis codage en Python sont des bibliothèques telles que -graphique python approprié pour mes besoins? Ou serait-il me sauver beaucoup de frais généraux (comme je comprends, les algorithmes de recherche graphique peuvent être de calculs) pour écrire une fonction spécialisée?
  4. Suis-je mieux loti avec une recherche *?
  5. Dois-je être précalculer des points plus court chemin dans la base de données de commerce et plafonnait optimisations ou devrais-je laisser tout le graphe recherche?
  6. Pouvez-vous remarqué quelque chose que je pourrais améliorer?
Était-ce utile?

La solution

Je pense que vous avez défini quelque chose qui s'inscrit dans une classe de problèmes appelés inventaire - des problèmes de routage. Je suppose que puisque vous avez des biens et des pièces de monnaie, le voyageur est à la fois l'achat et la vente le long de l'itinéraire choisi. Nous allons d'abord supposer que tout est déterministe - toutes les quantités de produits à la demande, l'offre disponible, l'achat et les prix de vente, etc sont connus à l'avance. La version stochastique devient plus difficile (évidemment).

L'un des objectifs serait de maximiser les profits avec une contrainte sur la bourse et les marchandises. Si le voyageur doit rentrer chez ses regards comme un tour, sinon, il ressemble à un chemin. Puisque vous n'avez pas besoin le voyageur à visiter chaque nœud, il est pas un TSP. C'est bien - les problèmes les plus courts de chemin sont généralement beaucoup plus facile que TSP à résoudre.

En raison des contraintes latérales et le choix limité des prochaines étapes à chaque noeud - j'envisager d'utiliser la programmation dynamique première tentative d'une technique de solution. Il vous aidera à énumérez ce que vous achetez et vendez à chaque étape et il y a un nombre limité d'étapes. En outre, parce que vous mettez une contrainte de temps sur la décision, qui limite l'espace d'état de choix.

Pour ceux qui ont suggéré l'algorithme de Djikstra - vous avez raison - les conventions d'étiquetage devraient inclure le temps, pièces de monnaie, et des biens et des bénéfices correspondants. Il se peut que les hypothèses de ce Djikstra peuvent ne pas fonctionner pour cela avec la complexité accrue du profit. Je n'ai pas pensé encore.

Voici un à un problème similaire dans le capital budgétisation.

Bonne chance!

Autres conseils

Si cela est un jeu où vous jouez contre les humains, je suppose que la taille totale de l'espace de données est en fait assez limitée. Dans ce cas, je serais enclin à jeter toute la taille de fantaisie que je doute vaut le coup.

Au lieu de cela, que diriez-vous d'un simple en largeur recherche?

Dressez une liste de toutes les villes, les marquer unvisited

Prenez votre ville de départ, marquer le temps de Voyage zéro 

for each city: 
  if not finished and travel time <> infinity then 
    attempt to visit all neighbors, only record the time if city is unvisited
  mark the city finished
repeat until all cities have been visited

O (): la boucle externe exécute villes * maximale houblon fois. La boucle interne exécute une fois par ville. Aucune allocation de mémoire sont nécessaires.

Maintenant, pour chaque aspect de la ville à ce que vous pouvez acheter et vendre ici là. Au moment de déterminer le taux de rendement sur le commerce rappeler que la croissance est exponentielle et non linéaire. Deux fois le bénéfice d'un commerce qui prend deux fois plus longtemps est pas une bonne affaire! Consulter comment calculer le taux de rendement interne.

Si la ville actuelle n'a pas le commerce ne vous embêtez pas avec l'analyse complète, il suffit de regarder sur les voisins et exécuter l'analyse à la place, ajoutant un au temps pour chaque mouvement.

Si vous avez des cycles CPU pour épargner (et vous très bien pourrait, signifiait quelque chose pour un être humain à jouer aura un espace de données assez petit), vous pouvez exécuter l'analyse sur toutes les villes en ajoutant dans le temps qu'il faut pour arriver à la ville.

Edit: Sur la base de votre commentaire, vous avez des tonnes de puissance CPU disponible que le jeu ne fonctionne pas sur votre CPU. Je maintiens ma solution: vérifiez tout. Je soupçonne fortement qu'il faudra plus de temps pour obtenir les informations de la route et le commerce qu'elle sera de calculer la solution optimale.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top