route.py

# coding:utf-8
import heapq
import time

current_milli_time = lambda: int(round(time.time() * 1000))

timeStart = current_milli_time()

class State:
    def __init__(self, initialCost, routeArray, visitedNodeArray, costArray):
        self.cost = initialCost;
        self.routeArray = routeArray
        self.markVisitedNode = visitedNodeArray
        self.costArray = costArray
        self.updated = False
        pass
    def addRoute(self, routeLbl):
        self.cost += cost_matrix[self.routeArray[-1] - 1][routeLbl - 1]
        self.costArray.append(cost_matrix[self.routeArray[-1] - 1][routeLbl - 1])
        self.routeArray.append(routeLbl);
        if minEachCost[routeLbl-1] > cost_matrix[self.routeArray[-1] - 1][routeLbl - 1]: 
            minEachCost[routeLbl-1] = cost_matrix[self.routeArray[-1] - 1][routeLbl - 1]
            self.updated = True
        pass

cost_matrix = [
               [0, 7, 12, 8, 11, 7],
               [3, 0, 10, 7, 13, 2],
               [4, 8, 0, 9, 12, 3],
               [6, 6, 9, 0, 10, 7],
               [7, 7, 11, 10, 0, 5],
               [9, 7, 8, 9, 10, 0]
               ]

SIZE = len(cost_matrix[0])
minCostMatrix = [0] * SIZE
minTopState = []

minEachCost = [0] * SIZE

heap = []

# 初期のルート候補を挙げる
for i in xrange(SIZE):
    if i == 0:
        continue
    mark = [False] * SIZE
    mark[i] = True
    node = State(0, [1], mark[:], [])
    node.addRoute(i + 1)
    node.markVisitedNode[i] = True
    
    heapq.heappush(heap, (cost_matrix[0][i], node))
    
while len(heap) != 0 :
    
    top = heapq.heappop(heap)
    
    # ルートを巡回した（帰りの１以外）場合のループを抜ける前の処理
    if len(top[1].routeArray) == SIZE:
        top[1].markVisitedNode[0] = True
        top[1].addRoute(1)
        minTopState = top[1]
        # 優先度付きキューから取り出した最初の状態クラスのインスタンスが
        # 最小エネルギーの経路となるため一つ答えを得て終了
        break
    
    for i in xrange(1, SIZE):
        if top[1].routeArray[-1] == (i + 1):
            continue
        if len(top[1].routeArray) < SIZE and top[1].markVisitedNode[i] == False:
            newNode = State(top[1].cost, top[1].routeArray[:], top[1].markVisitedNode[:], top[1].costArray[:])
            newRoute = i + 1
            newNode.addRoute(newRoute)
            newNode.markVisitedNode[i] = True
            heapq.heappush(heap, (newNode.cost, newNode))
        else:
            pass
# 経路、コストの確認
print(minTopState.routeArray, minTopState.cost, current_milli_time() - timeStart)