Jump to content

Recommended Posts

Witam.

Wykonuje projekt w C++ rozwiązujący problem komiwojażer. Miasta (czyli ich punkty w układzie x,y), mają być generowane losowo. Pojawia się tutaj moje pytanie. Czy język C++ oferuje generator losowy (bądź pseudolosowy), który będzie w stanie wylosować określoną ilość unikatowych par liczbowych? Czy istnieją biblioteki, które jakoś mi z tym pomogą? A może któryś z Użytkowników posiada zoptymalizowany kod takiego generatora? Oczywiście biorę pod uwagę sprawdzanie wszelkich poprzednich par, jednak chciałbym lepiej rozwiązać ten problem. 

Pozdrawiam.

Share this post


Link to post
Share on other sites

Kojarzy mi się taki wzór:

f(i) = A * i % B

Jeżeli A i B będą względnie pierwsze (brak wspólnych dzielników poza 1), to dla i z przedziału <0, B-1> uzyskasz unikalne wartości z tego właśnie przedziału. Jako że B będzie z góry znane, to wystarczy zapewnić, żeby A było odpowiednio dużą (żeby przypadkiem nie stało się dzielnikiem B) liczbą pierwszą. Przy okazji wypada się zatroszczyć, żeby iloczyn A*B mieścił się w zakresie wartości użytego typu danych.
(przy czym uczyłem się o tym ze ~3 lata temu, więc być może są do spełnienia jeszcze jakieś dodatkowe warunki, o których zdążyłem już zapomnieć)

Wracając do mapy - dla uproszczenia założę, że ma mieć identyczne wymiary - n. Przyjmujesz wtedy B=n*n, a kolejne punkty mają współrzędne x=f(i)/n oraz y=f(i)%n.

Share this post


Link to post
Share on other sites

Generator liczb losowych

Generatora liczb losowych niestety w prawdziwym komputerze nie uświadczysz.

Generator liczb pseudolosowych

W bibliotece <random> masz sporo możliwości losowania, wyboru rozkładu itd. kilka słów o tym napisał Kerrek na StackOverflow: http://stackoverflow.com/a/7114482

Losowanie bez powtórzeń

Generatory liczb pseudolosowych losują liczby, zmiana ich tak, żeby nie generowały duplikatów byłaby dość ciężka i bezsensowna, tym się musisz zająć sam. Możesz to zrobić albo zapamiętując wszystkie wylosowane elementy i przy każdym kolejnym sprawdzać czy jest unikatowy, albo wygenerować "ręcznie" dużo możliwych wyników i tylko generować indeksy tych, które zostaną użyte. Tutaj można zrobić taką sztuczkę, że jeżeli masz N elementów w tablicy, to losujesz indeks `i` należący do [1, n], a następnie wykonujesz swap(i, n). Wtedy losujesz znowu już od 1 do n-1, potem swap (i, n-1) i tak dalej. Dzięki temu masz pewność, że nie będziesz miał pecha (nie będziesz ciągle losował tego samego elementu).
Jak łatwo sprawdzać czy dany element wcześniej wystąpił? Możesz użyć standardowej implementacji set albo unordered_set. 

"Lepiej rozwiązać ten problem"
Po co efektywnie losować dane do problemu komiwojażera? Problem i tak jest NP-trudny, więc to czy wylosujesz dane w czasie liniowym, kwadratowym czy sześciennym nie ma znaczenia.

Edited by Hakken
dr. Klin by mnie zabił

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...