HillClimbingSolverGO.go

package main

import (
	"fmt"
	"math"
	"math/rand"
	"reflect"
	"time"
)

type HillClimbingSolver interface {
	New() HillClimbingSolver

	Better() HillClimbingSolver

	IsOptimal() bool
}

func SolveWithHillClimbing(h HillClimbingSolver) HillClimbingSolver {
	current := h.New()

	for {
		for i := 0; i < 100; i++ {
			successor := current.Better()
			// Found better successor
			if !reflect.DeepEqual(successor, current) {
				current = successor
			} else {
				break
			}
		}
		if current.IsOptimal() {
			return current
		}
	}
}

type NQ struct {
	ChessBoard []int
}

type Position struct {
	x float64
	y float64
}

type TSP struct {
	CityMap []Position
	Tour    []Position
}

func InitNQ() NQ {
	q := NQ{ChessBoard: make([]int, 5)}

	for i := 0; i < 5; i++ {
		q.ChessBoard[i] = i
	}

	q.Shuffle()
	q.Better()

	return q
}

func InitTSP() TSP {
	s := TSP{CityMap: make([]Position, 5), Tour: make([]Position, 5)}

	for i := 0; i < 5; i++ {
		position := Position{rand.Float64(), rand.Float64()}
		s.CityMap[i] = position
		s.Tour[i] = position
	}

	return s
}

func (q NQ) New() HillClimbingSolver {
	return InitNQ()
}

func (s TSP) New() HillClimbingSolver {
	return InitTSP()
}

func (q *NQ) Size() int {
	return len(q.ChessBoard)
}

func (s *TSP) Size() int {
	return len(s.CityMap)
}

func (q *NQ) duplicate() NQ {
	newBoard := make([]int, len(q.ChessBoard))

	for i := 0; i < len(q.ChessBoard); i++ {
		newBoard[i] = q.ChessBoard[i]
	}

	newNQ := NQ{ChessBoard: newBoard}
	return newNQ
}

func (s *TSP) duplicate() TSP {
	newCityMap := make([]Position, len(s.Tour))
	newTour := make([]Position, len(s.Tour))

	for i := 0; i < len(s.CityMap); i++ {
		newCityMap[i] = s.CityMap[i]
	}
	for i := 0; i < len(s.Tour); i++ {
		newTour[i] = s.Tour[i]
	}

	newTSP := TSP{CityMap: newCityMap, Tour: newTour}
	return newTSP
}

func randInt(max int) int {
	return rand.Intn(max)
}

func (q *NQ) Climb() {
	source := randInt(q.Size())
	target := randInt(q.Size())

	q.ChessBoard[source], q.ChessBoard[target] = q.ChessBoard[target], q.ChessBoard[source]
}

func (s *TSP) Climb() {
	source := randInt(s.Size())
	target := randInt(s.Size())

	s.Tour[source], s.Tour[target] = s.Tour[target], s.Tour[source]
}

func (q *NQ) Shuffle() {
	for i := 0; i < q.Size(); i++ {
		q.Climb()
	}
}

func (q *NQ) isValid(source int, target int) bool {
	return !(q.ChessBoard[source]-source == q.ChessBoard[target]-target ||
		q.ChessBoard[source]+source == q.ChessBoard[target]+target ||
		q.ChessBoard[source] == q.ChessBoard[target])
}

func (q *NQ) Loss() int {
	loss := 0

	for i := 0; i < len(q.ChessBoard); i++ {
		for j := i + 1; j < len(q.ChessBoard); j++ {
			if q.isValid(i, j) {
				loss++
			}
		}
	}
	return loss
}

func (s *TSP) Loss() float64 {
	loss := 0.0

	for i := 0; i < len(s.Tour)-1; i++ {

		distanceSquare := math.Pow(s.CityMap[i].x-s.CityMap[i+1].x, 2.0) + math.Pow(s.CityMap[i].y-s.CityMap[i+1].y, 2.0)

		loss += math.Sqrt(distanceSquare)
	}
	return loss
}

func (q NQ) IsOptimal() bool {
	return q.Loss() == 0
}

func (s TSP) IsOptimal() bool {
	return int(s.Loss()) <= s.Size()/2
}

func (q NQ) nextState() NQ {
	listSize := len(q.ChessBoard) * 2
	currentLoss := q.Loss()

	for i := 0; i < listSize; i++ {
		newQ := q.duplicate()
		newQ.Climb()
		fmt.Printf("loss:\n%v\n", currentLoss)
		fmt.Printf("state:\n%v\n", newQ.ChessBoard)
		if newQ.Loss() <= currentLoss {
			return newQ
		}
	}
	return q
}

func (s TSP) nextState() TSP {
	currentLoss := s.Loss()

	newS := s.duplicate()
	newS.Climb()
	fmt.Printf("loss:\n%v\n", currentLoss)
	fmt.Printf("state:\n%v\n", newS.Tour)
	if newS.Loss() <= currentLoss {
		return newS
	}
	return s
}

func (q NQ) Better() HillClimbingSolver {
	return q.nextState()
}

func (s TSP) Better() HillClimbingSolver {
	return s.nextState()
}

func main() {
	rand.Seed(time.Now().UTC().UnixNano())

	q := InitNQ()

	qInterface := SolveWithHillClimbing(q)
	qResult := NQ(qInterface.(NQ))

	fmt.Printf("Final board:\n%v\n", qResult)
	fmt.Printf("final loss:\n%v\n", qResult.Loss())

	s := InitTSP()

	sInterface := SolveWithHillClimbing(s)
	sResult := TSP(sInterface.(TSP))

	fmt.Printf("final tour:\n%v\n", sResult.Tour)
	fmt.Printf("final loss:\n%v\n", sResult.Loss())
}