De alhos a bugalhos

Vamos falar de um problema... ou talvez não.

Existem ficheiros em formato tsp que como o nome indicam têm informação relevante para resolver o problema do caixeiro viajante. Eis um exemplo para o caso das cidades do Sahara Ocidental.

NAME : wi29
COMMENT : 29 locations in Western Sahara
COMMENT : Derived from National Imagery and Mapping Agency data
TYPE : TSP
DIMENSION : 29
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
1 20833.3333 17100.0000
2 20900.0000 17066.6667
3 21300.0000 13016.6667
4 21600.0000 14150.0000
5 21600.0000 14966.6667
6 21600.0000 16500.0000
7 22183.3333 13133.3333
8 22583.3333 14300.0000
9 22683.3333 12716.6667
10 23616.6667 15866.6667
11 23700.0000 15933.3333
12 23883.3333 14533.3333
13 24166.6667 13250.0000
14 25149.1667 12365.8333
15 26133.3333 14500.0000
16 26150.0000 10550.0000
17 26283.3333 12766.6667
18 26433.3333 13433.3333
19 26550.0000 13850.0000
20 26733.3333 11683.3333
21 27026.1111 13051.9444
22 27096.1111 13415.8333
23 27153.6111 13203.3333
24 27166.6667 9833.3333
25 27233.3333 10450.0000
26 27233.3333 11783.3333
27 27266.6667 10383.3333
28 27433.3333 12400.0000
29 27462.5000 12992.2222
EOF

Depois de um cabeçalho aparecem as coordenadas das cidades precedidas de um identificador, no caso um inteiro com o número de ordem da cidade. Os algoritmos evolucionários que desenvolvemos para este problema assumem que o que conhecemos é a matriz das distâncias entre pares de cidades. Coloca-se por isso a necessidade de fazer um interface entre os dados guardados num ficheiro e as distâncias guardadas numa lista de listas. É o que é feito no código que se segue.

def le_coordenadas_tsp(ficheiro):
    """ Devolve a matriz das coordenadas a partir de ficheiro em formato tsp."""
    fich_in = open(ficheiro)
    tudo = fich_in.readlines()
    coordenadas = []
    for linha in tudo[7:-1]:
 n,x,y = linha[:-1].split()
 coordenadas.append((float(x),float(y)))
    fich_in.close()
    return coordenadas

def dicio_cidades(coordenadas):
    """ Cria um dicionário com as cidades e suas coordenadas."""
    dicio = {}
    for i, (x,y) in enumerate(coordenadas):
 dicio[i] = (x,y)
    return dicio


def fenotipo(genotipo,dic_cidades):
    """ Devolve o fenótipo associado."""
    fen = [dic_cidades[cidade] for cidade in genotipo]
    return fen

def evaluate(caminho):
    num_cidades = len(caminho)
    comp = 0
    for i in range(num_cidades):
 j = (i+1) % num_cidades
 comp  += distancia(caminho[i],caminho[j])
    return comp

def distancia(cid_i, cid_j):
    """ Distância Euclidiana."""
    x_i, y_i = cid_i
    x_j, y_j = cid_j
    dx = x_i - x_j
    dy = y_i - y_j
    dist = sqrt(dx**2 + dy**2)
    return dist

Na primeira parte a informação é extraída do ficheiro (le_coordenadas) e colocada num dicionário (dicio_cidades). De seguida podemos transformar uma permutação numa lista de coordenadas (fenotipo). A partir desse conhecimento podemos calcular as distância euclidiana entre qualquer par de cidades (evaluate e distancia). Nesta solução este código deve estar embebido no programa. Para ser tudo transformado de uma só vez, temos que fazer diferente:

def data_tsp_matrix(file_data):
    coordenadas = le_coordenadas_tsp(file_data)
    dic_cidades = dicio_cidades(coordenadas)
    city_matrix = [[0]* len(dic_cidades) for i in range(len(dic_cidades))]
    for i in range(len(dic_cidades)):
 for j in range(i+1,len(dic_cidades)):
     city_matrix[i][j] = city_matrix[j][i] = distancia(dic_cidades[i],dic_cidades[j])
    return city_matrix  

Este programa funciona para qualquer ficheiro em formato tsp. Admite a versão simétrica, isto é, ir de A a B custa o mesmo que ir de B a A.