Lists/dictionaries/Lin-Kernighan
Duncan Smith
buzzard at contactbox.co.uk
Sun Sep 3 23:36:37 CEST 2000
k is a parameter denoting the number of possible permutations. So if k=1
I'm only considering the n-1 possible permutations of a tree. In that case
I can use a single list of costs with the indices corresponding to the node
labels. With k=2 I must consider the costs of the (n-1)^2 possible pairs of
permutations. In most cases this is the sum of the costs of the individual
permutations. But if the permuted nodes are adjacent they must be evaluated
as a pair. The general idea is to choose a value of k such that I can find
a good (low cost) solution in a reasonable time. My code for k=1 is below.
However, I'd like to come up with a solution that is easier to generalise to
k=2,3,4... If there's nothing reasonably obvious that I should be doing I
probably just need to keep working at it. Thanks.
def Lin_Kern(self):
cost_list = []
for x in range(0, len(self.ordering)):
if self.cliques[x].pointer == 'None' or
self.cliques[self.cliques[x].pointer].pointer == 'None':
cost_list.append('None') #should not be
permuted
else:
cost_list.append(DJT.perm_cost(self, x)) #index is node
id
while min(cost_list) < 0:
to_perm = cost_list.index(min(cost_list))
update_list = Set([to_perm, self.cliques[to_perm].pointer])
update_list = (update_list + self.cliques[to_perm].pointed +
self.cliques[self.cliques[to_perm].pointer].pointed).asList()
DJT.perm(self, to_perm)
for x in update_list:
cost_list[x] = DJT.perm_cost(self, x)
More information about the Python-list
mailing list