Branch
and bound
Feladatok:
1.
Adott egy 4 x 4-es méretű
mátrix, amely 1-tól 15-ig tartalmazza sor, és
oszlop-folytonosan a
természetes
számokat. Az utolsó sor,
utolsó oszlopában a 0 érték
található, mely azt
jelzi, hogy az a pozíció
üres. Ez hívjuk a mátrix kezdeti
konfigurációjának. Adott,
továbbá a mátrixnak egy összekevert
állapota, melyet a számok jobbra, balra, le, fel,
léptetésével kaptunk.
Egy léptetés azt jelenti, hogy valamely számot az
üres pozícióra léptetünk.
Írjunk programot, mely meghatározza azt a
minimális számú
lépéssorozatot, melyet ebből az összekevert
állapotból kell tenni, hogy visszakapjuk a kezdeti
állapotot.
2. Egy folyó
egyik partján K
számú kannibál, M
számú misszionárius és egy
kétszemélyes csónak található. Írjunk programot, mely
meghatározza a
folyó túlsó partjára való
átkelési sorrendet, betartva a következő
szabályt: mindkét parton
a misszionáriusok száma több vagy egyenlő kell legye
a kannibálok számánál.
Japán
IQ teszt