nearest neighbour algorithm (tsz. nearest neighbour algorithms)
Adott egy pont vagy állapot, és egy halmaznyi másik pont. A cél: megtalálni azt a pontot, amelyik a legközelebb van.
Mérhető például:
Alkalmazás | Leírás |
---|---|
TSP heurisztika | Mindig a legközelebbi még meg nem látogatott városba megy |
k-Nearest Neighbour (k-NN) | Gépi tanulásban: a legközelebbi példák alapján osztályoz |
Klaszterezés | Pontok csoportosítása a legközelebbi középpont köré |
Navigáció, útvonalválasztás | Legközelebbi célállomás keresése |
Ez nem garantálja az optimális megoldást, de gyors és egyszerű.
import numpy as np
def euclidean(p1, p2):
return np.linalg.norm(np.array(p1) - np.array(p2))
def nearest_neighbour_tsp(points):
n = len(points)
visited = * n
path =
visited = True
total_dist = 0
for _ in range(n - 1):
last = path
nearest = None
nearest_dist = float('inf')
for i in range(n):
if not visited:
d = euclidean(points, points)
if d < nearest_dist:
nearest = i
nearest_dist = d
path.append(nearest)
visited = True
total_dist += nearest_dist
# Vissza a kiinduló ponthoz
total_dist += euclidean(points], points)
path.append(0)
return path, total_dist
points =
route, dist = nearest_neighbour_tsp(points)
print("Útvonal:", route)
print("Teljes hossz:", round(dist, 2))
✅ Előnyök | ❌ Hátrányok |
---|---|
Gyors: | Nem garantál optimális megoldást |
Egyszerű implementálni | Heurisztikaként pontatlan lehet |
Jól használható nagy adathalmazokra | Csapdába eshet lokális minimumban |
Tulajdonság | Részlet |
---|---|
Algoritmus neve | Nearest Neighbour |
Alkalmazás | TSP, osztályozás, klaszterezés |
Módszer típusa | Heurisztikus / távolságalapú |
Időkomplexitás | egyszerű esetben |
Előny | Gyors, egyszerű |
Hátrány | Nem optimális megoldást ad |