[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

[wytrzzeszcz]

@Vickers213: problem komiwojażera na płaszczyźnie

[Vickers213]

@Vickers213: juz nawet 13 punktow to za duzo na sposob z permutacjami ( ͡° ͜ʖ ͡°)

[bl4desofglory]

@Vickers213: https://pl.wikipedia.org/wiki/Problem_komiwoja%C5%BCera

[nunczako]

@Vickers213: nie możesz wprost napisać, że próbujesz znaleźć minimalny cykl Hamiltona w pełnym grafie ważonym?

[Vickers213]

@nunczako: @bl4desofglory: @wytrzzeszcz: dzięki, nie wiedzialem ze ten problem ma wlasną nazwe

[revoolution]

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)

@Vickers213: nie

[k.....e]

@Vickers213: powodzenia ze znalezieniem algorytmu xd

[MikelThief]

@Vickers213: dijkstra?

[Narrorek]

@Vickers213: A*

[Double_M]

@Vickers213: https://pl.wikipedia.org/wiki/Algorytm_najbli%C5%BCszego_s%C4%85siada

[Scrape]

@Vickers213: odpowiednio szeroka linia załatwi problem ;)

[FFF1243]

algorytmy metaheurystyczne

[TenGumis]

@nunczako ten graf nie jest ani pełny ani ważony.

[TenGumis]

@kebab-case algorytm istnieje i OP go nawet podał. Sprawdź wszystkie permutacje. Prędzej powinieneś napisać. Powodzenia ze znalezieniem szybkiego algorytmu :)

[nunczako]

@TenGumis: jest tylko nie ma narysowanych krawędzi ale to szczegół, wagami są tutaj odległości między wierzchołkami

[TenGumis]

@nunczako przepraszam, być może masz rację. Założyłem że można chodzić tylko po krawędziach grida

[Retsew]

@Vickers213 zgodnie ze wzorem z wikipedii dla tego rysunku masz 360 kombinacji, całe popołudnie z kalkulatorem i masz wyniki :p

[L.....G]

dijkstra?

@MikelThief: hm..jak dla mnie to nie do tego służy

A*

@Narrorek: Jak wyżej.

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)

@Vickers213: Jak Ci już powiedziano, to nie.
Pytanie jest takie, chcesz ćwiczyć programowanie czy coś? Czy to Twój realny problem i chcesz znaleźć jak najlepszy wynik dowolnymi metodami?

[maciekXDDD]

@Vickers213: #!$%@? wie gościu

[Vickers213]

@Retsew: wg jakiego wzoru? jak dla mnie 7! czyli 5040, a jak będe chcial wiecej punktow to będzie to tak dużo że komputer nie wyrabia

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