質問する

海外販売員の巡回問題は英語で旅行Salesman問題(TSP)と呼ばれる問題であり、コンピュータ科学分野で最も重要な問題の一つである.様々な変種問題がありますが、最も一般的な形式の問題を見てみましょう.
1番からN番までの都市があり、都市の間に道があります.(道がないかもしれませんが)今あるセールスマンはある都市を出発して、N都市を通って、元の都市に戻るツアー旅行ルートを計画しています.でも、もう一回行った町には行けない.(最後に旅行を始めた都市に戻るのを除く)このような旅行ルートはいろいろあるかもしれませんが、最小限の旅行計画を立てたいと思っています.
行列W[i][j]の形で各パス時間の移動に要する費用が与えられる.W[i][j]は、都市iから都市jまでの料金を示す.費用は非対称です.すなわち、W[i][j]はW[j][i]とは異なる場合がある.すべての都市の費用は正の整数です.W[i][i]は常に0.場合によっては、都市iから都市jまでは不可能であり、この場合、W[i][j]=0となる.
Nと費用行列が与えられた場合、費用が最も低いセールスマンの巡回旅行経路を解くプログラムを作成します.

入力

1行目は都市の数Nを与える.(2≦N≦10)次のN行には費用行列がある.各行列の成分は1000000以下の正の整数であり、行けない場合は0を与える.W[i][j]は都市iからjまでの料金を表す.
常に巡ることができる場合のみ入力されます.

しゅつりょく

1行目は外販員のツアーに必要な最小費用を出力します.

に答える

外審員のすべての数字は巡回しなければならない.これは最小値を求める問題だ.permutationを使用してすべてのシーケンスを取得した後
順番を確認し、最小長さを求める.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from itertools import permutations

N = int(input())            # 네명이면?
nums = list(range(N))       # 0,1,2,3 네명 만들어주기
graph =[]
for _ in range(N):
    graph.append(list(map(int,input().split())))
every = list(permutations(nums,N)) # 0,1,2,3 으로 만들수 있는 모든 순열 만들기

result = int(1e9)   # 큰값을 하나 만들어 놓는다
for cycle in every: # 아까만든 순열을 하나씩 돌면서
    count =0        # 길의 합을 구해준다
    for i in range(-1,N-1): # (0,1) (1,2) (2,3) (3,0) 을 계산하기 위한 (-1~3)
        if graph[cycle[i]][cycle[i+1]]==0:  # 만약 길이 막혀있다면
            count = int(1e9)                # count 초기화
        else:                               # 길이 열려있다면
            count += graph[cycle[i]][cycle[i+1]]    # 합해준다
    result = min(count,result)              # 이전과 비교해 최소값을 구해준다
                                            # 닫혀있다면 처음 값 그대로
if result == int(1e9):                      # 열린 길이 없다면
    print(0)                                # 0 출력
else:
    print(result)                           # 아니면 결과값 출력