我有一个优化问题,我正在寻找一种算法,该算法的性能要比单纯的方法好。
问题
考虑一个图,,G(N, E)
其中N
是节点E
集,是边集。每个节点n_i
在N
具有相关联的状态s_i
。我使用了字典D
来存储它,其中节点作为键,相应的状态作为值。相邻节点可以使用交换策略交换状态。具体来说,交换策略定义为
def swap(G, D, n_i, n_j): if n_i not in neighbors(G, n_j): print('Cannot swap between disconnected nodes') else: s_i = D[n_i] s_j = D[n_j] D[n_i] = s_j D[n_j] = s_i return D
每个状态现在必须以给定的顺序“访问”其他状态的列表,其中访问意味着这两个状态必须在上的任意一对相邻节点上G(N, E)
。例如s_1
必须访问[s_3, s_5, s_2]
,s_2
必须访问[s_1, s_3]
,s_3
必须访问[s_1, s_2, s_4]
等。访问顺序必须保留。但是,允许状态位于相邻节点上,而无需将其标记为访问。例如,如果s_1
开始于s_5
,则它必须首先成为,然后s_3
将该访问标记为已完成,然后s_5
再次成为。访问者列表是这样的,如果s_i
必须访问s_j
,那也意味着s_j
必须访问,s_i
即一切都是自洽的。
典型尺寸
该图通常大约有20-30个节点,每个节点通常连接到2-4个其他节点。访问列表原则上没有长度限制,但实际上不超过10。
目标
目标是完成访问列表,同时尽量减少交换操作的总数。什么是有效解决此问题的算法/启发式方法?
我天真的解决方案
我当前的算法可以做到最简单的事情。我首先(0,0)
根据以下功能查看访问的哪个目的地,即两个州在访问其他任何人之前必须先进行访问。
def interaction_priority(s1, s2): if s2 in visitors_of_s1: b = visitors_of_s1.index(s2) a = visitors_of_s2.index(s1) return (a, b)
对于这些状态,我G
使用networx
函数获取当前节点并找到这些节点之间的最短路径。我执行交换,直到它们相邻。让我们假设返回先前的功能(0,0)
的s_1 and s_3
。然后我发现当前节点之间的最短路径s_1
和s_3
inv_D = {s : n for n, s in D.items()} #Invert the dictionary of nodes and states def get_shortest_path(s1, s3): n1 = inv_D[s1] n3 = inv_D[s3] path_nodes = get_shortest_path(G, n1, n3) return path_nodes
现在,我沿着这条路径执行交换
if len(path_nodes)> 0: for i in path_nodes: D = swap(G, D, n1, i) visitors_of_s1.remove(s3) visitors_of_s3.remove(s1)
我知道我可以优化一些东西,例如使最后一个方法对称,依此类推,但是基本思想仍然不是很聪明。是否有一个聪明的算法可以优化状态在图形上的移动方式,但仍然可以完成所有访问。