-
Data: 2016-05-11 10:38:43
Temat: Re: problem z algorytmiki
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]On 11.05.2016 10:01, M.M. wrote:
> Mamy dwa równoliczne zbiory punktów 2D. Każdemu punktowi z
> jednego zbioru trzeba przyporządkować jeden punkt z drugiego
> zbioru. Innymi słowy, trzeba punkty połączyć w pary, w każdej
> parze jeden punkt musi być z pierwszego zbioru, drugi z drugiego.
> Suma odległości pomiędzy punktami z pary musi być najmniejsza.
>
> Można to szybko policzyć, czy nie?
To jest maksymalny przepływ o minimalnym koscie w grafie
dwudzielnym ("Assignment problem"). Algorytm węgeirski
i masz rozwiązanie w O(n^3),
Czy to "szybko", trudno powiedzieć ;-)
Wykorzystując to, że sa one na płaszczyźnie są różne heurystyki,
googlaj pod Euclidean Bipartite Matching
np to:
http://homepage.cs.uiowa.edu/~kvaradar/paps/p079-aga
rwal.pdf
Problem ten można rozwiązywać algorytmem simplex... niby wykłądniczy,
ale dla rzeczywistych danych możę zadziaąłć w miarę szybko;-)
Uwaga. Rozwiązania są dla problemu ciut bardziej skomplikowanego,
więc być mozę da się prościej. Na szybko nie widzę.
pzdr
bartekltg
Następne wpisy z tego wątku
- 11.05.16 10:46 M.M.
- 15.05.16 08:02 slawek
- 15.05.16 08:33 Wojciech Muła
- 15.05.16 14:07 M.M.
- 15.05.16 19:35 bartekltg
- 15.05.16 19:44 bartekltg
- 15.05.16 20:24 bartekltg
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-17 ZŁOMNIK o pracy w TVN TURBO, nowych przepisach i współczesnej motoryzacji. Turbo Taryfa!
- 2024-05-17 Białystok => DevOps Engineer Conexa First (Contractor) <=
- 2024-05-17 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-17 Zabrze => Junior HelpDesk <=
- 2024-05-17 Bieruń => Administrator i wdrożeniowiec Lotus Notes/Domino <=
- 2024-05-17 Warszawa => Senior Software Engineer PHP (BillPro) Contractor <=
- 2024-05-17 Warszawa => International freight forwarder <=
- 2024-05-17 Warszawa => Fullastack (Java) Developer <=
- 2024-05-17 Lublin => Business Development Manager - obszar bezpieczeństwa IT <=
- 2024-05-17 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-17 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-17 Warszawa => Senior PHP Developer (Symfony) <=
- 2024-05-18 wojna wojno a kredyt trzeba spłacać
- 2024-05-16 Samo rozładowywanie baterii trakcyjnej w elektryku.
- 2024-05-16 Warszawa => Senior PHP Developer (Symfony) <=