666 lines
23 KiB
Python
666 lines
23 KiB
Python
def graph_coloring_v8(adj_matrix):
|
||
"""高级混合图着色算法
|
||
结合多种算法优点，使用数学优化和多阶段策略，尽可能减少所需颜色数
|
||
1. 图分解与重组
|
||
2. 多阶段混合策略
|
||
3. 高级预处理与结构识别
|
||
4. 迭代颜色减少
|
||
5. 自适应参数调整
|
||
"""
|
||
import numpy as np
|
||
import random
|
||
import heapq
|
||
import time
|
||
from collections import defaultdict, deque
|
||
from itertools import combinations
|
||
|
||
start_time = time.time()
|
||
max_time = 60 # 最大运行时间(秒)
|
||
|
||
n = adj_matrix.shape[0]
|
||
best_coloring = np.full(n, -1)
|
||
best_color_count = n
|
||
|
||
# 构建邻接表以加速计算
|
||
adj_lists = [np.where(adj_matrix[i] == 1)[0] for i in range(n)]
|
||
|
||
# 计算顶点度数
|
||
degrees = np.sum(adj_matrix, axis=1)
|
||
max_degree = np.max(degrees)
|
||
|
||
# 1. 高级预处理与结构识别
|
||
|
||
def find_max_clique():
|
||
"""使用Bron-Kerbosch算法寻找最大团"""
|
||
def bron_kerbosch(r, p, x, max_clique):
|
||
if len(p) == 0 and len(x) == 0:
|
||
if len(r) > len(max_clique[0]):
|
||
max_clique[0] = r.copy()
|
||
return
|
||
|
||
# 选择枢轴点以优化分支
|
||
if p:
|
||
pivot = max(p, key=lambda v: len(set(adj_lists[v]) & p))
|
||
p_minus_n_pivot = p - set(adj_lists[pivot])
|
||
else:
|
||
p_minus_n_pivot = p
|
||
|
||
for v in list(p_minus_n_pivot):
|
||
neighbors_v = set(adj_lists[v])
|
||
bron_kerbosch(r | {v}, p & neighbors_v, x & neighbors_v, max_clique)
|
||
p.remove(v)
|
||
x.add(v)
|
||
|
||
# 提前终止条件
|
||
if time.time() - start_time > max_time / 10:
|
||
return
|
||
|
||
max_clique = [set()]
|
||
vertices = set(range(n))
|
||
|
||
# 使用度数排序启发式加速
|
||
sorted_vertices = sorted(range(n), key=lambda v: degrees[v], reverse=True)
|
||
for v in sorted_vertices[:min(100, n)]: # 限制初始顶点数量
|
||
if time.time() - start_time > max_time / 10:
|
||
break
|
||
r = {v}
|
||
p = set(adj_lists[v]) & vertices
|
||
x = vertices - p - r
|
||
bron_kerbosch(r, p, x, max_clique)
|
||
|
||
return list(max_clique[0])
|
||
|
||
def identify_independent_sets():
|
||
"""识别大的独立集"""
|
||
independent_sets = []
|
||
remaining = set(range(n))
|
||
|
||
while remaining and time.time() - start_time < max_time / 10:
|
||
# 选择度数最小的顶点开始
|
||
start_vertex = min(remaining, key=lambda v: degrees[v])
|
||
ind_set = {start_vertex}
|
||
candidates = remaining - {start_vertex} - set(adj_lists[start_vertex])
|
||
|
||
# 贪心扩展独立集
|
||
while candidates:
|
||
# 选择度数最小的顶点加入
|
||
v = min(candidates, key=lambda v: degrees[v])
|
||
ind_set.add(v)
|
||
candidates -= {v} | set(adj_lists[v])
|
||
|
||
independent_sets.append(ind_set)
|
||
remaining -= ind_set
|
||
|
||
return independent_sets
|
||
|
||
def find_bipartite_subgraphs():
|
||
"""识别二分图子结构"""
|
||
bipartite_subgraphs = []
|
||
visited = np.zeros(n, dtype=bool)
|
||
|
||
def bfs_bipartite(start):
|
||
queue = deque([(start, 0)]) # (vertex, color)
|
||
coloring = {start: 0}
|
||
component = {start}
|
||
|
||
while queue and time.time() - start_time < max_time / 10:
|
||
v, color = queue.popleft()
|
||
next_color = 1 - color
|
||
|
||
for u in adj_lists[v]:
|
||
if u not in coloring:
|
||
coloring[u] = next_color
|
||
component.add(u)
|
||
queue.append((u, next_color))
|
||
elif coloring[u] == color: # 冲突，不是二分图
|
||
return None
|
||
|
||
# 分离两个部分
|
||
part0 = {v for v, c in coloring.items() if c == 0}
|
||
part1 = {v for v, c in coloring.items() if c == 1}
|
||
return (part0, part1)
|
||
|
||
# 寻找所有连通的二分子图
|
||
for i in range(n):
|
||
if not visited[i] and time.time() - start_time < max_time / 10:
|
||
result = bfs_bipartite(i)
|
||
if result:
|
||
part0, part1 = result
|
||
bipartite_subgraphs.append((part0, part1))
|
||
for v in part0 | part1:
|
||
visited[v] = True
|
||
|
||
return bipartite_subgraphs
|
||
|
||
# 2. 图分解技术
|
||
|
||
def decompose_graph():
|
||
"""将图分解为更易处理的组件"""
|
||
# 寻找割点和桥
|
||
articulation_points = find_articulation_points()
|
||
|
||
# 移除割点后的连通分量
|
||
components = []
|
||
visited = np.zeros(n, dtype=bool)
|
||
|
||
def dfs(v, component):
|
||
visited[v] = True
|
||
component.add(v)
|
||
for u in adj_lists[v]:
|
||
if not visited[u] and u not in articulation_points:
|
||
dfs(u, component)
|
||
|
||
# 找出所有连通分量
|
||
for i in range(n):
|
||
if not visited[i] and i not in articulation_points:
|
||
component = set()
|
||
dfs(i, component)
|
||
if component:
|
||
components.append(component)
|
||
|
||
# 如果没有找到有效分解，返回整个图
|
||
if not components:
|
||
return [set(range(n))]
|
||
|
||
return components
|
||
|
||
def find_articulation_points():
|
||
"""使用Tarjan算法寻找割点"""
|
||
disc = [-1] * n
|
||
low = [-1] * n
|
||
visited = [False] * n
|
||
ap = set()
|
||
timer = [0]
|
||
|
||
def dfs(u, parent):
|
||
children = 0
|
||
visited[u] = True
|
||
disc[u] = low[u] = timer[0]
|
||
timer[0] += 1
|
||
|
||
for v in adj_lists[u]:
|
||
if not visited[v]:
|
||
children += 1
|
||
dfs(v, u)
|
||
low[u] = min(low[u], low[v])
|
||
|
||
# 检查u是否为割点
|
||
if parent != -1 and low[v] >= disc[u]:
|
||
ap.add(u)
|
||
elif v != parent:
|
||
low[u] = min(low[u], disc[v])
|
||
|
||
# 如果u是根节点且有多个子节点
|
||
if parent == -1 and children > 1:
|
||
ap.add(u)
|
||
|
||
for i in range(n):
|
||
if not visited[i]:
|
||
dfs(i, -1)
|
||
|
||
return ap
|
||
|
||
# 3. 核心着色算法
|
||
|
||
def dsatur_coloring(vertices=None, max_colors=None):
|
||
"""增强版DSATUR算法"""
|
||
if vertices is None:
|
||
vertices = set(range(n))
|
||
if max_colors is None:
|
||
max_colors = n
|
||
|
||
n_sub = len(vertices)
|
||
vertices_list = list(vertices)
|
||
vertex_map = {v: i for i, v in enumerate(vertices_list)}
|
||
reverse_map = {i: v for v, i in vertex_map.items()}
|
||
|
||
# 创建子图的邻接表
|
||
sub_adj_lists = [[] for _ in range(n_sub)]
|
||
for i, v in enumerate(vertices_list):
|
||
for u in adj_lists[v]:
|
||
if u in vertex_map:
|
||
sub_adj_lists[i].append(vertex_map[u])
|
||
|
||
colors = np.full(n_sub, -1)
|
||
saturation = np.zeros(n_sub, dtype=int)
|
||
adj_colors = [set() for _ in range(n_sub)]
|
||
|
||
# 计算子图中的度数
|
||
sub_degrees = np.zeros(n_sub, dtype=int)
|
||
for i in range(n_sub):
|
||
sub_degrees[i] = len(sub_adj_lists[i])
|
||
|
||
# 初始化优先队列 (-饱和度, -度数, 顶点ID)
|
||
vertex_heap = [(0, -sub_degrees[i], i) for i in range(n_sub)]
|
||
heapq.heapify(vertex_heap)
|
||
|
||
colored_count = 0
|
||
colored_vertices = np.zeros(n_sub, dtype=bool)
|
||
|
||
while colored_count < n_sub and vertex_heap:
|
||
# 获取优先级最高的未着色顶点
|
||
_, _, vertex = heapq.heappop(vertex_heap)
|
||
|
||
# 如果顶点已着色，跳过
|
||
if colored_vertices[vertex]:
|
||
continue
|
||
|
||
# 计算可用颜色
|
||
used = [False] * max_colors
|
||
for u in sub_adj_lists[vertex]:
|
||
if colors[u] != -1:
|
||
used[colors[u]] = True
|
||
|
||
# 找到最小可用颜色
|
||
color = -1
|
||
for c in range(max_colors):
|
||
if not used[c]:
|
||
color = c
|
||
break
|
||
|
||
if color == -1:
|
||
# 没有可用颜色
|
||
return None
|
||
|
||
colors[vertex] = color
|
||
colored_vertices[vertex] = True
|
||
colored_count += 1
|
||
|
||
# 更新邻居的饱和度
|
||
for u in sub_adj_lists[vertex]:
|
||
if not colored_vertices[u]:
|
||
if color not in adj_colors[u]:
|
||
adj_colors[u].add(color)
|
||
saturation[u] += 1
|
||
# 重新入堆以更新优先级
|
||
heapq.heappush(vertex_heap, (-saturation[u], -sub_degrees[u], u))
|
||
|
||
# 将子图着色映射回原图
|
||
result = np.full(n, -1)
|
||
for i in range(n_sub):
|
||
result[reverse_map[i]] = colors[i]
|
||
|
||
return result
|
||
|
||
def kempe_chain_interchange(coloring, v, c1, c2):
|
||
"""Kempe链交换"""
|
||
if coloring[v] != c1 or c1 == c2:
|
||
return False
|
||
|
||
# 保存原始着色
|
||
original = coloring.copy()
|
||
|
||
# 构建Kempe链
|
||
chain = {v}
|
||
queue = deque([v])
|
||
|
||
while queue:
|
||
current = queue.popleft()
|
||
for u in adj_lists[current]:
|
||
if u not in chain and coloring[u] in (c1, c2):
|
||
chain.add(u)
|
||
queue.append(u)
|
||
|
||
# 交换颜色
|
||
for u in chain:
|
||
if coloring[u] == c1:
|
||
coloring[u] = c2
|
||
elif coloring[u] == c2:
|
||
coloring[u] = c1
|
||
|
||
# 验证交换后的合法性
|
||
for u in range(n):
|
||
for v in adj_lists[u]:
|
||
if coloring[u] == coloring[v] and coloring[u] != -1:
|
||
# 恢复原始着色
|
||
coloring[:] = original
|
||
return False
|
||
|
||
return True
|
||
|
||
def iterated_greedy(initial_coloring=None, iterations=100):
|
||
"""迭代贪心算法"""
|
||
if initial_coloring is None:
|
||
# 使用DSATUR生成初始解
|
||
coloring = dsatur_coloring()
|
||
else:
|
||
coloring = initial_coloring.copy()
|
||
|
||
best = coloring.copy()
|
||
best_colors_used = len(set(coloring))
|
||
|
||
for _ in range(iterations):
|
||
if time.time() - start_time > max_time:
|
||
break
|
||
|
||
# 随机选择顶点顺序
|
||
vertices = list(range(n))
|
||
random.shuffle(vertices)
|
||
|
||
# 临时移除顶点着色
|
||
temp_coloring = coloring.copy()
|
||
for v in vertices:
|
||
temp_coloring[v] = -1
|
||
|
||
# 重新着色
|
||
for v in vertices:
|
||
used = [False] * n
|
||
for u in adj_lists[v]:
|
||
if temp_coloring[u] != -1:
|
||
used[temp_coloring[u]] = True
|
||
|
||
# 找到最小可用颜色
|
||
for c in range(n):
|
||
if not used[c]:
|
||
temp_coloring[v] = c
|
||
break
|
||
|
||
# 更新最佳解
|
||
colors_used = len(set(temp_coloring))
|
||
if colors_used < best_colors_used:
|
||
best = temp_coloring.copy()
|
||
best_colors_used = colors_used
|
||
coloring = temp_coloring.copy()
|
||
elif random.random() < 0.3: # 有时接受较差解以跳出局部最优
|
||
coloring = temp_coloring.copy()
|
||
|
||
return best
|
||
|
||
def tabu_search(initial_coloring, max_iterations=1000):
|
||
"""禁忌搜索优化"""
|
||
coloring = initial_coloring.copy()
|
||
best_coloring = coloring.copy()
|
||
best_colors_used = len(set(coloring))
|
||
|
||
# 初始化禁忌表
|
||
tabu_list = {}
|
||
tabu_tenure = 10
|
||
iteration = 0
|
||
|
||
# 计算冲突
|
||
def count_conflicts():
|
||
conflicts = 0
|
||
for v in range(n):
|
||
for u in adj_lists[v]:
|
||
if u > v and coloring[u] == coloring[v]:
|
||
conflicts += 1
|
||
return conflicts
|
||
|
||
# 找到最佳移动
|
||
def find_best_move():
|
||
best_delta = float('inf')
|
||
best_moves = []
|
||
|
||
for v in range(n):
|
||
current_color = coloring[v]
|
||
|
||
# 计算当前冲突
|
||
current_conflicts = sum(1 for u in adj_lists[v] if coloring[u] == current_color)
|
||
|
||
# 尝试所有可能的颜色
|
||
for c in range(best_colors_used + 1):
|
||
if c != current_color:
|
||
# 计算新冲突
|
||
new_conflicts = sum(1 for u in adj_lists[v] if coloring[u] == c)
|
||
delta = new_conflicts - current_conflicts
|
||
|
||
# 检查禁忌状态
|
||
move_key = (v, c)
|
||
is_tabu = move_key in tabu_list and iteration < tabu_list[move_key]
|
||
|
||
# 特赦准则：如果移动导致新的最佳解
|
||
if is_tabu and not (new_conflicts == 0 and c < best_colors_used):
|
||
continue
|
||
|
||
if delta <= best_delta:
|
||
if delta < best_delta:
|
||
best_moves = []
|
||
best_delta = delta
|
||
best_moves.append((v, c))
|
||
|
||
if not best_moves:
|
||
return None, None
|
||
|
||
# 随机选择一个最佳移动
|
||
v, c = random.choice(best_moves)
|
||
return v, c
|
||
|
||
# 主循环
|
||
while iteration < max_iterations and time.time() - start_time < max_time:
|
||
v, c = find_best_move()
|
||
if v is None:
|
||
break
|
||
|
||
# 执行移动
|
||
old_color = coloring[v]
|
||
coloring[v] = c
|
||
|
||
# 更新禁忌表
|
||
tabu_list[(v, old_color)] = iteration + tabu_tenure
|
||
|
||
# 更新最佳解
|
||
colors_used = len(set(coloring))
|
||
if colors_used < best_colors_used:
|
||
best_coloring = coloring.copy()
|
||
best_colors_used = colors_used
|
||
|
||
iteration += 1
|
||
|
||
return best_coloring
|
||
|
||
# 4. 多阶段混合策略
|
||
|
||
def hybrid_coloring():
|
||
"""多阶段混合着色策略"""
|
||
# 阶段1: 预处理和结构识别
|
||
max_clique = find_max_clique()
|
||
clique_size = len(max_clique)
|
||
|
||
# 阶段2: 初始解生成
|
||
# 使用DSATUR生成初始解
|
||
initial_coloring = dsatur_coloring()
|
||
if initial_coloring is None:
|
||
initial_coloring = np.zeros(n, dtype=int)
|
||
for i in range(n):
|
||
used = set()
|
||
for j in adj_lists[i]:
|
||
if j < i:
|
||
used.add(initial_coloring[j])
|
||
for c in range(n):
|
||
if c not in used:
|
||
initial_coloring[i] = c
|
||
break
|
||
|
||
# 阶段3: 迭代优化
|
||
# 应用迭代贪心
|
||
improved_coloring = iterated_greedy(initial_coloring, iterations=50)
|
||
colors_used = len(set(improved_coloring))
|
||
|
||
# 修复：使用nonlocal关键字声明best_color_count是外部变量
|
||
nonlocal best_color_count
|
||
|
||
if colors_used < best_color_count:
|
||
best_coloring[:] = improved_coloring
|
||
best_color_count = colors_used
|
||
|
||
# 阶段4: 禁忌搜索优化
|
||
if time.time() - start_time < max_time * 0.7:
|
||
tabu_coloring = tabu_search(improved_coloring, max_iterations=500)
|
||
tabu_colors_used = len(set(tabu_coloring))
|
||
|
||
if tabu_colors_used < best_color_count:
|
||
best_coloring[:] = tabu_coloring
|
||
best_color_count = tabu_colors_used
|
||
|
||
# 阶段5: 颜色合并
|
||
if time.time() - start_time < max_time * 0.9:
|
||
merged_coloring = color_merging(best_coloring.copy())
|
||
merged_colors_used = len(set(merged_coloring))
|
||
|
||
if merged_colors_used < best_color_count:
|
||
best_coloring[:] = merged_coloring
|
||
best_color_count = merged_colors_used
|
||
|
||
def color_merging(coloring):
|
||
"""尝试合并颜色类"""
|
||
colors_used = sorted(set(coloring))
|
||
|
||
# 尝试合并每对颜色
|
||
for c1, c2 in combinations(colors_used, 2):
|
||
# 检查是否可以合并
|
||
can_merge = True
|
||
vertices_with_c1 = np.where(coloring == c1)[0]
|
||
|
||
for v in vertices_with_c1:
|
||
for u in adj_lists[v]:
|
||
if coloring[u] == c2:
|
||
can_merge = False
|
||
break
|
||
if not can_merge:
|
||
break
|
||
|
||
if can_merge:
|
||
# 合并颜色
|
||
coloring[vertices_with_c1] = c2
|
||
|
||
# 递归尝试更多合并
|
||
return color_merging(coloring)
|
||
|
||
# 重新映射颜色以确保连续
|
||
color_map = {}
|
||
new_coloring = np.zeros_like(coloring)
|
||
next_color = 0
|
||
|
||
for i, c in enumerate(coloring):
|
||
if c not in color_map:
|
||
color_map[c] = next_color
|
||
next_color += 1
|
||
new_coloring[i] = color_map[c]
|
||
|
||
return new_coloring
|
||
|
||
# 5. 图分解与重组
|
||
|
||
def solve_by_decomposition():
|
||
"""通过图分解求解"""
|
||
# 分解图
|
||
components = decompose_graph()
|
||
|
||
if len(components) > 1:
|
||
# 分别处理每个组件
|
||
component_colorings = []
|
||
max_colors = 0
|
||
|
||
for component in components:
|
||
# 为组件着色
|
||
comp_coloring = dsatur_coloring(component)
|
||
|
||
# 重新映射颜色
|
||
color_map = {}
|
||
for v in component:
|
||
if comp_coloring[v] not in color_map:
|
||
color_map[comp_coloring[v]] = len(color_map)
|
||
comp_coloring[v] = color_map[comp_coloring[v]]
|
||
|
||
component_colorings.append((component, comp_coloring))
|
||
max_colors = max(max_colors, max(comp_coloring[list(component)]) + 1)
|
||
|
||
# 重组解
|
||
combined_coloring = np.full(n, -1)
|
||
for component, comp_coloring in component_colorings:
|
||
for v in component:
|
||
combined_coloring[v] = comp_coloring[v]
|
||
|
||
return combined_coloring
|
||
else:
|
||
return None
|
||
|
||
# 6. 迭代颜色减少
|
||
|
||
def iterative_color_reduction(coloring):
|
||
"""迭代尝试减少颜色数"""
|
||
colors_used = len(set(coloring))
|
||
|
||
# 如果颜色数已经等于最大团大小，无法进一步减少
|
||
max_clique = find_max_clique()
|
||
if colors_used <= len(max_clique):
|
||
return coloring
|
||
|
||
# 尝试减少一种颜色
|
||
target_colors = colors_used - 1
|
||
|
||
# 重新映射颜色以确保连续
|
||
color_map = {}
|
||
for i, c in enumerate(coloring):
|
||
if c not in color_map:
|
||
color_map[c] = len(color_map)
|
||
coloring[i] = color_map[c]
|
||
|
||
# 尝试移除最高颜色
|
||
highest_color = target_colors
|
||
vertices_with_highest = np.where(coloring == highest_color)[0]
|
||
|
||
# 临时移除这些顶点的颜色
|
||
temp_coloring = coloring.copy()
|
||
temp_coloring[vertices_with_highest] = -1
|
||
|
||
# 尝试用更少的颜色重新着色
|
||
for v in vertices_with_highest:
|
||
used = [False] * target_colors
|
||
for u in adj_lists[v]:
|
||
if temp_coloring[u] != -1:
|
||
used[temp_coloring[u]] = True
|
||
|
||
# 寻找可用颜色
|
||
available_color = -1
|
||
for c in range(target_colors):
|
||
if not used[c]:
|
||
available_color = c
|
||
break
|
||
|
||
if available_color != -1:
|
||
temp_coloring[v] = available_color
|
||
else:
|
||
# 无法减少颜色
|
||
return coloring
|
||
|
||
# 递归尝试进一步减少
|
||
if time.time() - start_time < max_time * 0.95:
|
||
return iterative_color_reduction(temp_coloring)
|
||
else:
|
||
return temp_coloring
|
||
|
||
# 主算法流程
|
||
|
||
# 1. 尝试通过图分解求解
|
||
decomp_coloring = solve_by_decomposition()
|
||
if decomp_coloring is not None:
|
||
decomp_colors_used = len(set(decomp_coloring))
|
||
if decomp_colors_used < best_color_count:
|
||
best_coloring = decomp_coloring
|
||
best_color_count = decomp_colors_used
|
||
|
||
# 2. 应用多阶段混合策略
|
||
hybrid_coloring()
|
||
|
||
# 3. 迭代颜色减少
|
||
if time.time() - start_time < max_time * 0.95:
|
||
reduced_coloring = iterative_color_reduction(best_coloring.copy())
|
||
reduced_colors_used = len(set(reduced_coloring))
|
||
|
||
if reduced_colors_used < best_color_count:
|
||
best_coloring = reduced_coloring
|
||
best_color_count = reduced_colors_used
|
||
|
||
# 确保颜色编号连续且从0开始
|
||
color_map = {}
|
||
final_coloring = np.zeros_like(best_coloring)
|
||
next_color = 0
|
||
|
||
for i, c in enumerate(best_coloring):
|
||
if c not in color_map:
|
||
color_map[c] = next_color
|
||
next_color += 1
|
||
final_coloring[i] = color_map[c]
|
||
|
||
return final_coloring |