Zadatak dana: kineski poštar

Na Chinese postman problem prvi put sam naletio na jednom IBT-u gdje je postavljena verzija tog problema koja je dopuštala rješenje u O(2N · M) koje sam tada smislio i oduševio se tim rješenjem.

Iako je problem rješiv i u O(N3) kao što je objašnjeno na Wikipediji (to rješenje trebate implementirati ako želite naučiti weighted matching), meni se ovo prvo rješenje daleko više sviđa jer je lijepo/neobično i zahtijeva manje znanja. Napisao sam ga ovdje ispod, bijelom bojom (SPOILER!).

Ako graf ima Eulerov ciklus (zatvoreni put koji točno jednom prolazi svakim bridom), on je optimalno rješenje. Inače je potrebno duplicirati neke bridove sa što manjom ukupnom težinom (to su bridovi kojima ćemo proći dvaput) tako da rezultirajući multigraf ima Eulerov ciklus, a to će biti onda kada svaki vrh bude imao paran stupanj. Promatrajmo bitmasku parnosti stupnjeva svih vrhova, za koju želimo da na kraju bude 000…00. Dupliciranje nekog brida mijenja parnosti njegovih vrhova pa dobivamo neku drugu bitmasku. Rješenje je, dakle, Dijkstrinim algoritmom naći najkraći put od početne bitmaske do nul-maske u novom grafu čiji su vrhovi bitmaske — njih je najviše 2N, što je dovoljno malo za N ≤ 15.

Ljepota rješenja je u tome što se problem na grafu rješava konstrukcijom sasvim novoga grafa.

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google+ photo

Ovaj komentar pišete koristeći vaš Google+ račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s