Érdekes

Érdekes Térkép problémák

Don Knuth dolgozik 4. kötet az Art of Computer Programming. Az egyik fejezetek a bináris döntési diagramok és alkalmazásaik, a téma, hogy találom nagyon érdekes. Knuth azt mutatja, hogy számos érdekes grafikon problémák kódolható, mint logikai formulák, és az ebből származó BDD képviseli az összes lehetséges megoldást a problémára. Gyakran van valamilyen optimalizálási feltétel, és ez elég könnyen kivonat a “legjobb” megoldás a BDD egyszerű dinamikus programozási algoritmus.

Itt megmutatjuk néhány példa segítségével a grafikon, amely a 48 összefüggő állapotok, a csomópont minden állam, és egy él két állapot között, ha megosztják a határon. Az egyes térképek, ha rákattint a képre, hogy akkor éri el a forrás dokumentum SVG formátumban. Itt látható a grafikonon, helyüket a csomópontok a főváros a kimondja:

Fővárosa Utak
Tegyük fel, hogy azt szeretnénk, hogy látogasson el a 48 állam fővárosa a követelmény, hogy csak áthaladnak az egyes állami egyszer. (Más szóval, meg akarja találni a Hamilton út a grafikonon.) Mint látható a fenti térképen, ha követi a legközvetlenebb útvonalat az állami fővárosok, akkor gyakran átmennek egy másik állam, vagy abban az esetben, haladva Lansing, Michigan Madison, Wisconsin, akkor hajt át a Michigan-tó. Ehelyett meg kell venni a legrövidebb útvonal használata, hogy belül marad a két állam minden az út egy szakaszán. Nevezzük egy ilyen útvonal a Capital Tour. Itt van egy diagram a megengedhető közötti útvonalakon kimondja:

Alapja egy egyszerű elemzés, valamint Knuth erőfeszítéseit, azt mondhatjuk, a következő:

Minden túra kell kezdeni, vagy vége a Maine, mivel Maine csak egyetlen szomszéd. Fogjuk használni Maine kiindulási pontként.
Minden túra véget kell túl New York, mivel ez egy csuklópontjának.
Vannak 68.656.026 különböző tőke túrák összességében.

Itt a legrövidebb tőke túra, összesen 11.698 mérföld:

Itt látható a leghosszabb Capitol túra, összesen 18.040 mérföld:

Gráfszínezést
Egy másik érdekes probléma osztályt magában színezés a térképet. A szabály az, hogy nincs két szomszédos államok azonos színű. A híres Four Color tétel kimondja, hogy minden síkbeli gráf színezhető, legfeljebb négy színben.

Mivel a BDD kódol minden lehetséges megoldást egy logikai formula, akkor könnyen kiszámítja, hogy számos megoldás létezik. Mert gráfszınezés, korrigáljuk a számít, hogy megszüntesse a szimmetriák miatt önkényes, szín értékek (4! Szimmetrikus esetben 4-színezés).

Színezéséhez az egybefüggő 48 állam, vannak 533816322048 lehetséges színezékeket. (Ez 1/2 száma által jelentett Knuth, hiszen a térkép tartalmaz Washingtonban a 49. “állam”, és hozzárendelhető a két szín nem használt Maryland és Virginia.) Itt van néhány érdekes példát speciális színezőanyag:

Kiegyensúlyozott színezés, amelyben minden színt használja pontosan 12 állam. Vannak 12554677864 ilyen színezékek, ami meglepően magas 2,4% -a az összes lehetséges színezékeket.

Egy kiegyensúlyozatlan színezés, amelyben az egyik szín (zöld) használunk a lehető legkisebb (2 Államok). Már csak 288 módja, hogy színes a térkép úgy, hogy az egyik szín hozzászokik csak kétszer.

Egy kiegyensúlyozatlan színezés, amelyben az egyik szín (sárga) használunk, amennyire csak lehetséges (18 Államok). Vannak 71002368 módon, hogy színes a térkép úgy, hogy az egyik szín hozzászokik 18 alkalommal.

Egyesíti mind. Színezékeket használva a színeket 2., 13., 15., és 18-szor. Ez a sorrend 1) balról jobbra, használja az egyes színek egymás számára a lehető legkevesebb számú alkalommal, és 2) jobbról balra, használja az egyes színek egymás számára a lehető legtöbb számú alkalommal. Jelenleg 24 ilyen megoldásokat.

Szemszögéből gráfszınezés programok, a térkép az amerikai 48 állam meglehetősen egyszerű. A nagyobb kihívást térképet lásd a weboldal a McGregor Graph.

Eredetileg a http://www.cs.cmu.edu/~bryant/boolean/. Menj a honlapon http://www.forallworld.com