贪婪搜索是P=NP之TSP问题的近似解

    Where there is a will there's a way

package v1

import (
	"math/rand"
	"time"
)

type City struct {
	Coordinates
	Name     string
	Distance float64
}

// Coordinates 经纬度
type Coordinates struct {
	Latitude  float64 `yaml:"latitude"`  //纬度
	Longitude float64 `yaml:"longitude"` //经度
}

// USCities 包含美国各州不同区域的至少 50 个城市
var USCities = []City{
	City{
		Name: "New York",

		Coordinates: Coordinates{
			Latitude:  40.7128,
			Longitude: -74.0060,
		},
		Distance: 0,
	},
	City{
		Name: "Los Angeles",

		Coordinates: Coordinates{
			Latitude:  34.0522,
			Longitude: -118.2437,
		},
		Distance: 0,
	},
	City{
		Name: "Chicago",

		Coordinates: Coordinates{
			Latitude:  41.8781,
			Longitude: -87.6298,
		},
		Distance: 0,
	},
	City{
		Name: "Houston",

		Coordinates: Coordinates{
			Latitude:  29.7604,
			Longitude: -95.3698,
		},
		Distance: 0,
	},
	City{
		Name: "Phoenix",

		Coordinates: Coordinates{
			Latitude:  33.4484,
			Longitude: -112.0740,
		},
		Distance: 0,
	},
	City{
		Name: "Philadelphia",

		Coordinates: Coordinates{
			Latitude:  39.9526,
			Longitude: -75.1652,
		},
		Distance: 0,
	},
	City{
		Name: "San Antonio",

		Coordinates: Coordinates{
			Latitude:  29.4241,
			Longitude: -98.4936,
		},
		Distance: 0,
	},
	City{
		Name: "San Diego",

		Coordinates: Coordinates{
			Latitude:  32.7157,
			Longitude: -117.1611,
		},
		Distance: 0,
	},
	City{
		Name: "Dallas",

		Coordinates: Coordinates{
			Latitude:  32.7767,
			Longitude: -96.7970,
		},
		Distance: 0,
	},
	City{
		Name: "San Jose",

		Coordinates: Coordinates{
			Latitude:  37.3382,
			Longitude: -121.8863,
		},
		Distance: 0,
	},
	City{
		Name: "Austin",

		Coordinates: Coordinates{
			Latitude:  30.2672,
			Longitude: -97.7431,
		},
		Distance: 0,
	},
	City{
		Name: "Jacksonville",

		Coordinates: Coordinates{
			Latitude:  30.3322,
			Longitude: -81.6557,
		},
		Distance: 0,
	},
	City{
		Name: "Fort Worth",

		Coordinates: Coordinates{
			Latitude:  32.7555,
			Longitude: -97.3308,
		},
		Distance: 0,
	},
	City{
		Name: "Columbus",

		Coordinates: Coordinates{
			Latitude:  39.9612,
			Longitude: -82.9988,
		},
		Distance: 0,
	},
	City{
		Name: "Charlotte",

		Coordinates: Coordinates{
			Latitude:  35.2271,
			Longitude: -80.8431,
		},
		Distance: 0,
	},
	City{
		Name: "San Francisco",

		Coordinates: Coordinates{
			Latitude:  37.7749,
			Longitude: -122.4194,
		},
		Distance: 0,
	},
	City{
		Name: "Indianapolis",

		Coordinates: Coordinates{
			Latitude:  39.7684,
			Longitude: -86.1581,
		},
		Distance: 0,
	},
	City{
		Name: "Seattle",

		Coordinates: Coordinates{
			Latitude:  47.6062,
			Longitude: -122.3321,
		},
		Distance: 0,
	},
	City{
		Name: "Denver",

		Coordinates: Coordinates{
			Latitude:  39.7392,
			Longitude: -104.9903,
		},
		Distance: 0,
	},
	City{
		Name: "Washington",

		Coordinates: Coordinates{
			Latitude:  38.9072,
			Longitude: -77.0369,
		},
		Distance: 0,
	},
	City{
		Name: "Boston",

		Coordinates: Coordinates{
			Latitude:  42.3601,
			Longitude: -71.0589,
		},
		Distance: 0,
	},
	City{
		Name: "El Paso",

		Coordinates: Coordinates{
			Latitude:  31.7619,
			Longitude: -106.4850,
		},
		Distance: 0,
	},
	City{
		Name: "Nashville",

		Coordinates: Coordinates{
			Latitude:  36.1627,
			Longitude: -86.7816,
		},
		Distance: 0,
	},
	City{
		Name: "Detroit",

		Coordinates: Coordinates{
			Latitude:  42.3314,
			Longitude: -83.0458,
		},
		Distance: 0,
	},
	City{
		Name: "Oklahoma City",

		Coordinates: Coordinates{
			Latitude:  35.4676,
			Longitude: -97.5164,
		},
		Distance: 0,
	},
	City{
		Name: "Portland",

		Coordinates: Coordinates{
			Latitude:  45.5051,
			Longitude: -122.6750,
		},
		Distance: 0,
	},
	City{
		Name: "Las Vegas",

		Coordinates: Coordinates{
			Latitude:  36.1699,
			Longitude: -115.1398,
		},
		Distance: 0,
	},
	City{
		Name: "Memphis",

		Coordinates: Coordinates{
			Latitude:  35.1495,
			Longitude: -90.0490,
		},
		Distance: 0,
	},
	City{
		Name: "Louisville",

		Coordinates: Coordinates{
			Latitude:  38.2527,
			Longitude: -85.7585,
		},
		Distance: 0,
	},
	City{
		Name: "Baltimore",

		Coordinates: Coordinates{
			Latitude:  39.2904,
			Longitude: -76.6122,
		},
		Distance: 0,
	},
	City{
		Name: "Milwaukee",

		Coordinates: Coordinates{
			Latitude:  43.0389,
			Longitude: -87.9065,
		},
		Distance: 0,
	},
	City{
		Name: "Albuquerque",

		Coordinates: Coordinates{
			Latitude:  35.0844,
			Longitude: -106.6504,
		},
		Distance: 0,
	},
	City{
		Name: "Tucson",

		Coordinates: Coordinates{
			Latitude:  32.2226,
			Longitude: -110.9747,
		},
		Distance: 0,
	},
	City{
		Name: "Fresno",

		Coordinates: Coordinates{
			Latitude:  36.7378,
			Longitude: -119.7871,
		},
		Distance: 0,
	},
	City{
		Name: "Mesa",

		Coordinates: Coordinates{
			Latitude:  33.4152,
			Longitude: -111.8315,
		},
		Distance: 0,
	},
	City{
		Name: "Sacramento",

		Coordinates: Coordinates{
			Latitude:  38.5816,
			Longitude: -121.4944,
		},
		Distance: 0,
	},
	City{
		Name: "Atlanta",

		Coordinates: Coordinates{
			Latitude:  33.7490,
			Longitude: -84.3880,
		},
		Distance: 0,
	},
	City{
		Name: "Kansas City",

		Coordinates: Coordinates{
			Latitude:  39.0997,
			Longitude: -94.5786,
		},
		Distance: 0,
	},
	City{
		Name: "Colorado Springs",

		Coordinates: Coordinates{
			Latitude:  38.8339,
			Longitude: -104.8214,
		},
		Distance: 0,
	},
	City{
		Name: "Miami",

		Coordinates: Coordinates{
			Latitude:  25.7617,
			Longitude: -80.1918,
		},
		Distance: 0,
	},
	City{
		Name: "Raleigh",

		Coordinates: Coordinates{
			Latitude:  35.7796,
			Longitude: -78.6382,
		},
		Distance: 0,
	},
	City{
		Name: "Omaha",

		Coordinates: Coordinates{
			Latitude:  41.2565,
			Longitude: -95.9345,
		},
		Distance: 0,
	},
	City{
		Name: "Long Beach",

		Coordinates: Coordinates{
			Latitude:  33.7701,
			Longitude: -118.1937,
		},
		Distance: 0,
	},
	City{
		Name: "Virginia Beach",

		Coordinates: Coordinates{
			Latitude:  36.8529,
			Longitude: -75.9780,
		},
		Distance: 0,
	},
	City{
		Name: "Oakland",

		Coordinates: Coordinates{
			Latitude:  37.8044,
			Longitude: -122.2711,
		},
		Distance: 0,
	},
	City{
		Name: "Minneapolis",

		Coordinates: Coordinates{
			Latitude:  44.9778,
			Longitude: -93.2650,
		},
		Distance: 0,
	},
	City{
		Name: "Tulsa",

		Coordinates: Coordinates{
			Latitude:  36.1539,
			Longitude: -95.9928,
		},
		Distance: 0,
	},
	City{
		Name: "Arlington",

		Coordinates: Coordinates{
			Latitude:  32.7357,
			Longitude: -97.1081,
		},
		Distance: 0,
	},
	City{
		Name: "New Orleans",

		Coordinates: Coordinates{
			Latitude:  29.9511,
			Longitude: -90.0715,
		},
		Distance: 0,
	},
	City{
		Name: "Wichita",

		Coordinates: Coordinates{
			Latitude:  37.6872,
			Longitude: -97.3301,
		},
		Distance: 0,
	},
}

// RandomUSCity 生成一个随机的美国城市示例
func RandomUSCity() City {
	// 示例城市列表（可扩展）
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	return USCities[r.Intn(len(USCities))]
}

func IsInContinentalUS(lat, lon float64) bool {
	return lat >= 24.5 && lat <= 49.4 && lon >= -124.8 && lon <= -66.9
}

package v2

import (
	"math"

	"github.com/zeusro/system/function/local"
	v1 "github.com/zeusro/system/problems/np/model/v1"
)

type Salesman struct {
	TodoCity map[string]v1.City // 计划旅行的所有城市列表
	Plan     []v1.City          // 实际执行的旅行计划,是一个环形队列，这里简单用数组表示
	KURO     float64            // KURO是日本动画《K》里面的一个角色，这里用来表示旅行的总距离，是一种浪漫主义表达手法
	Truth    bool               //问题是否可解
}

func NewSalesman(cities []v1.City) *Salesman {
	if len(cities) < 2 {
		panic("至少需要两个城市才能进行旅行")
	}
	s := &Salesman{
		TodoCity: make(map[string]v1.City),
	}
	// 拿到"地图"，获取USA所有城市背景之后，直接map化
	// 初始化旅行城市列表
	for _, c := range cities {
		s.TodoCity[c.Name] = c
	}
	s.Plan = make([]v1.City, len(cities)+1) // 预分配空间，+1是为了回到起点城市
	return s
}

// Travel 踏上寻找n的旅程
func (s *Salesman) TravelN(cityName string, n int) {
	// 上一次的目的地是这一次的起点城市。0比较特殊，代表出发城市。
	// 起点城市不在旅行计划中
	current := s.TodoCity[cityName]
	if n >= 1 {
		s.Plan[n] = current
	}
	delete(s.TodoCity, cityName) //由于计划是单线程，不用考虑线程安全
	//边界的判断条件是剩余旅行城市=0
	if n == 0 {
		s.Plan[0] = s.Plan[len(s.Plan)-1] // 确保最后一个城市是起点城市
		return
	}
	var nextCity v1.City
	minDistance := math.MaxFloat64
	for _, city := range s.TodoCity {
		distance := local.Haversine(city.Latitude, city.Longitude, current.Latitude, current.Longitude)
		if distance < minDistance {
			minDistance = distance
			nextCity = city
		}
	}
	s.Plan[n].Distance = minDistance
	s.KURO += minDistance                     // 累加距离
	s.TravelN(nextCity.Name, len(s.TodoCity)) // 递归调用
}

func (s *Salesman) GetK() float64 {
	if s.IsSolvable(s.Plan) {
		return s.KURO
	}
	return 0
}

func (s *Salesman) IsSolvable(city []v1.City) bool {
	if len(s.TodoCity) == 0 && len(s.Plan) == (len(city)+1) {
		s.Truth = true
	}
	return s.Truth
}

// haversine 📌 Haversine 公式：计算地球上两点的距离
// 传入两点的经纬度，返回两点之间的距离（单位：公里）
func Haversine(lat1, lon1, lat2, lon2 float64) float64 {
	const R = 6371 // 地球半径（单位：公里）

	dLat := degreesToRadians(lat2 - lat1)
	dLon := degreesToRadians(lon2 - lon1)

	a := math.Sin(dLat/2)*math.Sin(dLat/2) +
		math.Cos(degreesToRadians(lat1))*math.Cos(degreesToRadians(lat2))*
			math.Sin(dLon/2)*math.Sin(dLon/2)

	c := 2 * math.Atan2(math.Sqrt(a), math.Sqrt(1-a))
	return R * c
}

func degreesToRadians(deg float64) float64 {
	return deg * math.Pi / 180
}

package v2

import (
	"fmt"
	"testing"

	v1 "github.com/zeusro/system/problems/np/model/v1"
)

// 不打印
// ok  	github.com/zeusro/system/problems/np/model/v2	0.265s
// 打印
// ok  	github.com/zeusro/system/problems/np/model/v2	0.455s
func TestTravelN(t *testing.T) {
	s := NewSalesman(v1.USCities)
	// current := ConvertCityFromV1(v1.RandomUSCity())
	current := v1.USCities[0]
	// 直接指定起点城市，避免随机性
	s.TravelN(current.Name, len(s.TodoCity))
	if !s.IsSolvable(v1.USCities) {
		t.Fatal("旅行计划不可行")
	}
	start := 0
	for i := len(s.Plan) - 1; i > 0; i-- {
		fmt.Printf("%v:%+v\n", start, s.Plan[i])
		start++
	}
	fmt.Printf("跨越漫长的旅程（%v km），终于见到KURO\n", s.KURO)
}

// BenchmarkTravelN-8   	   15686	     74104 ns/op	   14696 B/op	       9 allocs/op
func BenchmarkTravelN(b *testing.B) {
	for i := 0; i < b.N; i++ {
		s := NewSalesman(v1.USCities)
		current := v1.RandomUSCity()
		s.TravelN(current.Name, len(s.TodoCity))
	}
}

1:t=0
2:x=x && y=y && z=z && 1=1
3:P!=NP

    踏上旅程，寻找真我