OptMod-2017/Gyakorlat12
8 királynõ
Írjunk fel egy matematikai modellt, ami megoldja a 8 királynõ problémát (helyezzünk el 8 királynõt a sakktáblán, úgy hogy egyik se üsse a másikat). Oldjuk meg AMPL-ben.
DNS
Hasonló sorozatok helytakarékos tárolása
A DNS-ek feltérképezésének egyik praktikus problémája a hosszú egymástól nem sokban különböző azonos hosszúságú DNS-ek praktikus tárolása. Most egy egyszerűsítsük a problémát bináris sorozatok esetére. Két sorozat között definiált a Hamming-távolság: Sum(i) |a_i - b_i| , azaz azon bitek száma amelyeket át kell billenteni hogy megkapjuk a másik sorozatot. Amíg a Hamming-távolságok nem túl nagyok, érdemes egyetlen sorozatot eltárolni illetve a különbségeket amivel a többi sorozat felírható. Magyarázd el, hogyan lehet ezt minimális feszítőfa keresésével megoldani, illetve add meg a megoldást Excel vagy AMPL segítségével (AMPL előnyben)!
A sorozatok:
- 011100011101
- 101101011001
- 110100111001
- 101001111101
- 100100111101
- 010101011100
