Reklama
Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2
Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko

5.08.2015
środa

Polska kwadratowa

5 sierpnia 2015, środa,

Znajoma namówiła mnie do zamieszczenia poniższego zadania, co czynię z pewną taką wstrzemięźliwością, bo jest ono tzw. optimizerem, czyli dłubaniną dla wybrańców lub dla komputerów. Znajoma zmaga się z nim od pewnego czasu i chciałaby mieć pewność, że osiągnęła najlepszy – w tym przypadku najmniejszy – wynik.

Oto mamy Polskę pokratkowaną, czyli podzieloną na małe kwadraciki, a praktycznie narysowaną z grubsza, czyli z „kanciastymi” granicami, na kartce w kratkę.

Pok_1

Czarne kratki to największe miasta wojewódzkie.
Tę Polskę (całą) należy rozparcelować na kwadraty. Dzielić należy oczywiście tylko wzdłuż oznaczonych linii. A najważniejsze jest to, aby kwadratów było jak najmniej. Miasta powinny się znaleźć poza kwadratami, a więc pozostaną kwadracikami 1×1, ale nie są wliczane do końcowego minimum.

Żeby było ciekawiej i dziwniej dodam, że zadanie pochodzi z łamigłówkowych mistrzostw Francji. Dlaczego Francuzi dzielili Polskę – nie powiem. Nie podam także wyniku znajomej, ale jeśli w komentarzach pojawią się gorsze, czyli większe rozwiązania (wystarczy podać liczbę kwadratów), będę je uwalniał bezzwłocznie.

Kom

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 21

Dodaj komentarz »
  1. 65

  2. Napisałem program i uruchomiłem. Program oczywiście przeszukuje wszystkie możliwe podziały mapy na kwadraty, więc na pewno nie pominie najlepszego rozwiązania. Natomiast dzięki optymalizacji mam nadzieję, że program dość szybko będzie odcinał przeszukiwanie gałęzi, które nie mają szans wygenerować rozwiązania lepszego od już znalezionych.

    W chwili obecnej najlepszy znaleziony podział zawiera 63 kwadraty (+ 7 kwadratów symbolizujących miasta). Nie potrafię ocenić, kiedy program skończy swe działanie.

    PS. Pełny podział mapy przedstawię później, bo zakładam, że mogą pojawić się jeszcze lepsze rozwiązania.

  3. Mam rozwiązanie z 60 kwadratami 🙂

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. Ooo… jak pisałem komentarz, to pojawiło się rozwiązanie z 57 kwadratami 😀

  6. Ech… Cofam poprzednie dwa komentarze, bo przeoczyłem subtelny fakt, że w drugiej wersji programu dodałem wypisywanie wyniku, które nie uwzględnia już istniejących 7 miast.

    Zatem mój obecny wynik, to 63 kwadraty 🙁

    Nie uwalniam zawczasu Pańskich komentarzy, choć wyniki są za duże, bo informacja, że w szranki stanął komputer, mogłaby zniechęcić „pieszych” rozwiązywaczy.
    Nawiasem mówiąc, mam wątpliwości, czy dożyję chwili, gdy komputer zakończy pracę :).
    mp

  7. Hehe… Rozumiem. Komputer pracuje, a ja co chwila wymyślam kolejne optymalizacje 🙂

    Oczywiście, jako doświadczony algorytmik, życzę Panu, aby przeżył Pan ten program z nawiązką 🙂

    PS. Tym razem mam już 58 kwadratów 🙂

  8. 55

  9. Mam troszkę niżej: 58.
    Mógłby Pan podpowiedzieć, do czego dążyć – może na przykład wyników powyżej 40 nie ma co podawać? A może ma wyjść 49 województw jak za starych czasów? 🙂

    Antyp1958 jest już blisko minimum, które znam.
    mp

  10. 15

    Nie uwalniam, bo to chyba żart albo rozwiązanie innego zadania (może coś niejasno napisałem).
    mp

    Uwolniłem po wyjaśnieniach.

  11. Może źle zrozumiałem reguły zadania, przeczytałem jeszcze raz i…. wszystko sie zgadza. Oto link do mojego rozwiązania (zajeło mi 5 minut, może jest lepsze jeszcze).
    Z lenistwa, nie zaznaczałem kwadratów jednokratkowych… bo sa już zaznaczone:
    http://s15.postimg.org/86se02g0b/Pok_1_1024x934_kl.jpg

  12. Czytam i czytam… i chyba wiem już gdzie tkwi mój błąd, nie liczonymi kwadracikami 1×1 mogą być tylko miasta.
    Ale swoja drogą powstało inne zadanie 🙂

    „Wpisz w Polskę jak najmniej kwadratów tak, aby nie pozostał żaden większy niż 1×1” – chyba tak brzmi nowe zadanie z rozwiązaniem 15.
    mp

  13. Wbrew pozorom instrukcja do ‚mojego’ zadania nie jest trywialna.
    Zasugerowałbym taką:
    ‚Wypełnij cała mapę kwadratami większymi od 1×1, tak by ich liczba była jak najmniejsza’.

    P.S. Wiedząc o co chodzi, nie potrafię jednak ocenić, czy ta definicja jest optymalna 🙂

  14. A może to podział na JOW-y?
    W pierwszym podejściu mam 62, czyli powiedzmy średnio 😀

  15. No dobra, poddaję się. Mam 57 kwadratów, mniej mi nie chce wyjść 🙁

  16. 52

    Pani Olu, czy Pani uprawia „strzelectwo”:)?
    mp

  17. http://pokazywarka.pl/d53irr/

    Śliczności:)
    mp

    PS Pani Olu, społeczeństwo się pyta, co oznacza gruba pionowa zielona kreska.

  18. Nic takiego 🙂 To pozostałość po roboczym dzieleniu Polski na sektory. Ułatwiała mi pracę i liczenie, ile mam kwadratów w danym sektorze po poprawkach. Dzięki takim liniom (było ich więcej) nie musiałam liczyć wszystkiego od nowa.

  19. Napisał Pan w jednym z komentarzy „minimum, które znam” – jakie jest to minimum?

    Właśnie Pani, jako jedyna, osiągnęła to minimum.
    Dodam, że jest kilka (nie wiem dokładnie ile – chyba koło 10) sposobów podziału Polski na 52 kwadraty. We wszystkich podziały płd. Polski są takie same, różnice występują tylko na Pomorzu :). Na mam pewności, czy podział na mniej niż 52 kwadraty jest niemożliwy.
    mp

  20. Też miałem 52 kwadraty. Jedno z możliwych jest poniżej
    http://pokazywarka.pl/zru9wb/
    Ponieważ znalazłem kilkanaście rozwiązań wykombinowałem, że zejście do 51 jest możliwe (ale chyba nie jest).

  21. Francuzi dzielili Polskę w ramach swoich eliminacji do 19tych World Puzzle Championship – te mistrzostwa odbywały się właśnie w Polsce.

    Ich rozwiązania można znaleźć tutaj:
    https://math.berkeley.edu/~auroux/frwpc10/sol3.pdf

css.php