hmt #4013
Description
"""
Simulated Annealing for Hamiltonian Cycle / Hamiltonian Path
This Python module implements a simulated annealing solver to search for a Hamiltonian
cycle (or path) in a graph. It supports:
- general undirected graphs (sparse or complete)
- weighted or unweighted edges
- ability to search for Hamiltonian cycle (closed) or Hamiltonian path (open)
- easily-adjustable temperature schedule and neighbor operator
Usage example (at bottom of file): run the module to see a quick demonstration.
Author: ChatGPT
"""
import random
import math
import time
from typing import Dict, Tuple, List, Optional, Set
Graph = Dict[int, Dict[int, float]] # adjacency: node -> (neighbor -> weight)
def is_hamiltonian_cycle(order: List[int], graph: Graph) -> bool:
"""Check whether order forms a Hamiltonian cycle on graph.
- All vertices must appear exactly once (except returning to start), and
- Every consecutive pair must have an edge.
"""
n = len(order)
if n == 0:
return False
if len(set(order)) != n:
return False
# Check edges between consecutive nodes and last to first
for i in range(n):
a = order[i]
b = order[(i + 1) % n]
if b not in graph.get(a, {}):
return False
return True
def path_cost(order: List[int], graph: Graph, closed: bool = True) -> float:
"""Compute total cost of path. If closed True, add cost from last back to first."""
cost = 0.0
for i in range(len(order) - 1):
a, b = order[i], order[i + 1]
if b not in graph.get(a, {}):
return float('inf')
cost += graph[a][b]
if closed and len(order) > 0:
a, b = order[-1], order[0]
if b not in graph.get(a, {}):
return float('inf')
cost += graph[a][b]
return cost
def random_initial_solution(nodes: List[int]) -> List[int]:
order = nodes[:] # copy
random.shuffle(order)
return order
def two_opt_swap(order: List[int]) -> List[int]:
"""Perform a 2-opt swap to generate a neighbor: reverse a segment between i and j."""
n = len(order)
if n < 4:
return order[:]
i = random.randint(0, n - 2)
j = random.randint(i + 1, n - 1)
new_order = order[:i] + list(reversed(order[i:j + 1])) + order[j + 1:]
return new_order
def random_swap(order: List[int]) -> List[int]:
"""Swap two nodes (smaller move than full 2-opt reversal)."""
n = len(order)
a, b = random.sample(range(n), 2)
new = order[:]
new[a], new[b] = new[b], new[a]
return new
def neighbor(order: List[int]) -> List[int]:
# Mix of 2-opt and swap for variety
if random.random() < 0.6:
return two_opt_swap(order)
else:
return random_swap(order)
def default_temperature(initial_temp: float, step: int, decay: float = 0.995) -> float:
"""Geometric cooling schedule."""
return initial_temp * (decay ** step)
def simulated_annealing(graph: Graph,
initial_temp: float = 10.0,
decay: float = 0.995,
max_iters: int = 20000,
max_no_improve: int = 2000,
closed: bool = True,
seed: Optional[int] = None) -> Tuple[List[int], float, bool]:
"""Run simulated annealing to find a Hamiltonian cycle (if closed=True) or path.
Returns: (best_order, best_cost, found_hamiltonian_cycle_bool)
"""
if seed is not None:
random.seed(seed)
nodes = list(graph.keys())
if len(nodes) == 0:
return [], 0.0, False
current = random_initial_solution(nodes)
current_cost = path_cost(current, graph, closed=closed)
best = current[:]
best_cost = current_cost
start_time = time.time()
no_improve = 0
for it in range(max_iters):
T = default_temperature(initial_temp, it, decay)
if T < 1e-8:
break
cand = neighbor(current)
cand_cost = path_cost(cand, graph, closed=closed)
delta = cand_cost - current_cost
accept = False
if cand_cost < current_cost:
accept = True
else:
# Metropolis criterion
if random.random() < math.exp(-delta / T):
accept = True
if accept:
current = cand
current_cost = cand_cost
# Update best
if current_cost < best_cost:
best = current[:]
best_cost = current_cost
no_improve = 0
else:
no_improve += 1
else:
no_improve += 1
# Early stop if no improvement for a while
if no_improve >= max_no_improve:
break
elapsed = time.time() - start_time
found = False
if closed:
found = is_hamiltonian_cycle(best, graph)
else:
# For path: ensure edges between consecutive nodes exist
found = path_cost(best, graph, closed=False) < float('inf') and len(set(best)) == len(best)
# Return best found, cost and boolean indicating if it's a valid Hamiltonian
return best, best_cost, found
Utility helpers to create graphs
def complete_graph_from_positions(positions: Dict[int, Tuple[float, float]]) -> Graph:
graph: Graph = {}
nodes = list(positions.keys())
for i in nodes:
graph[i] = {}
for i in nodes:
xi, yi = positions[i]
for j in nodes:
if i == j:
continue
xj, yj = positions[j]
d = math.hypot(xi - xj, yi - yj)
graph[i][j] = d
return graph
def graph_from_edge_list(n: int, edges: List[Tuple[int, int, float]]) -> Graph:
graph: Graph = {i: {} for i in range(n)}
for a, b, w in edges:
graph[a][b] = w
graph[b][a] = w
return graph
Demo / example
if name == 'main':
# Example 1: small complete Euclidean graph (TSP-like). This always has a Hamiltonian cycle.
positions = {
0: (0, 0),
1: (1, 0),
2: (1, 1),
3: (0.2, 0.7),
4: (0.5, -0.2)
}
graph = complete_graph_from_positions(positions)
best, cost, found = simulated_annealing(graph,
initial_temp=5.0,
decay=0.999,
max_iters=50000,
max_no_improve=4000,
closed=True,
seed=42)
print('--- Demo: complete Euclidean graph ---')
print('Best order:', best)
print('Cost:', cost)
print('Is valid Hamiltonian cycle?', found)
# Example 2: sparse graph that may or may not have Hamiltonian cycle.
edges = [
(0, 1, 1.0),
(1, 2, 1.0),
(2, 3, 1.0),
(3, 4, 1.0),
(4, 0, 1.0), # completes the cycle
# add a diagonal to make more connectivity
(0, 2, 1.4),
(1, 3, 1.4)
]
sparse = graph_from_edge_list(5, edges)
best2, cost2, found2 = simulated_annealing(sparse,
initial_temp=2.0,
decay=0.998,
max_iters=20000,
max_no_improve=2000,
closed=True,
seed=7)
print('\n--- Demo: sparse graph ---')
print('Best order:', best2)
print('Cost:', cost2)
print('Is valid Hamiltonian cycle?', found2)
# If you want to adapt this for Hamiltonian PATH (not cycle), call with closed=False
print('\nTip: for Hamiltonian PATH use simulated_annealing(..., closed=False)')