---
# System prepended metadata

title: Práctica 7-Lab6 (Recocido Simulado)

---

# Práctica 7-Lab6 (Recocido Simulado)
**Profesora**: Dra. Yenny Villuendas Rey

**Escuelas**:
$^{1}$ Escuela Superior de Cómputo del IPN
$^{2}$ Centro de Investigación en Computación del IPN

**Equipo**: 
- Enya Quetzalli Gómez Rodríguez$^{1}$
- Luis Fernando Quezada Mata$^{2}$
- Osvaldo David Velazquez Gonzalez$^{2}$

[Ver en línea](https://hackmd.io/@metah/practica7)

<br>

<style tyle="text/css">
p {
text-align: justify;
}
</style>

### **1. Detalle el pseudocódigo del algoritmo de Recocido Simulado** ###

El algoritmo de recocido simulado se puede ver como una iteración de algoritmos de Metrópolis. Si se baja la temperatura suficientemente lento se puede alcanzar el equilibrio térmico en cada temperatura. Esto se hace mediante la generación de varias transiciones en cada temperatura. Se puede demostrar que bajando suficientemente lento el parámetro asociado a la temperatura y generando suficientes transiciones en cada temperatura se puede alcanzar la configuración óptima.

La probabilidad de aceptación se expresa como:

$$
P_c \{acepta, j\} = 
\begin{cases}
 & \text{ 1 } \quad\quad\quad\quad\quad\quad \quad si f(j) \leq f(i) \\ 
 & \ exp(\frac{f(i)-f(j)}{c_k}) \quad\quad si f(j) >  f(i)
\end{cases}
$$
Dode $c \in R^+$ denota al parámetro de control.


\begin{align}
&k=0, i=i_{start}
\\
&\textbf{repite:}
\\
&\quad \textbf{para } l=1,\dots,L_k \textbf{ haz:}
\\
& \quad \quad \text{genera } j \in S_j
\\
& \quad \quad  \textbf{si } f(j) \leq f(i) \textbf{ entonces: }
\\
& \quad \quad \quad i=j
\\
& \quad \quad \textbf{si no, si } exp(\frac{f(i)-f(j)}{c_k}) > aleatorio[0,1] \textbf{ entonces: }
\\
& \quad \quad \quad i=j
\\
& \quad k = k + 1
\\
& \quad \text{actualiza } L_k \text{ y } c_k
\\
& \quad \textbf{end}
\\
& \textbf{hasta } \text{criterio de paro}
\end{align}

La velocidad de convergencia del algoritmo está determinada por $L_k$ y $c_k$.

### **2. Compárelo con el algoritmo de RMHC** ###

Partiendo de la elección inicial de estado, ambos algoritmos eligen uno de manera aleatoria.

Con respecto a la exploración del espacio de estados, en el caso de el algoritmo RMHC, el estado es sujeto a una mutación aleatoria; mientras que en el algortimo SA, el estado tiene asociada una vecindad, de la cual se elige aleatoriamente un estado diferente. Es posible, sin embargo, que la vecindad de un estado en el algoritmo SA coincida con el conjunto de las posibles mutaciones generadas por ese mismo estado en el algoritmo RMHC.

En el algoritmo RMHC se eligen únicamente las mutaciones con menor costo (o mayor beneficio) que el estado original. Por otra parte, en el algoritmo SA, si bien estos estados también se eligen en caso de ser seleccionados, los estados con mayor costo (o menor beneficio) también pueden ser seleccionados con cierta probabilidad, la cual irá disminuyendo conforme la temperatura lo haga. Cabe destacar que no existe un parámetro análogo a la temperatura del algoritmo SA en el algoritmo RMHC.

Por último, el algoritmo SA tiene la característica de encontrar óptimos globales; mientras que el algoritmo RMHC, al seleccionar únicamente mejores opciones en cada evaluación, puede quedarse atascado en un ótimo local.

<br>

### **3. Realice la modelación matemática necesaria para la solución, mediante SA, del Problema del Viajero Vendedor (Travel Salesman problem).**
***Recuerde que la modelación matemática incluye: definición de los estados inicial y final, definición del test objetivo, y definición de las acciones posibles (operadores)***

En el problema del viajero vendedor se plantea la existencia de $n$ ciudades conectadas por vías, cada una de las cuales tiene asociada un costo. El problema consiste en encontrar un camino de costo mínimo en el que se visiten todas las ciudades sin repetir el paso por ninguna de ellas, con excepción de la ciudad de la cual se partió, que es justo a la que se regresará al final del camino.

El conjunto de $n$ ciudades y vías entre ellas puede modelarse con el grafo simple y conexo $G$, asignando a cada arista un peso. Cada nodo del grafo representa una ciudad, las aristas representan las vías entre ellas y el peso de cada arista representa el costo de la vía. El problema del viajero vendedor consiste entonces en encontrar un ciclo de Hamilton de costo mínimo, en donde el costo del ciclo está dado por la suma de los costos de las aristas que lo conforman. En este trabajo se considerará el grafo $G$ como no dirigido.

Debido a que la existencia y cantidad de ciclos de Hamilton en un grafo arbitrario es díficil de caracterizar, y considerando que todo grafo simple y conexo de orden $n$ es un subgrafo del grafo completo $K_{n}$; en este trabajo se considerará al grafo $G$ de $n$ ciudades como un subgrafo del grafo completo $K_{n}$, asignando un costo infinito (o muy grande) a las aristas que no existan en el grafo $G$.

El conjunto de vértices de $K_{n}$ se denotará como $V$, y está dado por
\begin{equation}
V = \left\lbrace V_{1},\dots,V_{n} \right\rbrace.
\end{equation}

Por otro lado, el conjunto de aristas, denotado como $E$, es de la forma
\begin{equation}
E = \left\lbrace  \left\lbrace u,v \right\rbrace \subseteq V \: \middle| \:  u \neq v \right\rbrace,
\end{equation}

en donde cada arista $\left\lbrace u,v \right\rbrace$ tiene un costo asociado $Cost(\left\lbrace u,v \right\rbrace)$ dada por una función $Cost : E \rightarrow \mathbb{R}^{+}$.

Para resolver el problema usando el algoritmo SA, definimos el espacio de estados como el conjunto
\begin{equation}
S =\left\lbrace (P_{1},\dots,P_{n}) \in V^{n} \: \middle| \: \; P_{i} \neq P_{j} \; \forall \, i \neq j \right\rbrace,
\end{equation}

en donde el estado inicial será cualquier elemento elegido aleatoriamente de este conjunto. Nótese que el espacio de estados está bien definido gracias a que se está trabajando sobre el grafo $K_{n}$, de manera que todas las posibles aristas existen.

Los operadores, es decir las acciones posibles, están dados por un intercambio de componentes, y pueden modelarse como
\begin{equation}
\hat{M}_{ij}(P_{1},\dots,P_{i},\dots,P_{j}, \dots, P_{n}) = (P_{1},\dots,P_{j},\dots,P_{i}, \dots, P_{n}),
\end{equation}

es decir, el operador $\hat{M}_{ij}$ intercambia las componentes $i,j$ del estado $\bar{P}$.

El algoritmo SA requiere definir una vecindad para cada estado en $S$. Entonces, con base en los operadores y dado un estado arbitrario $\bar{P}$, definimos la vecindad de $\bar{P}$ como

\begin{equation}
V_{\bar{P}} = \left\lbrace \hat{M}_{ij}(\bar{P}) \: \middle| \: i \neq j \right\rbrace
\end{equation}

La función objetivo en este caso está dada por el costo del ciclo, la cual se define como
\begin{equation}
f(\bar{P}) = Cost(\left\lbrace P_{1},P_{n} \right\rbrace) + \sum_{i=1}^{n-1} Cost(\left\lbrace P_{i},P_{i+1} \right\rbrace),
\end{equation}

y es justamente la que el algoritmo busca minimizar.

Además, dado un estado $\bar{P}$ con una vecindad $V_{\bar{P}}$, cada elemento $\bar{Q}$ de la vecidad tiene una probabilidad asociada $\mathcal{P}_{\bar{P}}(\bar{Q})$ dada por:

\begin{equation}
\mathcal{P}_{\bar{P}}(\bar{Q}) =  \text{exp}\left( \frac{f(\bar{P})-f(\bar{Q})}{T} \right)
\end{equation}

donde $T$ representa la temperatura.

Entonces, el algoritmo SA consiste en elegir aleatoriamente un elemento $\bar{Q}$ de la vecidad $V_{\bar{P}}$, evaluar $\delta(\bar{Q},\bar{P}) = f(\bar{Q})-f(\bar{P})$:

* Si $\delta(\bar{Q},\bar{P}) \leq 0$, es decir que el costo del estado $\bar{P}$ es mayor o igual que el del estado $\bar{Q}$, entonces $\bar{Q}$ reemplazará a $\bar{P}$ como el estado en turno.
* Si $\delta(\bar{Q},\bar{P}) > 0$, es decir que el estado $\bar{Q}$ tiene un menor beneficio que el estado $\bar{P}$, entonces $\bar{Q}$ reemplazará a $\bar{P}$ con base en su probabilidad asociada $\mathcal{P}_{\bar{P}}(\bar{Q})$.

Otra acción posible (operador) es la de disminuir la temperatura hasta alcanzar $T=0$ (o un valor muy cercano). Esto hace que la probabilidad de aceptar estados con mayot costo disminuya conforme el algoritmo avanza.

El estado final en el algoritmo SA será el óptimo global, es decir, el estado de $S$ con el menor costo.

<br>




### **4. Realice una corrida manual del algoritmo de Recocido Simulado sobre el problema anterior. Defina para ello un esquema de recorido de su preferencia** ### 

![](https://i.imgur.com/7rX2aLp.jpg)

<br>

### **5. Para el problema planteado, proponga las estructuras de datos necesarias para su implementación** ###

Se utilizará un arreglo $state$ para representar a $P$, siendo $state$ de tamaño $n+1$ donde $state_{n+1} = state_1$. 

Para la representación del grafo $G$ se utilizará una lista de adyacencias $graph$ mediante el uso de un *map* o *dictionary* que dado un nodo como *llave*, mapea como su *valor* la lista de nodos conectados a él. 

Para la representación de los costos $cost$, se utilizará un *map* o *dictionary* que dada una tupla $(u,v) \in E$ como *llave*, mapea como su valor el costo establecido en la entrada de datos. 

<br>

### **6. Diseñe la interfaz de usuario para la solución del problema planteado mediante Recocido Simulado** ##

Para la interfaz de usuario, se decidió utilizar una representación por lista de adyacencias y parejas de nodos para los costos, todo mediante representación en formato *JSON*. Por ejemplo, para representar el grafo:

![](https://i.imgur.com/KY9h2mn.png)


Necesitartemos una representación de entrada como la siguiente:

```json=1
inputGraph = {
	1: [2,3,7],
	2: [1,3,4],
	3: [1,2,4,5,7],
	4: [2,3,5,6],
	5: [4,3,6,7],
	6: [4,5,7],
	7: [1,3,5,6],
}
inputCost = {
	(1,2):12,
	(1,3):10,
	(1,7):12,
	(2,3):8,
	(3,7):9,
	(2,4):12,
	(3,4):11,
	(3,5):3,
	(5,7):7,
	(4,5):11,
	(4,6):10,
	(5,6):6,
	(6,7):9
}
```

<br>

### **7. Ejecute la solución del problema planteado mediante Recocido simulado, utilizando para ello las estructuras de datos y la interfaz gráfica diseñadas** ###

```python=1
import random
import copy
import math
from graphviz import Digraph as dg
from graphviz import Graph as ug
```

Comenzamos creando valores globales que nos facilitaran el acceso a la información dentro de las funciones
```python=7
graph = {}
cost = {}
isDirectedGraph = False
infinite = 10000000000
n = 0
```

Crearemos una función auxiliar que nos ayudará en la actualización de las variables globales así como en la definición del grafo dirigido o no dirigido.
```python=13
def initialize(inputGraph, inputCost, directed = False):
    graph.update(inputGraph)
    global n,isDirectedGraph
    isDirectedGraph = directed
    n += len(graph.items())
    if(directed == False):
      for key,value in inputCost.items():
        cost[(key[0],key[1])] = value
        cost[(key[1],key[0])] = value
    else:
      cost.update(inputCost)
```

Tendremos una función auxiliar que nos permitirá dibujar gráficamente nuestra entrada de datos.
```python=1
def drawGraph(solution = False, path = []):
  G = dg('G') if isDirectedGraph else ug('G')
  G.strict = True
  G.graph_attr['rankdir'] = 'LR'
  G.node_attr['shape'] = 'circle'

  for node,neighbours in graph.items():
    for ne in neighbours:
      G.edge(str(node), str(ne), color='black', label=str(cost[(node,ne)]))
  if solution == False:
    return G
  for i in range(1, len(path)):
    G.edge(str(path[i-1]), str(path[i]), color='red')
  return G
```

Esta función nos regresará el costo total de un camino.
```python=40
def pathCost(path): 
  total_cost = 0
  for i in range(1,len(path)):
    if (path[i-1],path[i]) in cost:
      total_cost += cost[(path[i-1],path[i])]
    else:
      total_cost += infinite
  return total_cost
```

La *DFS* será una función auxiliar que nos ayudará a comenzar con un estado solución válido.
```python=49
def dfs(me, father, path, start):
  if me == start and len(path) == n+1:
    return copy.copy(path)
  if start == -1:
    start = me
  for node in graph[me]:
    if node != father and node not in path[1:]:
      path.append(node)
      solution = dfs(node, me, path, start)
      if len(solution) > 0:
        return solution
      path.pop()
  return []
```

Nos regresa el costo del estado, encapsulado para atender las necesidades de la función principal
```python=63
def getStateScore(state):
  return [pathCost(state)]
```

Esta función calcula únicamente la diferencia entre el estado anterior y el nuevo estado, ayudando con el calculo de un estado en tiempo $O(1)$
```python=66
def getDeltaScore(state, score, new_state, position):
  new_score = score[0]

  #First 
  pos = position[0]
  prev = position[0]-1
  next = (position[0]+1)%len(state) if position[0]+1 != len(state) else (position[0]+2)%len(state)
  new_score -= cost[(state[prev],state[pos])] if (state[prev],state[pos]) in cost else infinite
  new_score -= cost[(state[pos],state[next])] if (state[pos],state[next]) in cost else infinite
  new_score += cost[(new_state[prev],new_state[pos])] if (new_state[prev],new_state[pos]) in cost else infinite
  new_score += cost[(new_state[pos],new_state[next])] if (new_state[pos],new_state[next]) in cost else infinite

  #Second
  pos = position[1]
  prev = position[1]-1
  next = (position[1]+1)%len(state) if position[1]+1 != len(state) else (position[1]+2)%len(state)
  new_score -= cost[(state[prev],state[pos])] if (state[prev],state[pos]) in cost else infinite
  new_score -= cost[(state[pos],state[next])] if (state[pos],state[next]) in cost else infinite
  new_score += cost[(new_state[prev],new_state[pos])] if (new_state[prev],new_state[pos]) in cost else infinite
  new_score += cost[(new_state[pos],new_state[next])] if (new_state[pos],new_state[next]) in cost else infinite

  return [new_score]
```

Esta función valida que tengamos un estado válido en nuestro espacio de soluciones.
```python=89
def isValidState(state, score):
  if len(state) != n+1:
    return False
  for node in state:
    if node not in graph:
      return False
  return True
```

Esta función nos devuelve una solución aleatoria para el problema.
```python=97
def randomState():
  random.seed(a=None)
  while True:
    for node,neighbours in graph.items():
      random.shuffle(neighbours)
    path = [random.choice(list(graph.keys()))]
    state = dfs(path[0], -1, path, -1)
    score = getStateScore(state)
    if isValidState(state, score):
      break
  return state,score
```

Esta función calculará en $O(n)$ un nuevo estado vecino, donde $n$ es el número máximo de iteraciones. No es una cota fiable debido a que es un algoritmo aleatorio.
```python=109
def neighbour(state, score):
  state_copy = copy.copy(state)
  score_copy = copy.copy(score)
  while True:
    random_position1 = random.randint(1, len(state)-1)
    random_position2 = random.randint(1, len(state)-1)
    state_copy[random_position1], state_copy[random_position2] = state_copy[random_position2], state_copy[random_position1]
    state_copy[0] = state_copy[len(state)-1]
    score_copy = getDeltaScore(state, score, state_copy, (random_position1, random_position2))
    if isValidState(state_copy, score_copy) and state[random_position1] != state_copy[random_position1] and state[random_position2] != state_copy[random_position2]:
      break
    state_copy[random_position1], state_copy[random_position2] = state_copy[random_position2], state_copy[random_position1]
    state_copy[0] = state_copy[len(state)-1]
    score_copy = copy.copy(score)
  return state_copy, score_copy
```

Esta es nuestra función del recocido simulado.
```python=125
def rs(cooler, time_per_temperature, final_temperature, verbose=True, k=1.380649e-23):
  state, score = randomState()
  temperature = score[0]*0.4
  if verbose: print("T", round(temperature,2), " Cost=", score[0], " -> ", state)

  while temperature >= final_temperature:
    for i in range(0, time_per_temperature):
      new_state, new_score = neighbour(state,score)
      delta = new_score[0]-score[0]
      if verbose: print("\t", "Neighbour: Cost=", new_score[0], " -> ", new_state, end='')
      if delta < 0 or random.uniform(0,1) < math.exp(-delta/temperature):
        state,score = new_state, new_score
        if verbose: print(" !New Accepted", end='')
      if verbose: print()
    if verbose: print("T", round(temperature,2), " Cost=", score[0], " -> ", state)
    temperature = cooler(temperature)
  return state
```

Establecemos nuestra lambda enfriadora.
```python=143
cooler = lambda t : t*random.uniform(0.8,0.99)
```

Introducimos nuestros datos de entrada.
```python=145
#Datos de entrada
inputGraph = {
	1: [2,3,7],
	2: [1,3,4],
	3: [1,2,4,5,7],
	4: [2,3,5,6],
	5: [4,3,6,7],
	6: [4,5,7],
	7: [1,3,5,6],
}
inputCost = {
	(1,2):12,
	(1,3):10,
	(1,7):12,
	(2,3):8,
	(3,7):9,
	(2,4):12,
	(3,4):11,
	(3,5):3,
	(5,7):7,
	(4,5):11,
	(4,6):10,
	(5,6):6,
	(6,7):9
}
initialize(inputGraph, inputCost, False)
drawGraph()
```

Y ejecutamos nuestro algoritmo.
```python=173
solution = rs(cooler, 10, 0.1)
```

Como podemos ver en los resultados, la penalización a los estados invalidos tiene en efecto positivo en la aceptación incluso en temperaturas altas, por lo que únicamente tendremos aceptación de malos estado en estados que sean una solución válida.
Finalmente, podemos ver como el algoritmo llegó a una solución global. 
```txt
T 26.0  Cost= 65  ->  [3, 5, 6, 7, 1, 2, 4, 3]
	 Neighbour: Cost= 30000000038  ->  [3, 5, 4, 7, 1, 2, 6, 3]
	 Neighbour: Cost= 20000000044  ->  [3, 5, 6, 2, 1, 7, 4, 3]
	 Neighbour: Cost= 20000000044  ->  [3, 5, 6, 1, 7, 2, 4, 3]
	 Neighbour: Cost= 20000000044  ->  [1, 5, 6, 7, 3, 2, 4, 1]
	 Neighbour: Cost= 20000000047  ->  [3, 5, 1, 7, 6, 2, 4, 3]
	 Neighbour: Cost= 20000000044  ->  [3, 5, 6, 1, 7, 2, 4, 3]
	 Neighbour: Cost= 10000000057  ->  [3, 4, 6, 7, 1, 2, 5, 3]
	 Neighbour: Cost= 10000000057  ->  [3, 4, 6, 7, 1, 2, 5, 3]
	 Neighbour: Cost= 10000000059  ->  [5, 3, 6, 7, 1, 2, 4, 5]
	 Neighbour: Cost= 20000000049  ->  [3, 1, 6, 7, 5, 2, 4, 3]
T 26.0  Cost= 65  ->  [3, 5, 6, 7, 1, 2, 4, 3]
	 Neighbour: Cost= 20000000047  ->  [3, 5, 1, 7, 6, 2, 4, 3]
	 Neighbour: Cost= 10000000057  ->  [3, 4, 6, 7, 1, 2, 5, 3]
	 Neighbour: Cost= 10000000060  ->  [3, 6, 5, 7, 1, 2, 4, 3]
	 Neighbour: Cost= 10000000060  ->  [2, 5, 6, 7, 1, 3, 4, 2]
	 Neighbour: Cost= 10000000059  ->  [5, 3, 6, 7, 1, 2, 4, 5]
	 Neighbour: Cost= 20000000049  ->  [3, 1, 6, 7, 5, 2, 4, 3]
	 Neighbour: Cost= 20000000047  ->  [3, 5, 1, 7, 6, 2, 4, 3]
	 Neighbour: Cost= 20000000041  ->  [3, 5, 6, 7, 2, 1, 4, 3]
	 Neighbour: Cost= 10000000059  ->  [3, 7, 6, 5, 1, 2, 4, 3]
	 Neighbour: Cost= 20000000044  ->  [3, 5, 6, 1, 7, 2, 4, 3]
T 21.58  Cost= 65  ->  [3, 5, 6, 7, 1, 2, 4, 3]
	 Neighbour: Cost= 10000000057  ->  [3, 4, 6, 7, 1, 2, 5, 3]
	 Neighbour: Cost= 30000000036  ->  [3, 5, 2, 7, 1, 6, 4, 3]
	 Neighbour: Cost= 20000000051  ->  [3, 2, 6, 7, 1, 5, 4, 3]
	 Neighbour: Cost= 20000000049  ->  [3, 1, 6, 7, 5, 2, 4, 3]
	 Neighbour: Cost= 20000000047  ->  [7, 5, 6, 3, 1, 2, 4, 7]
	 Neighbour: Cost= 20000000047  ->  [3, 5, 1, 7, 6, 2, 4, 3]
	 Neighbour: Cost= 10000000052  ->  [3, 5, 6, 7, 4, 2, 1, 3]
	 Neighbour: Cost= 10000000057  ->  [3, 4, 6, 7, 1, 2, 5, 3]
	 Neighbour: Cost= 10000000052  ->  [3, 5, 6, 7, 4, 2, 1, 3]
	 Neighbour: Cost= 30000000038  ->  [3, 5, 4, 7, 1, 2, 6, 3]
T 18.43  Cost= 65  ->  [3, 5, 6, 7, 1, 2, 4, 3]
	 Neighbour: Cost= 20000000040  ->  [3, 5, 6, 4, 1, 2, 7, 3]
	 Neighbour: Cost= 20000000051  ->  [3, 2, 6, 7, 1, 5, 4, 3]
	 Neighbour: Cost= 10000000052  ->  [3, 5, 6, 7, 4, 2, 1, 3]
	 Neighbour: Cost= 10000000052  ->  [3, 5, 6, 7, 4, 2, 1, 3]
	 Neighbour: Cost= 10000000052  ->  [3, 5, 6, 7, 4, 2, 1, 3]
	 Neighbour: Cost= 10000000060  ->  [2, 5, 6, 7, 1, 3, 4, 2]
	 Neighbour: Cost= 20000000044  ->  [3, 5, 6, 2, 1, 7, 4, 3]
	 Neighbour: Cost= 20000000044  ->  [3, 5, 6, 2, 1, 7, 4, 3]
	 Neighbour: Cost= 20000000044  ->  [3, 5, 6, 1, 7, 2, 4, 3]
	 Neighbour: Cost= 30000000038  ->  [3, 5, 4, 7, 1, 2, 6, 3]
T 17.7  Cost= 65  ->  [3, 5, 6, 7, 1, 2, 4, 3]
	 Neighbour: Cost= 10000000060  ->  [2, 5, 6, 7, 1, 3, 4, 2]
	 Neighbour: Cost= 10000000060  ->  [3, 6, 5, 7, 1, 2, 4, 3]
	 Neighbour: Cost= 30000000036  ->  [3, 5, 2, 7, 1, 6, 4, 3]
	 Neighbour: Cost= 10000000059  ->  [5, 3, 6, 7, 1, 2, 4, 5]
	 Neighbour: Cost= 30000000038  ->  [3, 5, 4, 7, 1, 2, 6, 3]
	 Neighbour: Cost= 10000000059  ->  [5, 3, 6, 7, 1, 2, 4, 5]
	 Neighbour: Cost= 10000000054  ->  [3, 5, 7, 6, 1, 2, 4, 3]
	 Neighbour: Cost= 10000000060  ->  [2, 5, 6, 7, 1, 3, 4, 2]
	 Neighbour: Cost= 69  ->  [4, 5, 6, 7, 1, 2, 3, 4] !New Accepted
	 Neighbour: Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4] !New Accepted
T 16.21  Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000060  ->  [5, 4, 6, 7, 1, 3, 2, 5]
	 Neighbour: Cost= 10000000060  ->  [5, 4, 6, 7, 1, 3, 2, 5]
	 Neighbour: Cost= 10000000050  ->  [3, 5, 6, 7, 1, 4, 2, 3]
	 Neighbour: Cost= 30000000043  ->  [4, 5, 2, 7, 1, 3, 6, 4]
	 Neighbour: Cost= 20000000051  ->  [4, 5, 6, 3, 1, 7, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 2, 6, 7, 1, 3, 5, 4]
	 Neighbour: Cost= 10000000050  ->  [3, 5, 6, 7, 1, 4, 2, 3]
	 Neighbour: Cost= 20000000048  ->  [4, 5, 6, 2, 1, 3, 7, 4]
	 Neighbour: Cost= 20000000051  ->  [4, 5, 6, 3, 1, 7, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 5, 7, 6, 1, 3, 2, 4]
T 13.01  Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4]
	 Neighbour: Cost= 65  ->  [4, 6, 5, 7, 1, 3, 2, 4] !New Accepted
	 Neighbour: Cost= 10000000052  ->  [4, 6, 1, 7, 5, 3, 2, 4]
	 Neighbour: Cost= 10000000058  ->  [2, 6, 5, 7, 1, 3, 4, 2]
	 Neighbour: Cost= 10000000052  ->  [4, 6, 1, 7, 5, 3, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000046  ->  [5, 6, 4, 7, 1, 3, 2, 5]
	 Neighbour: Cost= 20000000051  ->  [4, 2, 5, 7, 1, 3, 6, 4]
	 Neighbour: Cost= 30000000043  ->  [4, 6, 3, 7, 1, 5, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000051  ->  [4, 2, 5, 7, 1, 3, 6, 4]
T 11.91  Cost= 65  ->  [4, 6, 5, 7, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000044  ->  [1, 6, 5, 7, 4, 3, 2, 1]
	 Neighbour: Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4] !New Accepted
	 Neighbour: Cost= 20000000048  ->  [4, 5, 6, 2, 1, 3, 7, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 5, 7, 6, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000046  ->  [1, 5, 6, 7, 4, 3, 2, 1]
	 Neighbour: Cost= 20000000047  ->  [6, 5, 4, 7, 1, 3, 2, 6]
	 Neighbour: Cost= 10000000057  ->  [4, 2, 6, 7, 1, 3, 5, 4]
	 Neighbour: Cost= 69  ->  [4, 5, 6, 7, 3, 1, 2, 4] !New Accepted
	 Neighbour: Cost= 20000000048  ->  [6, 5, 4, 7, 3, 1, 2, 6]
	 Neighbour: Cost= 10000000056  ->  [7, 5, 6, 4, 3, 1, 2, 7]
T 11.71  Cost= 69  ->  [4, 5, 6, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000059  ->  [1, 5, 6, 7, 3, 4, 2, 1]
	 Neighbour: Cost= 10000000059  ->  [4, 5, 6, 7, 2, 1, 3, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 5, 3, 7, 6, 1, 2, 4]
	 Neighbour: Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4] !New Accepted
	 Neighbour: Cost= 20000000045  ->  [4, 7, 6, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [4, 5, 3, 7, 1, 6, 2, 4]
	 Neighbour: Cost= 30000000043  ->  [4, 5, 2, 7, 1, 3, 6, 4]
	 Neighbour: Cost= 20000000045  ->  [4, 7, 6, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000052  ->  [4, 5, 1, 7, 6, 3, 2, 4]
	 Neighbour: Cost= 20000000045  ->  [4, 7, 6, 5, 1, 3, 2, 4]
T 10.68  Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000041  ->  [7, 5, 6, 4, 1, 3, 2, 7]
	 Neighbour: Cost= 20000000046  ->  [1, 5, 6, 7, 4, 3, 2, 1]
	 Neighbour: Cost= 20000000045  ->  [4, 7, 6, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 69  ->  [4, 5, 6, 7, 3, 1, 2, 4] !New Accepted
	 Neighbour: Cost= 10000000059  ->  [4, 5, 6, 7, 2, 1, 3, 4]
	 Neighbour: Cost= 10000000061  ->  [5, 4, 6, 7, 3, 1, 2, 5]
	 Neighbour: Cost= 30000000040  ->  [4, 5, 2, 7, 3, 1, 6, 4]
	 Neighbour: Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4] !New Accepted
	 Neighbour: Cost= 10000000057  ->  [4, 5, 7, 6, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000058  ->  [4, 5, 6, 1, 7, 3, 2, 4]
T 9.44  Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000045  ->  [4, 7, 6, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 65  ->  [4, 6, 5, 7, 1, 3, 2, 4] !New Accepted
	 Neighbour: Cost= 20000000046  ->  [4, 6, 2, 7, 1, 3, 5, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 1, 2, 3, 4] !New Accepted
	 Neighbour: Cost= 10000000060  ->  [6, 4, 5, 7, 1, 2, 3, 6]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 5, 4, 1, 2, 3, 7]
	 Neighbour: Cost= 20000000044  ->  [4, 7, 5, 6, 1, 2, 3, 4]
	 Neighbour: Cost= 10000000060  ->  [6, 4, 5, 7, 1, 2, 3, 6]
	 Neighbour: Cost= 30000000036  ->  [4, 6, 2, 7, 1, 5, 3, 4]
T 8.5  Cost= 66  ->  [4, 6, 5, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 1, 5, 7, 6, 2, 3, 4]
	 Neighbour: Cost= 10000000060  ->  [3, 6, 5, 7, 1, 2, 4, 3]
	 Neighbour: Cost= 10000000051  ->  [5, 6, 4, 7, 1, 2, 3, 5]
	 Neighbour: Cost= 69  ->  [4, 5, 6, 7, 1, 2, 3, 4] !New Accepted
	 Neighbour: Cost= 20000000045  ->  [1, 5, 6, 7, 4, 2, 3, 1]
	 Neighbour: Cost= 65  ->  [5, 4, 6, 7, 1, 2, 3, 5] !New Accepted
	 Neighbour: Cost= 20000000044  ->  [1, 4, 6, 7, 5, 2, 3, 1]
	 Neighbour: Cost= 69  ->  [4, 5, 6, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 10000000049  ->  [5, 7, 6, 4, 1, 2, 3, 5]
	 Neighbour: Cost= 30000000038  ->  [5, 4, 2, 7, 1, 6, 3, 5]
T 7.26  Cost= 65  ->  [5, 4, 6, 7, 1, 2, 3, 5]
	 Neighbour: Cost= 10000000059  ->  [5, 4, 6, 7, 3, 2, 1, 5]
	 Neighbour: Cost= 10000000055  ->  [5, 4, 6, 7, 2, 1, 3, 5]
	 Neighbour: Cost= 20000000050  ->  [5, 4, 6, 3, 1, 2, 7, 5]
	 Neighbour: Cost= 10000000059  ->  [5, 3, 6, 7, 1, 2, 4, 5]
	 Neighbour: Cost= 69  ->  [4, 5, 6, 7, 1, 2, 3, 4] !New Accepted
	 Neighbour: Cost= 40000000034  ->  [4, 5, 2, 7, 1, 6, 3, 4]
	 Neighbour: Cost= 20000000045  ->  [1, 5, 6, 7, 4, 2, 3, 1]
	 Neighbour: Cost= 65  ->  [5, 4, 6, 7, 1, 2, 3, 5] !New Accepted
	 Neighbour: Cost= 69  ->  [4, 5, 6, 7, 1, 2, 3, 4] !New Accepted
	 Neighbour: Cost= 10000000059  ->  [4, 5, 6, 7, 2, 1, 3, 4]
T 6.93  Cost= 69  ->  [4, 5, 6, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 20000000045  ->  [1, 5, 6, 7, 4, 2, 3, 1]
	 Neighbour: Cost= 40000000034  ->  [4, 5, 2, 7, 1, 6, 3, 4]
	 Neighbour: Cost= 40000000034  ->  [4, 5, 2, 7, 1, 6, 3, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 1, 2, 3, 4] !New Accepted
	 Neighbour: Cost= 10000000060  ->  [4, 6, 5, 2, 1, 7, 3, 4]
	 Neighbour: Cost= 20000000054  ->  [4, 6, 3, 7, 1, 2, 5, 4]
	 Neighbour: Cost= 20000000041  ->  [4, 6, 5, 3, 1, 2, 7, 4]
	 Neighbour: Cost= 20000000047  ->  [4, 6, 5, 1, 7, 2, 3, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 6, 5, 7, 3, 2, 1, 4]
	 Neighbour: Cost= 20000000047  ->  [4, 6, 5, 1, 7, 2, 3, 4]
T 5.7  Cost= 66  ->  [4, 6, 5, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 6, 5, 7, 3, 2, 1, 4]
	 Neighbour: Cost= 20000000041  ->  [4, 6, 5, 3, 1, 2, 7, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 5, 4, 1, 2, 3, 7]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 5, 4, 1, 2, 3, 7]
	 Neighbour: Cost= 20000000044  ->  [4, 7, 5, 6, 1, 2, 3, 4]
	 Neighbour: Cost= 10000000060  ->  [4, 6, 5, 2, 1, 7, 3, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 1, 7, 5, 2, 3, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 1, 7, 5, 2, 3, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 6, 5, 7, 3, 2, 1, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 3, 5, 7, 1, 2, 6, 4]
T 5.24  Cost= 66  ->  [4, 6, 5, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 20000000041  ->  [4, 6, 5, 3, 1, 2, 7, 4]
	 Neighbour: Cost= 10000000051  ->  [5, 6, 4, 7, 1, 2, 3, 5]
	 Neighbour: Cost= 10000000051  ->  [5, 6, 4, 7, 1, 2, 3, 5]
	 Neighbour: Cost= 10000000057  ->  [4, 6, 7, 5, 1, 2, 3, 4]
	 Neighbour: Cost= 10000000060  ->  [4, 6, 5, 2, 1, 7, 3, 4]
	 Neighbour: Cost= 20000000054  ->  [4, 6, 3, 7, 1, 2, 5, 4]
	 Neighbour: Cost= 69  ->  [4, 5, 6, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 30000000036  ->  [4, 6, 2, 7, 1, 5, 3, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 1, 5, 7, 6, 2, 3, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 5, 4, 1, 2, 3, 7]
T 4.42  Cost= 66  ->  [4, 6, 5, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 3, 5, 7, 1, 2, 6, 4]
	 Neighbour: Cost= 10000000060  ->  [4, 6, 5, 2, 1, 7, 3, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 5, 7, 2, 1, 3, 4]
	 Neighbour: Cost= 10000000060  ->  [3, 6, 5, 7, 1, 2, 4, 3]
	 Neighbour: Cost= 20000000043  ->  [1, 6, 5, 7, 4, 2, 3, 1]
	 Neighbour: Cost= 10000000051  ->  [5, 6, 4, 7, 1, 2, 3, 5]
	 Neighbour: Cost= 20000000043  ->  [1, 6, 5, 7, 4, 2, 3, 1]
	 Neighbour: Cost= 65  ->  [4, 6, 5, 7, 1, 3, 2, 4] !New Accepted
	 Neighbour: Cost= 20000000043  ->  [4, 7, 5, 6, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 6, 1, 7, 5, 3, 2, 4]
T 4.21  Cost= 65  ->  [4, 6, 5, 7, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000046  ->  [4, 6, 2, 7, 1, 3, 5, 4]
	 Neighbour: Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4] !New Accepted
	 Neighbour: Cost= 10000000060  ->  [2, 5, 6, 7, 1, 3, 4, 2]
	 Neighbour: Cost= 10000000057  ->  [4, 5, 7, 6, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000060  ->  [5, 4, 6, 7, 1, 3, 2, 5]
	 Neighbour: Cost= 10000000058  ->  [4, 5, 6, 1, 7, 3, 2, 4]
	 Neighbour: Cost= 10000000060  ->  [5, 4, 6, 7, 1, 3, 2, 5]
	 Neighbour: Cost= 20000000052  ->  [4, 5, 1, 7, 6, 3, 2, 4]
	 Neighbour: Cost= 20000000044  ->  [4, 5, 6, 7, 2, 3, 1, 4]
	 Neighbour: Cost= 10000000060  ->  [2, 5, 6, 7, 1, 3, 4, 2]
T 3.42  Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000060  ->  [5, 4, 6, 7, 1, 3, 2, 5]
	 Neighbour: Cost= 20000000045  ->  [4, 7, 6, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000044  ->  [4, 5, 6, 7, 2, 3, 1, 4]
	 Neighbour: Cost= 10000000060  ->  [2, 5, 6, 7, 1, 3, 4, 2]
	 Neighbour: Cost= 10000000057  ->  [4, 2, 6, 7, 1, 3, 5, 4]
	 Neighbour: Cost= 30000000044  ->  [4, 3, 6, 7, 1, 5, 2, 4]
	 Neighbour: Cost= 20000000052  ->  [4, 5, 1, 7, 6, 3, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [6, 5, 4, 7, 1, 3, 2, 6]
	 Neighbour: Cost= 20000000041  ->  [7, 5, 6, 4, 1, 3, 2, 7]
	 Neighbour: Cost= 10000000057  ->  [4, 2, 6, 7, 1, 3, 5, 4]
T 3.32  Cost= 68  ->  [4, 5, 6, 7, 1, 3, 2, 4]
	 Neighbour: Cost= 30000000044  ->  [4, 3, 6, 7, 1, 5, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [4, 5, 3, 7, 1, 6, 2, 4]
	 Neighbour: Cost= 20000000039  ->  [4, 1, 6, 7, 5, 3, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 5, 7, 6, 1, 3, 2, 4]
	 Neighbour: Cost= 30000000043  ->  [4, 5, 2, 7, 1, 3, 6, 4]
	 Neighbour: Cost= 20000000047  ->  [4, 5, 3, 7, 1, 6, 2, 4]
	 Neighbour: Cost= 20000000051  ->  [4, 5, 6, 3, 1, 7, 2, 4]
	 Neighbour: Cost= 69  ->  [4, 5, 6, 7, 1, 2, 3, 4] !New Accepted
	 Neighbour: Cost= 20000000048  ->  [4, 5, 6, 1, 7, 2, 3, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 5, 6, 1, 7, 2, 3, 4]
T 3.17  Cost= 69  ->  [4, 5, 6, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 20000000055  ->  [4, 3, 6, 7, 1, 2, 5, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 1, 2, 3, 4] !New Accepted
	 Neighbour: Cost= 10000000057  ->  [4, 6, 7, 5, 1, 2, 3, 4]
	 Neighbour: Cost= 30000000036  ->  [4, 6, 2, 7, 1, 5, 3, 4]
	 Neighbour: Cost= 10000000051  ->  [5, 6, 4, 7, 1, 2, 3, 5]
	 Neighbour: Cost= 20000000047  ->  [4, 6, 5, 1, 7, 2, 3, 4]
	 Neighbour: Cost= 30000000042  ->  [4, 2, 5, 7, 1, 6, 3, 4]
	 Neighbour: Cost= 20000000054  ->  [4, 6, 3, 7, 1, 2, 5, 4]
	 Neighbour: Cost= 10000000060  ->  [6, 4, 5, 7, 1, 2, 3, 6]
	 Neighbour: Cost= 10000000060  ->  [4, 6, 5, 2, 1, 7, 3, 4]
T 2.63  Cost= 66  ->  [4, 6, 5, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 20000000041  ->  [4, 6, 5, 3, 1, 2, 7, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 3, 5, 7, 1, 2, 6, 4]
	 Neighbour: Cost= 10000000060  ->  [6, 4, 5, 7, 1, 2, 3, 6]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 5, 7, 2, 1, 3, 4]
	 Neighbour: Cost= 20000000043  ->  [1, 6, 5, 7, 4, 2, 3, 1]
	 Neighbour: Cost= 65  ->  [4, 6, 5, 7, 1, 3, 2, 4] !New Accepted
	 Neighbour: Cost= 20000000043  ->  [4, 7, 5, 6, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000043  ->  [4, 7, 5, 6, 1, 3, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 1, 2, 3, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
T 2.36  Cost= 65  ->  [4, 6, 5, 7, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000044  ->  [1, 6, 5, 7, 4, 3, 2, 1]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4] !New Accepted
	 Neighbour: Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4] !New Accepted
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000041  ->  [2, 6, 7, 5, 3, 1, 4, 2]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
T 2.08  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 20000000041  ->  [2, 6, 7, 5, 3, 1, 4, 2]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 3, 5, 7, 1, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
T 1.78  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
T 1.63  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
T 1.51  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
T 1.37  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
T 1.23  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
T 1.02  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
T 1.01  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
T 0.9  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 3, 5, 7, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 20000000041  ->  [2, 6, 7, 5, 3, 1, 4, 2]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
T 0.89  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000041  ->  [2, 6, 7, 5, 3, 1, 4, 2]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 3, 5, 7, 1, 2, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 20000000041  ->  [2, 6, 7, 5, 3, 1, 4, 2]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
T 0.83  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
T 0.7  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
T 0.64  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 3, 5, 7, 1, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
T 0.56  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
T 0.53  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
T 0.44  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 3, 5, 7, 1, 2, 4]
T 0.41  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
T 0.35  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
T 0.31  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 3, 5, 7, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 20000000041  ->  [2, 6, 7, 5, 3, 1, 4, 2]
T 0.28  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
T 0.23  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 20000000041  ->  [2, 6, 7, 5, 3, 1, 4, 2]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
T 0.2  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
T 0.19  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
	 Neighbour: Cost= 20000000041  ->  [2, 6, 7, 5, 3, 1, 4, 2]
	 Neighbour: Cost= 10000000061  ->  [4, 5, 7, 6, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
T 0.17  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 5, 1, 3, 2, 4]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 3, 5, 7, 1, 2, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
T 0.15  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 20000000042  ->  [6, 4, 7, 5, 3, 1, 2, 6]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 3, 5, 7, 1, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
T 0.14  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 6, 1, 5, 3, 7, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 20000000042  ->  [4, 2, 7, 5, 3, 1, 6, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
T 0.13  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [7, 6, 4, 5, 3, 1, 2, 7]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
T 0.13  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 10000000055  ->  [4, 6, 7, 3, 5, 1, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 10000000057  ->  [4, 3, 7, 5, 6, 1, 2, 4]
	 Neighbour: Cost= 66  ->  [4, 6, 5, 7, 3, 1, 2, 4]
	 Neighbour: Cost= 10000000052  ->  [4, 7, 6, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 30000000034  ->  [4, 1, 7, 5, 3, 6, 2, 4]
	 Neighbour: Cost= 20000000048  ->  [4, 6, 7, 2, 3, 1, 5, 4]
T 0.11  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 10000000049  ->  [4, 6, 7, 5, 3, 2, 1, 4]
	 Neighbour: Cost= 10000000059  ->  [4, 6, 7, 5, 2, 1, 3, 4]
	 Neighbour: Cost= 20000000048  ->  [5, 6, 7, 4, 3, 1, 2, 5]
	 Neighbour: Cost= 20000000047  ->  [3, 6, 7, 5, 4, 1, 2, 3]
	 Neighbour: Cost= 20000000041  ->  [2, 6, 7, 5, 3, 1, 4, 2]
	 Neighbour: Cost= 30000000035  ->  [4, 6, 2, 5, 3, 1, 7, 4]
	 Neighbour: Cost= 10000000054  ->  [1, 6, 7, 5, 3, 4, 2, 1]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
	 Neighbour: Cost= 10000000056  ->  [4, 6, 7, 1, 3, 5, 2, 4]
T 0.11  Cost= 63  ->  [4, 6, 7, 5, 3, 1, 2, 4]
```

Finalmente, veremos una muestra gráfica de nuestra solución obtenida.
```python=175
drawGraph(True, solution)
```
![](https://i.imgur.com/rBUCZR1.png)


<br>
