Kiedyś dostałem takie zadanko:
Dla chętnych pomysł gdzie/jak umieścić statek kosmiczny.
edit: zakładając że pytanie jest statystyczne:
Zgadywałbym że w rogu, bo masz najwięcej odległej przestrzeni.
Analogicznie w samym środku będziesz średnio "najbliżej" bo do najdalszej bomby byłoby nie więcej niż 500 jednostek w każdym wymiarze.
Ja bym dopytał jaka metryka odległości i jaki rozkład prawdopodobieństwa i czy 3d coś znacząco zmienia.
@Shalom: powiedzmy w rogu 1,1,1 - a co jak bomba jest 2,2,2?
W samym środku bomba może być blisko. Trzeba policzyć tak, żeby było najkorzystniej - czyli jak najdalej od pewnego zestawu bomb.
Czyli jak najdalej od zestawu najbliższych bomb.
@yarel 3D niewiele zmienia bo można operować na 2D +1 wymiar.
Generalnie chodzi o pomysł jak to rozwiązać, policzyć.
Nie znam rozwiązania ale szedłbym takimi:
wydaje mi się, że to może mieć coś wspólnego z k-nearest neighbors, ale nie pamiętam jak się to liczyło i nie mam pomysłu, jak konkretnie to zrobić.
w każdym razie wydaje mi się, że ten problem należy rozwiązać w jakiś przybliżony sposób, może to knn, może inny podobny algorytm z nurtu machine learning.
sprawdzić wszystkie miejsca (przejść całą przestrzeń = 1 000 000 000) i dla każdego liczyć odległość do bomb
Choć w sumie miliard to nie jest wcale tak dużo, żeby po prostu przeliczyć to na pałę.
No ale co jeśli punktów będzie 100 miliardów, a bomb będzie 100 tysięcy? I będziesz musiał to liczyć ileś razy na sekundę? Więc liczenie na pałę nie będzie się skalować.
a co jak bomba jest 2,2,2?
Ale ty pytasz o algorytm czy to pytanie statystyczne bo różnica jak między piciem w Szczawnicy a szczaniem w piwnicy :D
Jeśli pytanie jest statystyczne to dowód anegdotyczny nie ma zadnego sensu. Zawsze możesz trafić wszystkie bomby dookoła siebie xD
Ustawienie się w rogu ma sens bo odległość do każdej bomby będzie losową wartością 0...1000, więc średnio odległość będzie 500 w każdym wymiarze. Analogicznie na środku odległość do bomb będzie 0...500 w kazdym wymiarze więc średnio 250 w każdym wymiarze.
Jeśli pytanie jest algorytmiczne to liczysz sobie Wieloboki Voronoi.
edit: swoją drogą as far as possible from all the bombs jest niejasną definicją. Co to znaczy? Że średnia odległość ma być największa? Że mediana? Że najmniejsza odległość na być maksymalnie duża? Jeśli wszystkie bomby są w jednym rogu a jedna bomba w przeciwległym rogu to najlepszą pozycją jest środek czy może róg z bombą?
Jeśli założymy że najmniejsza odległość ma być jak największa, to wieloboki Voronoi się tu sprawdzą idealnie.
Kojarzy się mediana geometryczna.
Najpierw znajdź ten punkt, a potem znajdź punkt najbardziej od niego oddalony, który ciągle jest wewnątrz ograniczonego obszaru. Logika by była, że w tej medianie obrywasz najmocniej, więc im dalej od niej tym lepiej. Aczkolwiek nie wiem, czy na pewno to poprawne rozwiązanie.
@Shalom: pytam o rozwiązanie zadania/problemu. Bomby, jak jest napisane, są rozrzucone losowo, przyjmij że takich losowań od nowa jest 1000 i chodzi o to, żeby w takiej sytuacji zawsze znaleźć najbezpieczniejsze miejsce. Wieloboki... Ok, to chcesz rozwiązać zadanie, czy pochwalić się, że niby wiesz w którym kierunku iść?
Co do edit: ma być tak, żeby statek kosmiczny był jak najbardziej bezpieczny przy jednoczesnym wybuchu wszystkich bomb. Nie szukaj dziury w całym.
@Spearhead podobny problem jak Shalom - dajmy na to 9 bomb jest na prawie granicach przestrzeni, a jedna w środku, więc generalnie dostaniesz się obok bomby.
Krawędzie wieloboków w diagramie Vornoi są równo oddalone od bomb. Rozwiązanie nie może leżeć wewnątrz wieloboku voronoi, bo jest bliżej położony do pewnej bomby niż najbliższa krawędź wieloboku. Ponadto rozwiązanie leży w jednym z wierzchołków któregoś z tych wieloboków, bo jest bardziej oddalony od pewnej pary bomb niż wszystkie inne punkty na danej krawędzi.
Ja bym poszedł metodą gradientu (gradient descent, steepest descent).
Mając dane 10 pozycji bomb, wyznaczam funkcję sumy odległości euklidesowej od nich wszystkich d. Losuję punkt, a następnie wyznaczam pochodne cząstkowe po x, y, z, po których funkcja wzrośnie najbardziej. Idę wzdłuż wektora o jednostkę odległości, a następnie powtarzam.
@pikob: pochwal się później gdzie to była rekrutacja i jak ci poszło. Moze tym razem rekruter odpisze po weryfikacji technicznej :)
GutekSan pisze:
"ustaw rakietę tak, by zniszczenie od bomb było najmniejsze, wiedząc że siła niszczenia jest odwrotnie proporcjonalna do odległości"
Dokładnie o to chodzi. Ale bez liczenia kwadratu odległości, wystarczy sama odległość.
Zakładamy że fale wybuchów nie interferują.
EDIT: "chodzi o największą odległość od najbliższej bomby".
@pikob ok czyli chodzi dokładnie o to o czym pisałem ja i @Zing w takim razie, nie o to o czym pisał @GutekSan Rozwiazaniem jest policzenie https://pl.wikipedia.org/wiki/Diagram_Woronoja i wybraniem punktu, dla którego najmniejsza odległość będzie największa.
Czyli:
Shalom napisał(a):
@pikob ok czyli chodzi dokładnie o to o czym pisałem ja i @Zing w takim razie, nie o to o czym pisał @GutekSan Rozwiazaniem jest policzenie https://pl.wikipedia.org/wiki/Diagram_Woronoja i wybraniem punktu, dla którego najmniejsza odległość będzie największa.
Moim zdaniem zadanie jest nieścisłe.
pomijając jużto, że przestrzeń 1000x1000x1000 nic tu ani nie ułatwia ani nie utrudnia równie dobrze mogło być założone, że jest po prostu ograniczona np. zakresem od 0 do 1 na każdej osi. W samych obliczeniach to i tak niewiele zmienia. Chyba, że mamy zakaz używania liczb zmiennoprzecinkowych :-)
Teoretycznie to co piszesz to pierwsze co przychodzi na myśl. Jednak ze zdania place one spaceship as far as possible from all the bombs, as when they will explode at the same time, the spaceship will remain as fine as possible. nie wynika jaka jest zależność między uszkodzeniami a odległością od bomby.
Jeśli "ilość uszkodzeń" maleje z kwadratem odległości to będzie zupełnie co innego niż w przypadku gdy maleje liniowo.
Nigdzie w warunkach zadania nie jest napisane, że statek ma znajdować się wewnątrz tej przestrzeni. Bomby i owszem tak. Należy umieścić go więc w nieskończonej odległości od dowolnego jej punktu. Dziękuję za uwagę, można się rozejść.
A może w zadaniu chodzi o rozważenie też metody "brute force", skoro przestrzeń jest dyskretna. Powiedzmy, że minimalizujemy sumę odwrotności odległości euklidesowych od wszystkich bomb. Jakieś 100 mld operacji zmiennoprzecinkowych, o ile nie mam pomroczności teraz - pesteczka przy laptopach zalecanych "na studia" tu na forum. ;)
Dyskusja doskonale ilustruje stosowanie common sensu do wymagań biznesowych. "Jak to o co innego chodziło? Przecież rozsądek podpowiadał, że właśnie o to" ;) Op powinien doprecyzować wątpliwe obszary i wtedy można działać.
Napisałem algorytm, który to liczy, ale jest zbyt skomplikowany i i tak nikt go tu nie zrozumie, więc nawet nie wrzucam. Wyszło mi [0, 0, 0].
Nie myślałem zbyt długo nad tym problemem ale ja bym zaczął od opracowania rozwiązania w 2D dla dwóch bomb...Potem trzeba pomyśleć jak to zoptymalizować.
Może chodzi o utworzenie drzewa kd.