StasFomin в 21:24, 13 июня 2011

2011-06-13T21:24:50Z

Новая страница

<code-python>
#!/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)
</code-python>

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

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

== Главное ==
* Программа неверна.
* Возвращает:
(156, (2, 4, 1, 3))
— по матрице стоимостей сразу видно, что ни один путь не может стоить 156 (должен делится на 5).

Reviews/VasilyKorchagin/TSP - История изменений

StasFomin в 21:24, 13 июня 2011