matematyczna lingwistyka

spook · Post autor: **spook** » 7 wrz 2011, o 00:30

na poczatek witam wszystkich pasjonatow matematyki.
jako ze jestem w tej dziedzinie totalnym laikiem, z gory przepraszem za niejasnosc przekazu, i brak polskich znakow.

otoz natrafilem na problem ktory jak mi sie wydaje jest natury geometrycznej.

dany jest prostokat ktorego b=2a (nazwijmy go gienek),
oraz 21 kol o promieniu = (1/25 a) wewnatrz gienka.
10 z tych kol to zenki a 11 z nich to benki.
poruszaja sie one we wszystkich mozliwych kierunkach na plaszczyznie gienka,
lecz nie moga sie ze soba zetknac (ani zenki z zenkami ani zenki z benkami, ani benki z benkami)
moim celem jest znalezienie wzoru(funkcji?), ktory powie mi,
jak powinny poruszac sie benki aby kazdy z nich zachowywal maksymalna odleglosc od najblizszego zenka.

Czy jest ktos tak mily na forum, aby pomoc mi w tym zbitku humanistycznej papki przedstawic moja zagadke na jezyk matematyki?

józef92 · Post autor: **józef92** » 7 wrz 2011, o 09:18

To żeś problem sobie wymyślił. Na pewno nie jest to proste, o ile wykonywalne.

xiikzodz · Post autor: **xiikzodz** » 7 wrz 2011, o 09:52

To wygląda na problem NP-trudny. To znaczy nawet jeśli obiekty poruszają się po siatce jedynie góra dół lewo prawo, zawsze o ustalony dystans, to znalezienie jednego optymalnego ruchu dla wszystkich obiektów jednocześnie jest prawdopodobnie NP-trudne. Mowa oczywiście o algorytmie. Z uwagi na to, że takie optymalne ruchy można dowolnie dokładnie aproksymować ruchami po odpowiednio drobnej siatce, wyjściowy problem jest nie łatwiejszy. Pewnie istnieją jakieś programy do tego np. stosowane na stadionach. A jeśli nie istnieją, to pewnie ktoś nad nimi pracuje. Tak spekuluję sobie w każdym razie.