Combinatorial Optimization: Path Enumeration Algorithm

組合せ最適化: アルゴリズム 1.1 パス列挙アルゴリズム

B.コルテ/J.フィーゲン 著「組合せ最適化 理論とアルゴリズム 第2版」の例を Python で実装してみる。

 

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	"""
	Combinatorial Optimization - B.Korte, J.Vygen
	Algorithm 1.1
	Path Enumeration Algorithm
	"""
	def back_track(n):
	"""Generate all permutations of 0 .. n-1"""
	# step 1: initialize
	p = range(n)
	yield p
	i = n - 2
	while i >= 0:
	# step 2: find 'k'
	aux = [False] * n
	for j in range(i):
	aux[p[j]] = True
	k = p[i] + 1
	while k < n and aux[k]:
	k += 1
	# step 3
	if k < n:
	p[i] = k
	if i == n - 1:
	yield p
	if i < n - 1:
	p[i + 1] = -1
	i += 1
	if k == n:
	i -= 1
	def minimum_path(points):
	def distance(p, q):
	return max(abs(p[0] - q[0]), abs(p[1] - q[1]))
	ret = None
	n = len(points)
	for p in back_track(n):
	x = sum(distance(points[p[i]], points[p[i + 1]]) for i in range(n - 1))
	if not ret or x < ret[0]:
	ret = (x, [points[i] for i in p])
	return ret
	if __name__ == '__main__':
	import itertools
	for x in back_track(4):
	print x
	print len(list(back_track(5)))
	# Using built-in function.
	for x in itertools.permutations(range(4)):
	print x
	print minimum_path([(1, 1), (5, 2), (1, 4), (3, 3), (4, 8), (2, 10)])

view raw a01_1_path_enumeration_algorithm.py hosted with ❤ by GitHub

output

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

[0, 1, 2, 3] [0, 1, 3, 2] [0, 2, 1, 3] [0, 2, 3, 1] [0, 3, 1, 2] [0, 3, 2, 1] [1, 0, 2, 3] [1, 0, 3, 2] [1, 2, 0, 3] [1, 2, 3, 0] [1, 3, 0, 2] [1, 3, 2, 0] [2, 0, 1, 3] [2, 0, 3, 1] [2, 1, 0, 3] [2, 1, 3, 0] [2, 3, 0, 1] [2, 3, 1, 0] [3, 0, 1, 2] [3, 0, 2, 1] [3, 1, 0, 2] [3, 1, 2, 0] [3, 2, 0, 1] [3, 2, 1, 0] 120 (0, 1, 2, 3) (0, 1, 3, 2) (0, 2, 1, 3) (0, 2, 3, 1) (0, 3, 1, 2) (0, 3, 2, 1) (1, 0, 2, 3) (1, 0, 3, 2) (1, 2, 0, 3) (1, 2, 3, 0) (1, 3, 0, 2) (1, 3, 2, 0) (2, 0, 1, 3) (2, 0, 3, 1) (2, 1, 0, 3) (2, 1, 3, 0) (2, 3, 0, 1) (2, 3, 1, 0) (3, 0, 1, 2) (3, 0, 2, 1) (3, 1, 0, 2) (3, 1, 2, 0) (3, 2, 0, 1) (3, 2, 1, 0) (13, [(5, 2), (3, 3), (1, 1), (1, 4), (4, 8), (2, 10)])