Matematyka.pl

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?

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

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

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.

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

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?

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

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

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

algorytm rozwiązujący problem muszę napisać

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.

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

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

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