problem najkrótszej drogi
-
Cosinusoida89sonia
- Użytkownik
- Posty: 37
- Rejestracja: 24 mar 2013, o 22:58
- Płeć: Kobieta
- Lokalizacja: Polska
problem najkrótszej drogi
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?-- 4 wrz 2014, o 11:53 --Rozumiem że wybranie z 27 stolic (bo Warszawa juz odpada) 15 najludniejszych i znalezienie najkrótszej drogi z Warszawy przez te 15 miast i znów do Warszawy nie wchodzi w grę.
-
kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
problem najkrótszej drogi
Piszesz to samo zadanie już drugi raz. Podpowiedziałam, że można sprawdzić np. algorytm zachłanny. Robiłaś coś z tym zadaniem?
Najpierw wybierasz stolice:
Tworzysz
\(\displaystyle{ O _{27 \times 27}}\) - macierz odległości pomiędzy wszystkimi parami stolic
\(\displaystyle{ W _{27}}\) - wektor odległości wszystkich stolic od Warszawy
\(\displaystyle{ L _{27}}\) - wektor liczby ludności państw odpowiadających stolicom
\(\displaystyle{ R _{27}}\) - wektor roboczy
Krok 1. Wypełniasz wektor \(\displaystyle{ R}\) wartościami
\(\displaystyle{ r _{i}= \frac{l _{i} }{2w _{i} }}\)
Pierwsza stolica to taka, dla której \(\displaystyle{ r _{i}}\) jest maksymalne
W miejsce wybranej stolicy wpisujesz do wektora \(\displaystyle{ R}\) \(\displaystyle{ r _{i}=-1}\)
Krok 2. Wypełniasz na nowo wektor \(\displaystyle{ R}\) w taki sposób: wartości \(\displaystyle{ -1}\) pozostawiasz bez zmian, a dla pozostałych elementów liczysz
\(\displaystyle{ r _{i}= \frac{suma \ ludnosci \ l \ panstw \ dla \ wybranych \ wczesniej \ stolic+l _{i} }{w _{stolicy \ z \ kroku \ 1}+suma \ odległosci \ o \ \ miedzy \ stolicami \ z \ poprzednich \ krokow+ o_{i,ostatnia \ wybrana \ stolica} + w _{i} }}\)
Kolejna stolica jest taka, dla której \(\displaystyle{ r _{i}}\) jest maksymalne
W miejsce wybranej stolicy wpisujesz do wektora \(\displaystyle{ R}\) \(\displaystyle{ r _{i}=-1}\)
Wykonujesz 14 razy Krok 2.
Masz już \(\displaystyle{ 15}\) stolic, więc liczysz najkrótszą trasę jakimś algorytmem dla problemu komiwojażera.
Jakieś tam przybliżenie rozwiązania optymalnego z tego dostaniesz.
Najpierw wybierasz stolice:
Tworzysz
\(\displaystyle{ O _{27 \times 27}}\) - macierz odległości pomiędzy wszystkimi parami stolic
\(\displaystyle{ W _{27}}\) - wektor odległości wszystkich stolic od Warszawy
\(\displaystyle{ L _{27}}\) - wektor liczby ludności państw odpowiadających stolicom
\(\displaystyle{ R _{27}}\) - wektor roboczy
Krok 1. Wypełniasz wektor \(\displaystyle{ R}\) wartościami
\(\displaystyle{ r _{i}= \frac{l _{i} }{2w _{i} }}\)
Pierwsza stolica to taka, dla której \(\displaystyle{ r _{i}}\) jest maksymalne
W miejsce wybranej stolicy wpisujesz do wektora \(\displaystyle{ R}\) \(\displaystyle{ r _{i}=-1}\)
Krok 2. Wypełniasz na nowo wektor \(\displaystyle{ R}\) w taki sposób: wartości \(\displaystyle{ -1}\) pozostawiasz bez zmian, a dla pozostałych elementów liczysz
\(\displaystyle{ r _{i}= \frac{suma \ ludnosci \ l \ panstw \ dla \ wybranych \ wczesniej \ stolic+l _{i} }{w _{stolicy \ z \ kroku \ 1}+suma \ odległosci \ o \ \ miedzy \ stolicami \ z \ poprzednich \ krokow+ o_{i,ostatnia \ wybrana \ stolica} + w _{i} }}\)
Kolejna stolica jest taka, dla której \(\displaystyle{ r _{i}}\) jest maksymalne
W miejsce wybranej stolicy wpisujesz do wektora \(\displaystyle{ R}\) \(\displaystyle{ r _{i}=-1}\)
Wykonujesz 14 razy Krok 2.
Masz już \(\displaystyle{ 15}\) stolic, więc liczysz najkrótszą trasę jakimś algorytmem dla problemu komiwojażera.
Jakieś tam przybliżenie rozwiązania optymalnego z tego dostaniesz.
-
Cosinusoida89sonia
- Użytkownik
- Posty: 37
- Rejestracja: 24 mar 2013, o 22:58
- Płeć: Kobieta
- Lokalizacja: Polska
problem najkrótszej drogi
czy dobrze zrozumiałam że najpierw szukam 15-stu stolic takich że stosunek liczby ich miszkańcow do drogi z Warszawy do danej stolicy i z powrotem jest największy?
-
Cosinusoida89sonia
- Użytkownik
- Posty: 37
- Rejestracja: 24 mar 2013, o 22:58
- Płeć: Kobieta
- Lokalizacja: Polska
problem najkrótszej drogi
Tak.faktycznie.
Mam jeszcze pytanie. Czy do tego zadania da się zapisać funkcje celu? Bo juz wiem jak algorytm ma dzieląc ale jak optymalizuje się cos to wlasne ustala się funkcje celu czyli ta wartość która chcemy w naszym przypadku zmaksymalizować tzn suma ludzi przez calkowita droga.
Mam jeszcze pytanie. Czy do tego zadania da się zapisać funkcje celu? Bo juz wiem jak algorytm ma dzieląc ale jak optymalizuje się cos to wlasne ustala się funkcje celu czyli ta wartość która chcemy w naszym przypadku zmaksymalizować tzn suma ludzi przez calkowita droga.
-
kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
problem najkrótszej drogi
Wybór 15 stolic:
\(\displaystyle{ \frac{ \sum _{i=1} ^{15}l_{i} } {w _{1}+w _{15}+ \sum _{i=1} ^{14}o_{i \ i+1} } \rightarrow max}\)
Minimalizacja długości trasy:
\(\displaystyle{ w _{1}+w _{15}+ \sum _{i=1} ^{14}o_{i \ i+1} \rightarrow min}\)
W kroku 2 był błąd w formule (nie zauważyłam).Formuła \(\displaystyle{ \frac{ \sum _{k=1} ^{i}l_{k} }{w _{1}+w _{i} + \sum _{k=1} ^{i-1}o_{k \ k+1} }}\)
\(\displaystyle{ \frac{ \sum _{i=1} ^{15}l_{i} } {w _{1}+w _{15}+ \sum _{i=1} ^{14}o_{i \ i+1} } \rightarrow max}\)
Minimalizacja długości trasy:
\(\displaystyle{ w _{1}+w _{15}+ \sum _{i=1} ^{14}o_{i \ i+1} \rightarrow min}\)
W kroku 2 był błąd w formule (nie zauważyłam).Formuła \(\displaystyle{ \frac{ \sum _{k=1} ^{i}l_{k} }{w _{1}+w _{i} + \sum _{k=1} ^{i-1}o_{k \ k+1} }}\)
-
Cosinusoida89sonia
- Użytkownik
- Posty: 37
- Rejestracja: 24 mar 2013, o 22:58
- Płeć: Kobieta
- Lokalizacja: Polska
problem najkrótszej drogi
a czy wybór 15-stu stolic nie powinien wyglądać tak:
\(\displaystyle{ \frac{ \sum_{1}^{15} l_{i} }{ \sum_{1}^{15} w_{i} } \rightarrow max}\)
bo chyba w pierwszym kroku interesują tylko odległości poszczególnych stolic od Warszawy a odległości między nimi dopiero w drugim kroku będą nam potrzebne przy minimalizacji trasy.
chociaż też zastanawiam sie czy nie powinno się jakoś inaczej indeksować tych \(\displaystyle{ l_{i}}\) bo jak mamy \(\displaystyle{ l_{1}+ l_{2}+...+l _{15}}\) to nie wiem czy to nie wygląda tak że bierzemy 15-cie pierwszych wartości z wektora \(\displaystyle{ L _{27}}\)... ?
\(\displaystyle{ \frac{ \sum_{1}^{15} l_{i} }{ \sum_{1}^{15} w_{i} } \rightarrow max}\)
bo chyba w pierwszym kroku interesują tylko odległości poszczególnych stolic od Warszawy a odległości między nimi dopiero w drugim kroku będą nam potrzebne przy minimalizacji trasy.
chociaż też zastanawiam sie czy nie powinno się jakoś inaczej indeksować tych \(\displaystyle{ l_{i}}\) bo jak mamy \(\displaystyle{ l_{1}+ l_{2}+...+l _{15}}\) to nie wiem czy to nie wygląda tak że bierzemy 15-cie pierwszych wartości z wektora \(\displaystyle{ L _{27}}\)... ?
-
kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
problem najkrótszej drogi
Funkcja celu musi być taka, jak w treści zadania. Poza tym uwzględnienie odległości między miastami zmniejsza rozrzut stolic. Np. niech trzy stolice i Warszawa leżą na jednej prostej. Od zachodu: A,B,Warszawa,C. Powiedzmy, że z tych trzech stolic mamy wybrać dwie.
Niech
\(\displaystyle{ l _{A}=100, \ w _{A}=1000 \\
l _{B}=40, \ w _{B}=500 \\
l _{C}=90, \ w _{C}=1000 \\
AB=500}\)
Wtedy, wg. Twojego kryterium byłoby \(\displaystyle{ \frac{l _{A} }{w _{A}}= 0,1; \ \frac{l _{B} }{w _{B} }=0,08; \ \frac{l _{C} }{w _{C} }=0,09}\), więc wybierzesz A i C.
Wtedy szukany stosunek to \(\displaystyle{ \frac{190}{1000+2000+1000}=0,0475}\)
Natomiast wg. mojego kryterium będzie AB i dostanę \(\displaystyle{ \frac{140}{1000+500+500}= 0,07}\).
Co do indeksacji masz rację. Trzebaby stworzyć dodatkowy wektor binarny \(\displaystyle{ X _{27 } .}\) Na początku wypełnić go zerami, a potem przy każdym wyborze kolejnej stolicy zamieniać odpowiednie 0 na 1. Wtedy w funkcji celu byłoby w liczniku \(\displaystyle{ \sum _{i=1} ^{27}l_{i}x _{i}}\). Mianownik też należałoby podobnie zmienić, tworząc dodatkową binarną macierz odległości \(\displaystyle{ Y _{27 \times 27}}\).
Niech
\(\displaystyle{ l _{A}=100, \ w _{A}=1000 \\
l _{B}=40, \ w _{B}=500 \\
l _{C}=90, \ w _{C}=1000 \\
AB=500}\)
Wtedy, wg. Twojego kryterium byłoby \(\displaystyle{ \frac{l _{A} }{w _{A}}= 0,1; \ \frac{l _{B} }{w _{B} }=0,08; \ \frac{l _{C} }{w _{C} }=0,09}\), więc wybierzesz A i C.
Wtedy szukany stosunek to \(\displaystyle{ \frac{190}{1000+2000+1000}=0,0475}\)
Natomiast wg. mojego kryterium będzie AB i dostanę \(\displaystyle{ \frac{140}{1000+500+500}= 0,07}\).
Co do indeksacji masz rację. Trzebaby stworzyć dodatkowy wektor binarny \(\displaystyle{ X _{27 } .}\) Na początku wypełnić go zerami, a potem przy każdym wyborze kolejnej stolicy zamieniać odpowiednie 0 na 1. Wtedy w funkcji celu byłoby w liczniku \(\displaystyle{ \sum _{i=1} ^{27}l_{i}x _{i}}\). Mianownik też należałoby podobnie zmienić, tworząc dodatkową binarną macierz odległości \(\displaystyle{ Y _{27 \times 27}}\).