REKLAMA

Efektywny algorytm Knutha dla problemu Dokładnego Pokrycia i jego zastosowanie w trudnych łamigłówkach

Niejeden z nas grał, a na pewno zna łamigłówki Sudoku czy Polyomino. To drugie od czasu wprowadzenia przez Solomona Golomba wzbudziło zainteresowanie matematyków zajmujących się nauką i rekreacją. Liczne gry – jak np. Tetris czy Ubongo – łamigłówki i nierozwiązane problemy oparte są na tych zachwycających elementach, które powstają przez połączenie wzdłuż krawędzi wielu nie nachodzących na siebie kwadratów jednostkowych...

Zagadnienia poruszane w tym artykule:

  • Problem Dokładnego Pokrycia;
  • Algorytm niedeterministyczny;
  • Algorytm deterministyczny, czyli algorytm brute-force dla problemu ECP;
  • Postać macierzowa ECP;
  • Algorytm X Knutha;
  • Dancing links, Algorytm DLX;
  • Dancing links w działaniu;
  • Przykład rozwiązania Tetromino za pomocą ECP;
  • Przykład rozwiązania Sudoku za pomocą ECP;
  • Testowanie algorytmu i szybkości działania;
  • Monte Carlo w pomiarze szybkości;
  • Czy można jeszcze szybciej...?
  • Algorytm DLX + ZDD;
  • Podstawowy algorytm rozproszony.

Artukuł pochodzi z magazynu Programista nr 96 (2/2021). Jest to wydanie kwiecień/maj 2021 r.

Szczegółowy spis treści wydania nr 96: https://programistamag.pl/programista-2-2021-96/

Autorem artykułu jest Łukasz Grządko. Autor przygodę z komputerem zaczął w wieku 8 lat. Mając 10 lat, programował interaktywne gry video w języku Basic. Uczestnik wielu konkursów matematyczno-programistycznych. Swoje umiejętności matematyczne i informatyczne poszerzył i wzmocnił, kończąc studia na Uniwersytecie Wrocławskim. Zainteresowany teoretycznymi podstawami informatyki i matematyką, algorytmami i strukturami danych oraz inżynierią oprogramowania. Ponadto aktywny uczestnik TopCoder Algorithms od ponad 16 lat. Obecnie pracuje jako Software Development Engineer w technologiach LTE i 5G Mobile Broadband we wrocławskim oddziale Nokii.