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

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

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ę.

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.
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.

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.

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

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ć

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"?

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?

0

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

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
0

Wartości pewnej funkcji dwóch zmiennych z = f( x, y ), gdzie x, y, z przyjmują wartości całkowitoliczbowe, przechowywane są w SQLowym
repozytorium danych (w bazie danych) w tabeli o nazwie Ftable. Struktura tabeli utworzona została z wykorzystaniem instrukcji

 
CREATE TABLE Ftable (
x int NOT NULL,
y int NOT NULL,
z int NOT NULL
)
CONSTRAINT [PK_Ftable] PRIMARY KEY
(
x, y
)

Połączenie do SQL-owej bazy danych (dostęp do bazy) realizowany jest z wykorzystaniem driverów JDBC poprzez wykonanie metody
String database = <connection_string>; // gdzie <connection_string> parametr linii komend
Connection conn = DriverManager.getConnection(database);

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 ).

0

Algorytm mógłby wyglądać tak:

  • dla każdego "kwadratu" siatki sprawdzasz, czy jego wierzchołki mają tę samą wartość - jeżeli nie odrzucasz taki kwadrat
  • następnie szukasz największego spójnego obszaru, który tworzą kwadraty nieodrzucone.

W załączniku rysunek, liczby oznaczają wartości f(x, y)

0

@lemmiwink to co opisałeś to jest zasadniczo ta sama konstrukcja o której pisałem wcześniej i moim zdaniem jest poprawna.

0

Jeżeli nie mamy ograniczenia na poszukiwanie to, brak rozwiązań, np: f(x,y) = ceil(log2(abs(x)+1))+ceil(log2(abs(y)+1))
Zaś jeżeli mamy podany obszar poszukiwań to możemy to zrobić w czasie x*y używając tablicy dwuwymiarowej [y,x] oraz programowania dynamicznego.

6

Panowie, prosiłem aby zadania wykonywać samodzielnie !
W takim wypadku będę musiał wyciągnąć konsekwencje.

Pozdrawiam wiosennie.

0

Wiedziałem że jak się doda ograniczenia to zadanie wyjdzie banalne...

Działa z SQLite:

CREATE TABLE Table01 (
  x  integer,
  y  integer,
  z  integer
);

/* Data for table Table01 */
INSERT INTO Table01 (x, y, z) VALUES (2, 2, 2);
INSERT INTO Table01 (x, y, z) VALUES (2, 2, 2);
INSERT INTO Table01 (x, y, z) VALUES (2, 3, 2);
INSERT INTO Table01 (x, y, z) VALUES (1, 3, 2);
INSERT INTO Table01 (x, y, z) VALUES (1, 1, 2);
INSERT INTO Table01 (x, y, z) VALUES (7, 2, 2);
INSERT INTO Table01 (x, y, z) VALUES (1, 3, 2);
INSERT INTO Table01 (x, y, z) VALUES (1, 1, 2);
INSERT INTO Table01 (x, y, z) VALUES (7, 2, 2);
INSERT INTO Table01 (x, y, z) VALUES (0, 3, 12);
INSERT INTO Table01 (x, y, z) VALUES (0, 1, 22);
INSERT INTO Table01 (x, y, z) VALUES (7, 0, 23);
INSERT INTO Table01 (x, y, z) VALUES (7, 12, 21);

select (max(x)-min(x)) * (max(y) - min(y)) as area, 
min(x), max(x), min(y), max(y), z 
from table01
group by z
order by 1 desc
limit 1
0

@vpiotr że niby co tutaj działa? o_O
A co jeśli ta sama wartość Z występuje w zupełnie oderwanych od siebie fragmentach siatki? Na przykład na 4 rogach siatki? To twoj magiczny algorytm zwróci że to Z obejmuje całą siatkę. Good job ;]

2
Shalom napisał(a):

@vpiotr że niby co tutaj działa? o_O
A co jeśli ta sama wartość Z występuje w zupełnie oderwanych od siebie fragmentach siatki? Na przykład na 4 rogach siatki? To twoj magiczny algorytm zwróci że to Z obejmuje całą siatkę. Good job ;]

Ile tu żalu w tej wypowiedzi, ile zawiści. Nie można tak normalnie, bez emocji?

select 
(t2.x - t1.x) * (t2.y - t1.y) as area, 
t1.x, t1.y, t2.x, t2.y 
from table01 t1, table01 t2 
where t1.z = t2.z
and t1.x < t2.x
and t1.y < t2.y
and not exists(
select 1 from table01 t3
where t3.x >= t1.x and t3.x <= t2.x
and t3.y >= t1.y and t3.y <= t2.y
and t3.z <> t1.z
)
order by 1 desc
limit 1

Edit: Wyjaśnienie - poprzednia wersja obliczała obszar największej powierzchni, ale z możliwymi dziurami.
Ta wersja oblicza obszar największego prostokąta obejmującego tylko punkty z jedną wartością.
Jednocześnie odrzuca obszary-punkty i obszary-linie, które nie mają powierzchni (ostre nierówności).

Edit-2: usunąłem min, max.

0

Tak powinienem to interpretować? Max jest dla z =3 o wartości 4?
http://ifotos.pl/zobacz/Beztytuup_nhnhxap.png/

1

To podaje lepszy wynik dla Twojego przypadku testowego:

SELECT 
(t4.x - t1.x) * (t3.y - t2.y) AS area, 
t1.x, t2.y, t4.x, t3.y, t1.z 
FROM table01 t1, table01 t2, table01 t3, table01 t4 
WHERE t1.z = t2.z
and t1.z = t3.z 
and t1.z = t4.z 

AND t1.x <= t2.x
AND t1.x <= t3.x
AND t1.x < t4.x

and t2.x <= t4.x
and t3.x <= t4.x

and t2.y <= t1.y
and t2.y < t3.y
and t2.y <= t4.y

AND NOT EXISTS(
SELECT 1 FROM table01 tneg
WHERE tneg.x >= t1.x AND tneg.x <= t4.x
AND tneg.y >= t2.y AND tneg.y <= t3.y
AND tneg.z <> t1.z
)

ORDER BY 1 DESC
LIMIT 1

Wyjaśnienie:
t1 - lewy skrajny punkt
t2 - górny skrajny punkt
t3 - dolny skrajny punkt
t4 - prawy skrajny punkt

1
jrj napisał(a):

Panowie, prosiłem aby zadania wykonywać samodzielnie !
W takim wypadku będę musiał wyciągnąć konsekwencje.

Pozdrawiam wiosennie.

Lepiej by było gdyby Pan zajął się poprawianiem prac a nie szukaniem rozwiązań w internecie. Z przyjemnością zobaczę wyniki swoich prac :)

Pozdrawiam wiosennie.

0

Zamiast prześladować studentów na ogólnopolskim forum, radziłbym ich czegoś sensownego nauczyć... Nawet ludzie w sensownej pracy wspomagają się róznymi źródłami i to nie jest zabronione, najważniejszą sprawą jest rozwiązanie problemu.

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