ホームページ >バックエンド開発 >Python チュートリアル >バックトラッキング サブセット ツリー テンプレートに基づいた巡回セールスマン問題 (TSP) に対する Python の解決策を説明する例
この記事では主に、バックトラッキング手法サブセット ツリー テンプレートに基づいて巡回セールスマン問題 (TSP) を解決するための Python を紹介します。巡回セールスマン問題について簡単に説明し、バックトラッキング手法サブセット ツリー テンプレートを使用した Python の関連実装手順と実装手順を分析します。例の形式で巡回セールスマン問題を解決します。運用スキルを必要とする友人はそれを参照できます
この記事では、バックトラッキング手法のサブセット ツリー テンプレートに基づいて Python で巡回セールスマン問題 (TSP) を解く例について説明します。詳細は次のとおりです:
問題
巡回セールスマン問題 (TSP) は複数の都市を旅行したいと考えており、各都市間のコストがわかっています。コストを節約するために、巡回セールスマンは、自分がいる都市から出発して、各都市に一度移動し、その後、元の都市に戻ることにしました。総コストを最小化するにはどのルートを選択すればよいでしょうか?
分析
この問題は次のように説明できます: G=(V,E) は、V の各ノードを含む有向リング、つまり、次のツアー ルートを見つけます。この有向リング上のすべてのエッジ コストの合計を最小化します。
この質問と前の記事 http://www.jb51.net/article/122933.htm の違いは、この質問が重み付けされた画像であることです。ほんの少しの変更を加えるだけで十分です。
解の長さはn+1に固定されています。
グラフ内のすべてのノードには、独自の隣接ノードがあります。ノードの場合、そのノードに隣接するすべてのノードがこのノードの状態空間を構成します。パスがこのノードに到達すると、その状態空間が横断されます。
最終的には、最適な解決策が必ず見つかります!
もちろん、バックトラッキング手法のサブセット ツリー テンプレートを適用し続けてください! ! !
コード
'''旅行商问题(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)
レンダリング
以上がバックトラッキング サブセット ツリー テンプレートに基づいた巡回セールスマン問題 (TSP) に対する Python の解決策を説明する例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。