Problema interesanta cu harta

Don Knuth lucreaza la volumul 4 al artei de programare pe calculator. Unul dintre capitole se refera la Diagramele binare si la aplicatiile lor, un subiect pe care il consider foarte interesant. Knuth arata ca o varietate de probleme grafice interesante pot fi codificate ca formule booleene, iar BDD derivat reprezinta toate solutiile posibile ale problemei. Deseori exista un fel de criteriu de optimizare si este destul de usor sa extrageti cea mai buna solutie din BDD printr-un algoritm simplu de programare dinamica.

Aici vom arata cateva exemple, folosind graficul reprezentând cele 48 de state, cu un nod pentru fiecare stare si o margine intre doua state daca impartasesc o frontiera. Pentru fiecare dintre harti, daca faceti clic pe imaginea sa, veti ajunge la documentul sursa in format SVG. Iata graficul, localizand nodurile capitalelor statelor:

Tururi de capitale

Sa presupunem ca doriti sa vizitati capitala celor 48 de state cu cerinta ca treceti numai prin fiecare stat o data. (Cu alte cuvinte, doriti sa gasiti o cale Hamiltoniana in grafic.) Dupa cum puteti vedea din harta de mai sus, daca urmati ruta cea mai directa dintre capitalele de stat, veti trece adesea printr-un alt stat sau, in cazul in care mergeti din Lansing, Michigan la Madison, Wisconsin, veti conduce prin Lacul Michigan. In schimb, ar trebui sa luati cel mai scurt traseu de conducere care se afla in cele doua state pentru fiecare pas al calatoriei. Sa numim un astfel de traseu un turneu de capital. Iata o diagrama a rutelor admise intre stari:

Pe baza unei simple analize, precum si eforturilor lui Knuth, putem spune urmatoarele:

• Toate traseele trebuie sa inceapa sau sa se termine in Maine, deoarece Maine are doar un singur vecin. Vom folosi Maine ca punct de plecare.
• Toate traseele trebuie sa se termine dincolo de New York, deoarece este un punct de articulare.
• Exista 68.656.026 trasee de capitala diferite.

Aici este cel mai scurt tur de capitale, totalizand 11.698 mile:

Aici este cel mai lung tur de capitale, totalizand 18,040 mile:

Culoarea graficului

O alta clasa de probleme interesante implica colorarea hartii. Regula este ca doua state adiacente nu pot avea aceeasi culoare. Celebra teorema de patru culori afirma ca orice grafic planar poate fi colorat cu cel mult patru culori.

Pentru ca un BDD codifica toate solutiile posibile la o formula booleana, putem calcula cu usurinta cate solutii exista. Pentru colorarea graficului, ne ajustam numerele pentru a elimina simetriile datorita alocarii arbitrare a valorilor culorilor (4 cazuri simetrice pentru 4 culori).

Pentru colorarea celor 48 de state invecinate, exista 533 816 322 048 de coloranti posibili. (Acesta este 1/2 numarul raportat de Knuth, deoarece harta lui include Washington, DC ca al 49-lea "stat", si poate fi atribuit oricare dintre cele doua culori care nu sunt utilizate pentru Maryland si Virginia.) Iata cateva exemple interesante de Culori speciale:

• O colorare echilibrata, in care fiecare culoare este utilizata pentru exact 12 stari. Exista 12.554.677.864 astfel de coloranti, ceea ce reprezinta un surplus de 2,4% din toate culorile posibile.

  

• O colorare neechilibrata, in care una dintre culorile (verde) este utilizata cat mai putin posibil (2 stari). Exista doar 288 moduri de a culori harta astfel incat o culoare sa fie utilizata doar de doua ori.

  

• O colorare neechilibrata, in care una dintre culori (galben) este utilizata cat mai mult posibil (18 stari). Exista 71.002.368 cai de colorare a hartii astfel incat o culoare sa fie utilizata de 18 ori.

  

• Combinand ambele. Culori cu culori 2, 13, 15 si 18 de ori. Aceasta secventa 1) de la stanga la dreapta, foloseste fiecare culoare succesiv pentru cel mai mic numar posibil de ori si 2) de la dreapta la stanga, foloseste fiecare culoare succesiv pentru cel mai mare numar de ori. Există 24 de astfel de solutii.

  
  Din perspectiva programelor de colorare a graficelor, harta Statelor Unite ale Americii 48 este destul de simpla. Pentru o harta mai dificila, consultati pagina web de pe graficul McGregor.

Ultima modificare: Marti Ianuarie 19 07:48:18 EST 2010