Quelle est la différence entre un voyageur de commerce et un voyageur chinois?

Quelle est la Différence entre voyage-problème de voyageur de commerce et chinois postier problème?
Pour moi les deux veut aller à une destination, puis en arrière.

source d'informationauteur alansiqueira27

  1. 7

    Le voyageur de commerce est d'aller à chaque ville une fois et en prenant la route la plus courte.

    Le Postier Chinois Problème est sur un chemin d'accès de chaque ville, de chaque autre ville.

    E. g. avec les points A, B, C et D le voyageur de commerce qui pourrait aller de A-B-C-D-A, mais les Chinois facteur irait besoin d'un itinéraire qui a A-B et A-C et A-D, etc.

    Le voyageur de commerce n'est pas direct entre chaque point (dans l'exemple ci-dessus il n'y A pas C link).

    EDIT:

    Chaque ville est un sommet et chaque inter-city link est un avantage. Donc, je pense que je suis juste en retraitant @Xodarap de réponse.

  2. 10

    Graphiques sont faits d'arêtes et de sommets. RPC exige une visite de tous les bords. C. à thé exige une visite de tous les sommets.

  3. 3

    À partir d'une brève lecture des deux articles (et je n'ai jamais pris un cours de théorie des graphes, afin que je puisse être de parler à travers mon chapeau), il apparaît que le "RPC" implique la visite de tous bords, et le "TSP" implique la visiter tous les nœuds.

  4. 2

    Gardant ultra-simple:

    La Problème du voyageur de commerce est d'aller à chaque ville exactement une fois, tandis que le retour à la ville d'origine (donc en marchant le long d'une Cycle hamiltonien) et aussi en prenant le chemin le plus court parmi tous les itinéraires possibles qui répondent à ce critère (si une telle voie existe). Trouver un tel cycle, perforce trouver peut-être unique le cycle optimal avec la distance la plus courte est "dur".

    La Chinois Postier Problème ou Itinéraire d'Inspection Problème est à propos de la visite de chaque route entre les villes au moins une fois, tandis que le retour à l'origine de la ville et de prendre le chemin le plus court parmi tous les itinéraires possibles qui répondent à ce critère (si une telle voie existe). Une solution qui prend chaque itinéraire exactement une fois est automatiquement optimale et appelé Cycle Eulérien. Trouver un tel cycle est "faisable".

  5. 1

    Je pense que c'est juste une autre variation de la trajectoire de problème présenté dans la comp de la sci cours au collège.

    Chinois Problème du voyageur de commerce (TSP) est un exemple typique symétrique c. à thé de problème. Ses simple
    la description est: étant Donné une liste de 31 les capitaux de la chine des villes et de leurs distances deux à deux, la tâche est de trouver le plus rapidement possible à la visite de chaque ville exactement une fois. Le C-TSP est un moyennes
    C. à thé de problème, ce qui a (31-1)!/2 =1.326 *1032 les itinéraires possibles.

  6. 1

    La principale différence entre les deux est:

    Le Problème du voyageur de commerce ne pouvez pas visiter un nœud plus d'une fois. Le chemin produit sera composé de tous les différents nœuds/villes.

    Les Chinois Postier/Route d'Inspection problème peut avoir des nœuds dupliqués dans le chemin produit (mais pas dupliquer les bords). I. e. les nœuds peuvent être visités plus d'une fois aussi longtemps que vous prenez une autre route que vous avez pris.

  7. 1

    Problème Du Voyageur De Commerce:
    Compte tenu des villes et de la distance entre les villes, trouver la distance la plus courte visite, telles que des visites de la ville exactement un. La visualisation de ce qu'un graphe et d'un coût ou d'un poids associé à chaque arête, trouver le moins cher ou le moins de poids tour (chemin Hamiltonien) de telle sorte que chacun des sommets ou nœud est visité exactement une fois. Nous pouvons penser à ce que la recherche de tous les possibles chemin Hamiltonien et ensuite trouver le meilleur d'entre eux. Trouver tous les itinéraires possibles est un problème d'optimisation et de la NP - Complet signifie pas de temps polynomial une solution existe pour ce problème

    Chinois Postier Problème:
    Contrairement au problème du voyageur de commerce, le RPC exige de trouver un moindre coût ou le poids minimum d'un tour à travers le graphe tel que chaque arête est visité au moins une fois. Le problème a polynôme solution et la solution optimale nécessite de trouver une Euler tournée à travers le graphe si le graphe est Eulérien. D'autre modifier le graphique pour le rendre eulérien et de définir une Euler tour. Une instance spéciale de Postier Chinois Problème est de savoir où nous n'avons pas besoin de parcourir toutes les arêtes du graphe, mais seulement certains d'entre eux (Obligatoire bords). Cette variation est appelée Rural facteur de problème et est NP-complet. En d'autres termes, étant donné un graphe, trouver un coût minimum/minimum poids de la tour tel que tous les bords sont couverts au moins une fois peut-être à l'aide de la non-requis bords.