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.

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