Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
7 odpowiedzi w tym temacie

#1 Mateusz Szczurek

Mateusz Szczurek

    Nowicjusz

  • Użytkownik
  • 4 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 10.08.2015 - 21:25

Cześć! Zamierzam spotkać sie z kilkunastoma znajomymi. Problem w tym, że pochodzimy z róznych miast i chcę, by każdy z nas miał jak najmniejszą odlgłość do pokonania. Nie może byc to odległość równa dla każdego - na figórze z wierzchołkami jako nasze miasta nie da sie opisać okręgu. Czy możliwe jest jednak ustalenie takiego punktu spotkania (obliczenie go w układzie współrzędnych czy cokolwiek), aby każdy z nas miał mozliwie najmniejszą trasę do pokonania? W sensie by od każdego z nas do tego punktu była jak najmniejsza odległość - nie musi być równa, ale nie chcę, żeby ktoś z nas miał do pokonania np. 100km a ktoś 5km


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 3458 postów
3051
Profesor
  • Płeć:Mężczyzna

Napisano 10.08.2015 - 21:36

Rozumiem, że pomijasz zakręty drogi, nierówności terenu itd. Chodzi Ci o wyznaczenie punktu na mapie (płaskiej) a droga to odcinki od miast do punkty spotkania.


  • 0

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską


#3 Mateusz Szczurek

Mateusz Szczurek

    Nowicjusz

  • Użytkownik
  • 4 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 10.08.2015 - 21:38

Tak, ale jeśli obliczenia nie były by zbyt skomplikowane, to mażna by drogi uwzględnić


  • 0

#4 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 3458 postów
3051
Profesor
  • Płeć:Mężczyzna

Napisano 10.08.2015 - 22:13

No to raczej były by skomplikowane bo musiał byś mieć wykaz wszystkich możliwych odległości między miejscowościami. Jest to możliwe ale raczej mało praktyczne.

 

pre_1439239416__dro.jpg

 

Jeszcze tylko chciałbym coś uścielić - ta figura jest wypukła

 

Podejście z okręgiem opisanym jest dobre, nawet jeżeli nie da się dokładnie opisać okręgu.

 

Teraz problem przedstawia się tak wyznaczyć środek okręgu tak by suma odległości od puktów wielokąta do brzegu okręgu była jak najmniejsza.

 

Jak to można aproksymować

Bierzesz mniejszą ilość miast i szukasz okręgu, Następnie pomijasz inne miasto i szukasz okręgu. Wyszło Ci teraz dwa różne punkty (środki okręgów) i weź środek tych punktów jako rozwiązanie.

 

Staraj się pomijać punkty bliskie sobie bo to fałszuje Ci wynik zgodnie z metodą najmniejszych kwadratów (drugie narzędzie do badania - nieco pracochłonne ale dość skuteczne, a z komputerem da się zrobić)

 

https://github.com/t...lding/issues/47

Zielony to punkt o który Ci chodzi

 

 

 

Wystarczy takie podejście?


  • 1

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską


#5 Mateusz Szczurek

Mateusz Szczurek

    Nowicjusz

  • Użytkownik
  • 4 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 11.08.2015 - 10:17

Hmm, można by według jakiegoś schematu pogrupować niektóre miasta w trójki i opisać na nich okręgi - następnie wyznaczyć środek wielokąta o wierzchołkach z środków tych okręgów podobną metodą.
Tylko według jakiego schematu grupować te miasta?
Jest jeszcze jeden problem - w tym przypadku niektórzy mieli by jakieś 50 km, a inni 10.
Chodzi o to, by znaleźć taki punkt, by nikt nie miał więcej niż np. 30km. Niektórzy mogą mieć 10, inni 15, ale by nikt nie miał więcej niż powiedzmy 30. Wiem, że istnieje taka możliwość tego punktu, w której największa odległość do pokonania nie przekracza najmniejszej mozliwej wartości zależnej od ułożenia tych miast, tylko nie wiem, jak go znaleźć


  • 0

#6 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 3458 postów
3051
Profesor
  • Płeć:Mężczyzna

Napisano 11.08.2015 - 10:34

Z każdego punkty zatocz łuk o promieniu 30 km. Da Ci to pewien obszar wspólny dla którego każdy ma mniej niż 30 km (no teoretycznie bo jeśli ten wielokąt przypomina spłaszczoną elipsę to takie rozwiązanie niewiele Ci da

 

Choć nowy obszar także możesz podobnie potraktować i w ten sposób wyznaczysz zoptymalizujesz rozwiązanie


  • 1

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską


#7 Mateusz Szczurek

Mateusz Szczurek

    Nowicjusz

  • Użytkownik
  • 4 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 11.08.2015 - 10:55

Faktycznie, dzięki za pomoc :)


  • 0

#8 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 3458 postów
3051
Profesor
  • Płeć:Mężczyzna

Napisano 11.08.2015 - 11:31

Możesz też podejść do problemu kosztowo

 

Może się zdarzyć, że opłaca się dojechać do dalszej miejscowości (bo jest tam bezpośredni dojazd) niż dojechać do bliższej gdzie trzeba się przesiadać.

 

Więc ustalacie z kolegami kilka proponowanych punktów spotkań a oni sprawdzają ile wyniesie koszt dojazdu do każdego z nich z własnej miejscowości.

 

Wybieracie oczywiście wariant gdzie suma kosztów będzie najmniejsza a później cały koszt dzielicie na ilość osób. W ten sposób nie ważne, że ktoś przejechał 5 a inni 15 km. Każdy z was zapłaci tyle samo - więc jest sprawiedliwie


  • 1

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską