GAでTSP問題を解くときの超定番である、「ルート表現から順序条件に変換するアルゴリズム」と「順序表現からルート表現に変換するアルゴリズム (前記の逆変換)」をGolangで試してみた件

2021年2月14日

/*
GAでTSP問題を解くときの超定番である、
「ルート表現から順序条件に変換するアルゴリズム」と
「順序表現からルート表現に変換するアルゴリズム (前記の逆変換)」を
Golangで試してみた件
*/

package main

import "fmt"

func main() {

	// ルート表現から順序条件に変換するアルゴリズム

	var sliceA = []int{7, 8, 0, 4, 1, 6, 3, 9, 5, 2} // ルート表現
	var sliceB = []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	// 1111 var sliceC = [10]int{} // 順序条件が入るところ
	var sliceC = []int{} // 順序条件が入るところ

	// ルート表現から順列表現に変換
	for i := 0; i < len(sliceA); i++ {
		fmt.Printf("i: %v\n", i)
		for k := 0; k < len(sliceB); k++ {
			fmt.Printf("k: %v\n", k)
			if sliceA[i] == sliceB[k] {

				fmt.Printf("before Slice_A: %v\n", sliceA)
				fmt.Printf("before Slice_B: %v\n", sliceB)
				fmt.Printf("before Slice_C: %v\n", sliceC)

				// 1111 sliceC[i] = k
				sliceC = append(sliceC, k)
				sliceB = append(sliceB[:k], sliceB[k+1:]...) // k番目の要素を削除

				fmt.Printf("after Slice_A: %v\n", sliceA)
				fmt.Printf("after Slice_B: %v\n", sliceB)
				fmt.Printf("after Slice_C: %v\n", sliceC)
				fmt.Printf("\n")
			}
		}
	}

	fmt.Printf("=======\n")

	// 順序表現からルート表現に変換するアルゴリズム (上記の逆変換)

	sliceA = []int{} // 今からルート表現を入れるところ
	sliceB = []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	// sliceCには、すでに順序表現が入っている

	for i := 0; i < len(sliceC); i++ {
		fmt.Printf("i: %v\n", i)
		k := sliceC[i]
		fmt.Printf("k: %v\n", k)
		j := sliceB[k]
		fmt.Printf("j: %v\n", j)

		fmt.Printf("before Slice_C: %v\n", sliceC)
		fmt.Printf("before Slice_B: %v\n", sliceB)
		fmt.Printf("before Slice_A: %v\n", sliceA)

		sliceA = append(sliceA, j)
		sliceB = append(sliceB[:k], sliceB[k+1:]...) // k番目の要素を削除

		fmt.Printf("after Slice_C: %v\n", sliceC)
		fmt.Printf("after Slice_B: %v\n", sliceB)
		fmt.Printf("after Slice_A: %v\n", sliceA)
	}
	fmt.Printf("\n")
}