[Vickers213]

Mam plansze, zaczynam z punktu x i muszę „odwiedzić” wszystkie punkty które zaznaczyłem. Chce żeby łącza droga była jak najkrótsza. Jeden sposób na jaki wpadłem, to stworzenie 7! permutacji kolejności tych punktów, policzenie łącznej drogi dla każdego i znalezienie minimalnej wartości. Problem jest taki ze jak to nie będzie 7 tylko 20 punktów to będzie to ekstremalnie niewydajne. Wiec mam pytanie: czy zawsze wybierając najbliższy punkt od aktualnego, droga będzie najkrótsza (zakładając ze nie będzie sytuacji w której jakieś 2 punkty są w takiej samej odległości od trzeciego)

Rysunek pogladowy

#programowanie #matematyka

[L.....G]

mój realny "problem", pod prysznicem miałem rozkmine czy da sie uwydajnić podroże z punktu do punktu ( ͡° ͜ʖ ͡°)

@Vickers213: hehe lubię takie rozkminy, jednak teraz piszesz coś innego.
Albo chcesz dostać się z A do B (poprzez jakieś tam pośrednie punkty, ale po co ? nie można od razu z A do B prostą drogą ?)

Albo to jest problem komiwojażera czyli odwiedzasz wszystkie punkty w dowolnej kolejnośći (i tak wygląda Twój problem) i

[Vickers213]

@LowcaG: pisząc z punktu do punktu miałem na myśli problem komiwojażera. Właśnie czytam, ponoć najbliższy sąsiad daje średnio 25% gorszy wynik od optymalnego ( ͡° ʖ̯ ͡°)

[wytrzzeszcz]

@LowcaG: właśnie to jest problem np (komiwojażer) ale może być przybliżony problemem p trudnym (komiwojażer na płaszczyźnie)
@Vickers213: podejście by w każdym węźle trzymać listę innych posortowanych po odległości i przerywać jeśli przekroczymy minimalna już określoną trasę też jest warty uwagi. Na studiach było jeszcze podejście z algorytmem mrówkowym

[L.....G]

@Vickers213: http://www.math.uwaterloo.ca/tsp/concorde.html tym chyba ludzie osiągają jedne z najlepszych wyników

[Retsew]

@Vickers213 wgl wikipedii jeżeli dobrze rozumiem ten wzór to (n-1)!/2 , chyba że to dla jakichś konkretnych przypadków