Maison développement back-end Tutoriel Python Exemples pour expliquer la solution de Python au problème du voyageur de commerce (TSP) basée sur le modèle d'arborescence de sous-ensemble de retour en arrière

Exemples pour expliquer la solution de Python au problème du voyageur de commerce (TSP) basée sur le modèle d'arborescence de sous-ensemble de retour en arrière

Sep 07, 2017 am 10:14 AM
python 回溯 basé sur

Cet article présente principalement Python pour résoudre le problème du voyageur de commerce (TSP) sur la base du modèle d'arbre de sous-ensemble de méthode de retour en arrière. Il décrit brièvement le problème du voyageur de commerce et analyse l'implémentation associée de Python en utilisant le modèle d'arbre de sous-ensemble de méthode de retour en arrière pour résoudre le problème. problème du voyageur de commerce sous forme d'exemples. Pour les étapes et les conseils de fonctionnement, les amis dans le besoin peuvent se référer à

Cet article décrit comment Python résout le problème du voyageur de commerce (TSP) sur la base du modèle d'arborescence de sous-ensemble de retour en arrière. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Problème

Le problème du voyageur de commerce (TSP) est le problème de Voyageurs de commerce à Pour voyager dans plusieurs villes, le coût entre chaque ville est connu Afin de réduire les coûts, le voyageur de commerce a décidé de partir de la ville où il se trouvait, de se rendre une fois dans chaque ville puis de revenir à la ville d'origine, et a demandé. lui quel itinéraire choisir pour atteindre tous les endroits Le coût total de la marche le plus court ?

Analyse

Ce problème peut être décrit comme suit : G=(V,E) est pondéré Pour un graphe orienté, trouvez un anneau orienté contenant chaque nœud de V, c'est-à-dire un itinéraire de déplacement qui minimise la somme des coûts de toutes les arêtes sur cet anneau orienté.

La différence entre cette question et l'article précédent http://www.jb51.net/article/122933.htm est que cette question est une image pondérée. Une petite modification suffit.

La longueur de la solution est fixe n+1.

Chaque nœud du graphique a son propre nœud adjacent. Pour un nœud, tous ses nœuds adjacents constituent l'espace d'état de ce nœud. Lorsque le chemin atteint ce nœud, son espace d’état est parcouru.

Au final, la solution optimale sera certainement trouvée

Évidemment, continuez à appliquer le modèle d'arbre de sous-ensemble de backtracking ! ! !

Code


'''旅行商问题(Traveling Salesman Problem,TSP)'''
# 用邻接表表示带权图
n = 5 # 节点数
a,b,c,d,e = range(n) # 节点名称
graph = [
  {b:7, c:6, d:1, e:3},
  {a:7, c:3, d:7, e:8},
  {a:6, b:3, d:12, e:11},
  {a:1, b:7, c:12, e:2},
  {a:3, b:8, c:11, d:2}
]
x = [0]*(n+1) # 一个解(n+1元数组,长度固定)
X = []     # 一组解
best_x = [0]*(n+1) # 已找到的最佳解(路径)
min_cost = 0    # 最小旅费
# 冲突检测
def conflict(k):
  global n,graph,x,best_x,min_cost
  # 第k个节点,是否前面已经走过
  if k < n and x[k] in x[:k]:
    return True
  # 回到出发节点
  if k == n and x[k] != x[0]:
    return True
  # 前面部分解的旅费之和超出已经找到的最小总旅费
  cost = sum([graph[node1][node2] for node1,node2 in zip(x[:k], x[1:k+1])])
  if 0 < min_cost < cost:
    return True
  return False # 无冲突
# 旅行商问题(TSP)
def tsp(k): # 到达(解x的)第k个节点
  global n,a,b,c,d,e,graph,x,X,min_cost,best_x
  if k > n: # 解的长度超出,已走遍n+1个节点 (若不回到出发节点,则 k==n)
    cost = sum([graph[node1][node2] for node1,node2 in zip(x[:-1], x[1:])]) # 计算总旅费
    if min_cost == 0 or cost < min_cost:
      best_x = x[:]
      min_cost = cost
      #print(x)
  else:
    for node in graph[x[k-1]]: # 遍历节点x[k-1]的邻接节点(状态空间)
      x[k] = node
      if not conflict(k): # 剪枝
        tsp(k+1)
# 测试
x[0] = c # 出发节点:路径x的第一个节点(随便哪个)
tsp(1)  # 开始处理解x中的第2个节点
print(best_x)
print(min_cost)
Copier après la connexion

Rendu

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Comment résoudre le problème des autorisations rencontré lors de la visualisation de la version Python dans le terminal Linux? Comment résoudre le problème des autorisations rencontré lors de la visualisation de la version Python dans le terminal Linux? Apr 01, 2025 pm 05:09 PM

Solution aux problèmes d'autorisation Lors de la visualisation de la version Python dans Linux Terminal Lorsque vous essayez d'afficher la version Python dans Linux Terminal, entrez Python ...

Comment copier efficacement la colonne entière d'une dataframe dans une autre dataframe avec différentes structures dans Python? Comment copier efficacement la colonne entière d'une dataframe dans une autre dataframe avec différentes structures dans Python? Apr 01, 2025 pm 11:15 PM

Lorsque vous utilisez la bibliothèque Pandas de Python, comment copier des colonnes entières entre deux frames de données avec différentes structures est un problème courant. Supposons que nous ayons deux dats ...

Les annotations des paramètres Python peuvent-elles utiliser des chaînes? Les annotations des paramètres Python peuvent-elles utiliser des chaînes? Apr 01, 2025 pm 08:39 PM

Utilisation alternative des annotations des paramètres Python Dans la programmation Python, les annotations des paramètres sont une fonction très utile qui peut aider les développeurs à mieux comprendre et utiliser les fonctions ...

Python multiplateform de bureau de bureau de bureau: quelle bibliothèque GUI est la meilleure pour vous? Python multiplateform de bureau de bureau de bureau: quelle bibliothèque GUI est la meilleure pour vous? Apr 01, 2025 pm 05:24 PM

Choix de la bibliothèque de développement d'applications de bureau multiplateforme Python De nombreux développeurs Python souhaitent développer des applications de bureau pouvant s'exécuter sur Windows et Linux Systems ...

Pourquoi mon code ne peut-il pas faire renvoyer les données par l'API? Comment résoudre ce problème? Pourquoi mon code ne peut-il pas faire renvoyer les données par l'API? Comment résoudre ce problème? Apr 01, 2025 pm 08:09 PM

Pourquoi mon code ne peut-il pas faire renvoyer les données par l'API? En programmation, nous rencontrons souvent le problème du retour des valeurs nulles lorsque l'API appelle, ce qui n'est pas seulement déroutant ...

Comment Uvicorn écoute-t-il en permanence les demandes HTTP sans servir_forever ()? Comment Uvicorn écoute-t-il en permanence les demandes HTTP sans servir_forever ()? Apr 01, 2025 pm 10:51 PM

Comment Uvicorn écoute-t-il en permanence les demandes HTTP? Uvicorn est un serveur Web léger basé sur ASGI. L'une de ses fonctions principales est d'écouter les demandes HTTP et de procéder ...

Comment les scripts Python effacent-ils la sortie en position de curseur à un emplacement spécifique? Comment les scripts Python effacent-ils la sortie en position de curseur à un emplacement spécifique? Apr 01, 2025 pm 11:30 PM

Comment les scripts Python effacent-ils la sortie en position de curseur à un emplacement spécifique? Lors de l'écriture de scripts Python, il est courant d'effacer la sortie précédente à la position du curseur ...

Google et AWS fournissent-ils des sources publiques d'image PYPI? Google et AWS fournissent-ils des sources publiques d'image PYPI? Apr 01, 2025 pm 05:15 PM

De nombreux développeurs s'appuient sur PYPI (PythonPackageIndex) ...

See all articles