Algoritmus
Nyers erő
Az ismétléses permutáció algoritmusával legyártjuk az összes esetet, és mindegyikre megnézzük, hogy teljesül-e a Langford tulajdonság. Vigyázat!!! L[10] kiszámításához
$\frac{20!}{2^{10}}=2~375~880~867~360~000$ esetet kell megnéznünk.
Hatékonyabban
Nem érdemes minden permutációt megvizsgálni, hiszen például az
11232...
kezdetű sorozat biztos nem felel meg, bárhogy is folytatjuk. Ha a kezdőszeletekre tesztelni akarjuk a Langford-tulajdonságot, akkor az előző algoritmus már nem alkalmas a keresés vezérlésére.
Visszalépéses kereséssel (back-track) tudjuk lemetszeni a keresési fa rossz ágait.
Nagyon hatékonyan
Egy megfelelő permutációt keresve nem csak akkor tudjuk, hogy a vizsgált kezdőszelet rossz, ha van benne két azonos szám rossz távolságra, hanem akkor is, ha egy szám első előfordulásától "jobbra" már nincs elég hely. (Pl. az első 10-es után még 4 számnak van hely, nem lehet a második 10-es tőle 10 lépésre.)
Leggyorsabban?
Ha "lerakjuk" az első k-t, akkor meghatároztuk a másik k helyét is.
Érdemes tehát eleve a párokat pakolni az üres helyekre, a Langford-szabály szerint.
Így az úgynevezett pontos fedés feladat (Exact Cover Problem) egy variánsát kapjuk, ami 16-nál kisebb n-ekre már gyorsan elintézhető. (Nagy input esetén továbbra is reménytelen a dolog, a pontos fedés probléma NP-teljes.)
Kódok
Főoldal
>
Szakkörök
>
BDG Szakkör
>
2008/2009
>
2. óra - Permutáció
>
Langford permutációk
>
Megoldás
