OptMod-2017/Gyakorlat12

Kkovacs (vitalap | szerkesztései)
(Új oldal, tartalma: „== 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 …”)
Újabb szerkesztés →

---

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:

1. 011100011101
2. 101101011001
3. 110100111001
4. 101001111101
5. 100100111101
6. 010101011100