NézetNyomtat

8. óra
Címkék > Óra

8. óra

Pontos fedés
Jól használható a backt-track a pontos fedés problémájának megoldásához. Itt egy adott alakzatot kell előre adott alakzatok példányaival lefedni hézagmentesen és átfedés nélkül.
D. E. Knuth megoldása: a fedéshez használható alakzatok minden lehetséges helyzetéhez előállítjuk a lefedendő alakzat mezőinek azt a részhalmazát, amiben pont azok a mezők vannak, amelyeket az alakzat az adott helyzetben fed. Ezek után a részhalmazok egy olyan halmazát keressük, amelyek diszjunkt uniója az eredeti (teljes) mezőhalmaz.
Általánosságban ez a feladat "nehéz" (NP-teljes), konkrét esetekben okosan gyorsított visszalépéses kereséssel megoldható lehet.

A "Dancing Links" (DLX) algoritmus feladat-reprezentációja

Egy fedés és a hozzá tartozó részhalmazok

Egy "csempe" összes lehetséges helyzete és az ezekhez tartozó részhalmazok

Feladat