类似于旅行商的优化问题-需要更好的启发式

Question

我有一个优化问题，我正在寻找一种算法，该算法的性能要比单纯的方法好。

问题

考虑一个图，，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)

我知道我可以优化一些东西，例如使最后一个方法对称，依此类推，但是基本思想仍然不是很聪明。是否有一个聪明的算法可以优化状态在图形上的移动方式，但仍然可以完成所有访问。