Jakiego algorytmu można do tego użyć?

Odpowiedz Nowy wątek
2013-04-20 23:21
0

Witam zastanawiam się czy jest jakieś odzwierciedlenie w algorytmach i strukturach danych dla następującego problemu:

Mamy wartości pewnej funkcji dwóch zmiennych z = f( x, y ), gdzie x, y, z przyjmują wartości całkowitoliczbowe. Należy obliczyć (wyznaczyć) powierzchnię największego obszaru płaskiego. Przez ‘obszar płaski’ rozumiemy pewien obszar O w którym
dla każdej pary x i y leżącej wewnątrz obszaru O wartość funkcji jest stała ( z = const ).

Z góry dzięki

Pozostało 580 znaków

2013-04-21 10:06
0

IMO, zadanie jest źle sformułowane i rozwiązanie nigdy nie istnieje. Każdy znaleziony obszar płaski można powiększyć o obszar nie zawierający żadnej pary (x,y), np. o koło, które ma środek w punkcie (n+1/2,k+1/2) i promień 1/2 (k i n to liczby całkowite). Nowy obszar jest nadal płaski i ma większą powierzchnię.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 1x, ostatnio: bogdans, 2013-04-21 11:15

Pozostało 580 znaków

2013-04-21 11:20
0

@bogdans ale czemu miałoby nie mieć rozwiązania?
Ja rozumiem że wymiary "siatki" są zadane? Możesz wygenerować graf przechodząc po wierzchołkach takim niby BFSem:

  • startujesz w jakimś punkcie a potem rozchodzisz się robiąc x-1, x+1, y-1, y+1, ale przechodzisz dalej tylko jeśli wierzchołek na którym masz stanąc ma takie samo z jak ten z którego wychodzisz
  • każdy wierzchołek na jaki trafisz w ten sposób odpowiednio markujesz
  • jeśli nie możesz przejść dalej to startujesz z kolejnego nieodpowiedzonego jeszcze wierzchołka
  • na koniec sprawdzasz który podgraf ma najwięcej wierzchołków i voila.

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
@Shalom, bo nie ma. Pytanie jest o maksymalna powierzchnię. Jakie jest rozwiązanie dla siatki złożonej z jednego punktu (0,0)? - bogdans 2013-04-21 12:16

Pozostało 580 znaków

2013-04-21 11:28
0

Wydaje mi się, że jednak można. Skoro x i y są całkowitoliczbowe, to najmniejszy obszar płaski, jaki może istnieć w tej sytuacji tworzą 4 punkty, takie, że [x][y] = [x + 1][y] = [x][y - 1] = [x + 1][y - 1]. Wystarczy teraz policzyć ile takich "jednostek" przylega do siebie, aby znaleźć pole pewnego obszaru płaskiego.

A trzy punkty nie tworzą obszaru płaskiego ? - _13th_Dragon 2013-04-21 15:15

Pozostało 580 znaków

2013-04-21 11:41
0

Brak rozwiązania - z kilku względów:

  • brak ograniczenia zakresu liczb
  • funkcja nie musi być różnowartościowa ani wzajemnie jednoznaczna (bo są stałe obszary)
  • czyli za płaskim obszarem również może być płaski obszar - kółko o grubości n i promieniu r w innym kółku)

Słyszałem różne cuda o teorii grafów, ale w czymś takim raczej nie pomogą. Nawet Monte Carlo by nie pomogło.


Szacuje się, że w Polsce brakuje 50 tys. programistów
edytowany 2x, ostatnio: vpiotr, 2013-04-21 11:44

Pozostało 580 znaków

2013-04-21 11:52
0

@vpiotr x i y muszą być całkowitoliczbowe, więc obszar płaski zawsze będzie składał się z kwadratów jednostkowych - o żadnych kółkach nie ma mowy

Pokaż pozostałe 2 komentarze
OK, źle to sformułowałem. Kwadratowe kółko w kwadratowym kółku. Lepiej? - vpiotr 2013-04-21 12:03
a czy to "kwadratowe kółko" będzie miało współrzędne należące do funkcji f? - lemmiwink 2013-04-21 12:06
tak, przykład (fioletowe to wartości stałe, białe - zmienne): http://tinypic.com/r/257kg47/4 - vpiotr 2013-04-21 12:08
hmmm, ciężko mi coś z tego wywnioskować - mógłbyś to opisać? - lemmiwink 2013-04-21 12:12
Proszę na przykładzie, powiedz jaki największy plaski obszar dla f(x,y) = ceil(log2(abs(x)+1))+ceil(log2(abs(y)+1)) pogadamy kiedy podasz wynik - _13th_Dragon 2013-04-21 15:21

Pozostało 580 znaków

2013-04-21 11:53
0

Ograniczenia jeśli chodzi o ilość to mam z góry zadaną i znaną. Jeśli to z grafem i podgrafem jest jedynym rozwiązaniem to ciężko będzie mi to zaimplementować

To może podaj to ograniczenie, będzie łatwiej odpowiadać. - vpiotr 2013-04-21 11:57
Miałem na myśli, że jest skończona ilość tych punktów. Nie wiem ile ich będzie. Może być ich 20 100 albo 1000 - damiannno 2013-04-21 12:14
Siatka składa się z jednego punktu (0,0) (funkcja jest nieistotna), jakie jest Twoim zdaniem rozwiązanie? - bogdans 2013-04-21 12:21

Pozostało 580 znaków

2013-04-21 12:00
szewczykus
0

A czy, przy tak sformułowanym problemie, maksymalna powierzchnia tego obszaru płaskiego to "nieskończoność odjąć te punkty dla których z!=const"?

Pozostało 580 znaków

2013-04-21 12:30
0

A gdyby tak brać punkty dla najmniejszego y oraz x potem dla najmniejszego y i największego x i potem na odwrót czyli dla max y i min x i max y max y? Mielibyśmy wtedy jakiś czworokąt prawda? Potem by się ten czworokąt podzieliło na dwa trójkąty i obszar policzony dla danego z=const;P Co o tym sądzicie?

edytowany 1x, ostatnio: damiannno, 2013-04-21 12:32

Pozostało 580 znaków

2013-04-21 12:39
0

Podaj dokładną treść zadania, to z pierwszego postu nie ma rozwiązania.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
Na następnej stronie masz dokładną treść. Nic nowego ona nie wniesie chyba - damiannno 2013-04-21 12:50
To zadanie nie ma rozwiązania, dodatkowo zwrot dla każdej pary x i y leżącej wewnątrz obszaru O wartość funkcji jest stała jest bez sensu. - bogdans 2013-04-21 13:03

Pozostało 580 znaków

2013-04-21 12:42
0

@lemmiwink: "złośliwa" funkcja testowa:

fioletowe to wartości stałe, białe - zmienne: http://tinypic.com/r/257kg47/4

f(x,y) = 
x = -1; -1 <= y <= 1 => 2,
x = 1; -1 <= y <= 1 => 2,
-1 <= x <= 1; y = -1 => 2,
-1 <= x <= 1; y = 1  => 2,

x = -3; -3 <= y <= 3 => 2,
x = 3; -3 <= y <= 3 => 2,
-3 <= x <= 3; y = -3 => 2,
-3 <= x <= 3; y = 3  => 2,

inaczej => f(x,y) = x*y

Szacuje się, że w Polsce brakuje 50 tys. programistów
Pokaż pozostałe 7 komentarzy
Inaczej rozumiemy termin obszar płaski, ja rozumiem, że obszar jest płaski jeśli funkcja w nim jest stała, a Ty jakoś inaczej. Termin płaski wziął się chyba ze szczególnego przypadku gdy funkcja f jest wysokością npm. - bogdans 2013-04-21 13:32
rozumiemy tak samo - tylko, że w tym przypadku funkcja jest określona tylko w "oczkach" siatki - lemmiwink 2013-04-21 13:33
To jest oczywistą oczywistością, że jeżeli obszar zawiera tylko jeden punkt z siatki (nie zawiera żadnego punktu), to funkcja jest w tym obszarze stała. - bogdans 2013-04-21 13:36
jeżeli obszar nie zawiera żadnego punktu to jak funkcja w tym obszarze mże być stała? - lemmiwink 2013-04-21 13:44
Są dwie możliwości: funkcja jest stała, funkcja nie jest stała. Która alternatywa bardziej Ci odpowiada? Formalnie: funkcja f jest stała w dziedzinie D, jeżeli dla każdych a,b z dziedziny D f(a) = f(b). Dla pustej dziedziny ten warunek jest spełniony. Żeby nie bawić się w formalizmy matematyczne proponowałem obszar, który zawiera dokładnie jeden punkt z siatki. - bogdans 2013-04-21 17:47

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0