Reviews/VasilyKorchagin/TSP — различия между версиями

Текущая версия на 21:24, 13 июня 2011

#!/usr/bin/python2
# -*- coding: utf8 -*-
 
from itertools import permutations
 
def TSP_bool(n, D, B):
    """
    Верно ли, что минимально возможное значение суммы меньше B?
    """
    for p in permutations(xrange(1, n)): # Перебор всех перестановок
        length = D[0][p[0]] # Прибавляем путь из первой вершины
        if length  > 0 and D[p[-1]][0] > 0: # Путь p связен с v0
            found = True
            for i in xrange(len(p) - 1):
                if D[p[i]][p[i + 1]] == -1: # Нет такого ребра
                    found = False # Путь не найден
                    break
                length += D[p[i]][p[i + 1]]
                if length > B: # Если сумма больше B, то путь не найден
                    found = False
                    break
            #print found
            if found:
                # Прибавляем путь из последней вершины в первую
                if length + D[p[-1]][0] < B:
                    return True, p
    return False, ()
 
def TSP(n, D):
    B_min = 0
    # n умножить на максимальный вес
    B_max = n * max([inner for outer in D for inner in outer])
    true_path = ()
    while B_max - B_min > 1:
        B = (B_min + B_max) / 2
        tsp_bool, path = TSP_bool(n, D, B)
        if tsp_bool:
            true_path = path
            B_max = B
        else:
            B_min = B
    if TSP_bool(n, D, B_min)[0]:
        return B_min, true_path
    return B_max, true_path
 
D = [
 [0 , 15, 20, 15, -1],
 [15, 0 , 50, 10, 60],
 [20, 50, 0 , 30, 50],
 [15, 10, 30, 0 , 80],
 [-1, 60, 50, 80, 0 ]
]
 
print TSP(5, D)

Замечания

• От лишней пунктуации надо избавляться — это же питон, максимум простоты и читаемости.
  • ; не нужны.
  • лишние скобки вокруг возвращаемых tuples не нужны.
  • «продления строк» \ внутри скобочных конструкций не нужны.

• sum — встроенная функция, переменную надо именовать по-другому.
• continue, break — это почти что «goto», их желательно избегать, тут это возможно.
• Все лишнее нужно выкидывать. Например «else-ветвь» в конце.
• n — это свойство «матрицы» D, гонять его отдельным параметром — отстой.

Главное

• Программа неверна.
• Возвращает:

(156, (2, 4, 1, 3))

— по матрице стоимостей сразу видно, что ни один путь не может стоить 156 (должен делится на 5).