optymalizacja problemu

Cosinusoida89sonia · Post autor: **Cosinusoida89sonia** » 1 wrz 2014, o 21:57

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?

musialmi · Post autor: **musialmi** » 1 wrz 2014, o 23:31

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

Cosinusoida89sonia · Post autor: **Cosinusoida89sonia** » 2 wrz 2014, o 11:49

Czy to chodzi o jakiś algorytm związany z drzewami ?

musialmi · Post autor: **musialmi** » 2 wrz 2014, o 11:54

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.

Dilectus · Post autor: **Dilectus** » 2 wrz 2014, o 12:51

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...

kropka+ · Post autor: **kropka+** » 2 wrz 2014, o 14:22

No niezupełnie. Poza Polską jest 27 państw, więc mamy \(\displaystyle{ {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?

Dilectus · Post autor: **Dilectus** » 3 wrz 2014, o 00:48

Masz rację, Kropko. Zatem tych piętnastek jest

\(\displaystyle{ {27 \choose 15}=17383860}\)

a więc zaledwie trochę ponad siedemnaście milionów...

Cosinusoida89sonia · Post autor: **Cosinusoida89sonia** » 3 wrz 2014, o 08:56

algorytm rozwiązujący problem muszę napisać

musialmi · Post autor: **musialmi** » 3 wrz 2014, o 10:31

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.

Cosinusoida89sonia · Post autor: **Cosinusoida89sonia** » 3 wrz 2014, o 22:18

Też tak myślałam ale nie wiem jak to zapisać matematycznie...

Dilectus · Post autor: **Dilectus** » 3 wrz 2014, o 23:56

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 \(\displaystyle{ 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ć \(\displaystyle{ 15!}\), czyli \(\displaystyle{ 1,3 \cdot 10^{12}}\) tras. Trochę roboty jest...

kropka+ · Post autor: **kropka+** » 4 wrz 2014, o 14:27

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