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
