szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 1 wrz 2014, o 20:57 
Użytkownik

Posty: 38
Lokalizacja: Polska
Polski dyplomata ma objechać 15 stolic państw z Unii Europejskiej i przedstawić stanowisko rządu RP. Wyjeżdża z Warszawy i do Warszawy trafia. Jakie stolice ma odwiedzić i jaką trasą ma jechać aby stosunek sumy liczby mieszkańców państw, które odwiedzi, dzielony przez całkowitą przebytą drogę mierzoną w kilometrach był jak największy?
Góra
Mężczyzna Offline
PostNapisane: 1 wrz 2014, o 22:31 
Użytkownik
Avatar użytkownika

Posty: 3500
Lokalizacja: PWr ocław
Na początku należy skupić się na zachodzie i południu Europy, natomiast odrzucić północ. Problem byłby łatwiejszy, gdyby nie chodziło tylko o stolice, w końcu takie miasta jak Barcelona, Hamburg malutkie nie są. Warto pokręcić się po terenie pomiędzy Polską a Grecją (dużo państw na małej powierzchni). Podoba mi się ten problem, może na dniach zajmę się nim bardziej, jeśli nikt nie rozwiąże wcześniej :p
Góra
Kobieta Offline
PostNapisane: 2 wrz 2014, o 10:49 
Użytkownik

Posty: 38
Lokalizacja: Polska
Czy to chodzi o jakiś algorytm związany z drzewami ?
Góra
Mężczyzna Offline
PostNapisane: 2 wrz 2014, o 10:54 
Użytkownik
Avatar użytkownika

Posty: 3500
Lokalizacja: PWr ocław
Nie wiem. Znam tylko zasadę na zadanie "Przejdź z miasta A do B przez kilka innych miast, idąc sumarycznie najkrótszą drogą": wybieranie zawsze najkrótszej drogi to nie jest gwarancja rozwiązania. To trzeba zrobić metodą prób i błędów (np. rekurencyjnie, jeśli za pomocą komputera). Albo przynajmniej tak mi się wydaje, jako laikowi.
Góra
Mężczyzna Offline
PostNapisane: 2 wrz 2014, o 11:51 
Użytkownik

Posty: 2043
Lokalizacja: Warszawa
Cytuj:
Polski dyplomata ma objechać 15 stolic państw z Unii Europejskiej

Ponieważ UE składa się z 28 państw, warto wiedzieć, na ile sposobów można wybrać 15 z nich. Jest to, jak wiadomo, kombinacja 15 z 28, czyli liczba 37442160. Spośród tych ponad trzydziestu milionów sposobów należy wybrać ten, który spełnia warunki zadania... :)
Góra
Kobieta Offline
PostNapisane: 2 wrz 2014, o 13:22 
Użytkownik
Avatar użytkownika

Posty: 4376
Lokalizacja: Łódź
No niezupełnie. Poza Polską jest 27 państw, więc mamy {27 \choose 15} takich piętnastek.

Czy Ty masz tylko przedstawić model/algorytm optymalizacyjny, czy masz też podać rozwiązanie? Czy możesz napisać program, który to policzy?
Góra
Mężczyzna Offline
PostNapisane: 2 wrz 2014, o 23:48 
Użytkownik

Posty: 2043
Lokalizacja: Warszawa
Masz rację, Kropko. Zatem tych piętnastek jest

{27 \choose 15}=17383860

a więc zaledwie trochę ponad siedemnaście milionów... :)
Góra
Kobieta Offline
PostNapisane: 3 wrz 2014, o 07:56 
Użytkownik

Posty: 38
Lokalizacja: Polska
algorytm rozwiązujący problem muszę napisać
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2014, o 09:31 
Użytkownik
Avatar użytkownika

Posty: 3500
Lokalizacja: PWr ocław
Znasz informatyczny problem o hetmanach? Ustaw 8 hetmanów na szachownicy tak, żeby żaden nie był na biciu. Można to rozwiązać tak: stawiasz jednego, następnie stawiasz drugiego gdzieś. Jeśli jest na biciu, to stawiasz w kolejne miejsce. I tak dalej, aż hetman będzie bezpieczny. Kolejne ustawiasz w ten sam sposób. Jeśli się zdarzy, że któryś nie ma żadnego miejsca, na którym mógłby zostać ustawiony, to cofasz się o jednego hetmana i przesuwasz go w inne dostępne miejsce. I tak dalej. Myślę, że trzeba to rozwiązać podobną metodą. Tutaj będziemy ustawiać miasta w takiej kolejności, żeby szukany stosunek był jak największy.
Góra
Kobieta Offline
PostNapisane: 3 wrz 2014, o 21:18 
Użytkownik

Posty: 38
Lokalizacja: Polska
Też tak myślałam ale nie wiem jak to zapisać matematycznie...
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2014, o 22:56 
Użytkownik

Posty: 2043
Lokalizacja: Warszawa
Cytuj:
aby stosunek sumy liczby mieszkańców państw, które odwiedzi, dzielony przez całkowitą przebytą drogę mierzoną w kilometrach był jak największy?


Myślę, że chodzi tu nie o mieszkańców, a o obywateli państw... :)

Można znaleźć liczbę obywateli każdej możliwej piętnastki państw. Powinna być ona jak największa, zaś przebyta trasa - jak najkrótsza. W każdej piętnastce jest 15! permutacji tras, z których jedna jest najkrótsza.

W każdej możliwej piętnastce (a jest ich siedemnaście milionów z haczykiem) trzeba przebadać 15!, czyli 1,3 \cdot 10^{12} tras. Trochę roboty jest... :)
Góra
Kobieta Offline
PostNapisane: 4 wrz 2014, o 13:27 
Użytkownik
Avatar użytkownika

Posty: 4376
Lokalizacja: Łódź
Dlatego w takich sytuacjach szuka się przybliżonych rozwiązań optymalnych - tracimy na przybliżeniu, ale zyskujemy na czasie. Np. można zastosować algorytm zachłanny, gdzie w każdym kroku będziemy dobierali jedną stolicę, której wybór jest lokalnie optymalny. Gdy wybierzemy 15 stolic kończymy algorytm.
Skrótowy przegląd różnych algorytmów jest np. tutaj http://zasoby1.open.agh.edu.pl/dydaktyka/informatyka/c_algorytmy_i_str_danych/index.php?go=algrytmy_zachlanne
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Optymalizacja - najmniejsze pole powierzchni, koszta itd  Suzie  2
 Optymalizacja Wielokryterialna - zbiór punktów niezdominowan  Standy131  0
 Optymalizacja wielokryterialna funkcji  maszynaz  1
 Programowanie liniowe optymalizacja wyboru trzy zmienne  Evica  1
 Optymalizacja rozwiązania - analiza Solver  MiszaK89  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl