Jaunās pasaules meklējumos

Es visu laiku izklaidējos! Vismaz tā jūs noteikti domājat, ņemot vērā mana bloga saturu :)

Manos plānos ir kaut kad uzrakstīt, kas ir kvantu skaitļošana, tas ir, ar ko tad es īsti nodarbojos. Bet ne šoreiz, jo es joprojām nezinu vieglu veidu, kā to paskaidrot. Tomēr tagad es aprakstīšu vienu konkrētu problēmu, kuras atrisinājumam es kaut kā cenšos tuvoties. Lielas ticības tam gan nav, jo, kā teica mans profesors, ja es to atrisinu, es varu vienkārši izvēlēties jebkuru pasaules universitāti un kļūt par profesoru tajā :D Tomēr, jebkurš solis atrisinājuma virzienā (vai arī apzināšanās, kas nedod vēlamo rezultātu) varētu būt noderīgs.

Mērķis: atrast efektīvu algoritmu priekš grafu izomorfisma. Tā kā tas varētu izklausīties pilnīgi nesaprotami, es mēģināšu paskaidrot, ko tas īsti nozīmē.

Grafs ir matemātiska abstrakcija priekš situācijas, kad ir kaut kādi objekti (saukti par virsotnēm), no kuriem katrs pāris ir vai nav savā starpā savienots (ar kaut ko sauktu par šķautni). Piemēram

• virsotnes var apzīmēt pilsētas, un divas virsotnes ir savienotas ar šķautni, ja starp attiecīgajām pilsētām ir ceļš;
• vai, piemēram, virsotnes ir pilsētas ar lidostām, un divas virsotnes ir savienotas ar šķautni, ja starp attiecīgajām pilsētām ir avioreiss;
• virsotnes var apzīmēt portāla draugiem.lv lietotājus, un divas virsotnes ir savienotas, ja attiecīgie lietotāji ir “draugi”.

Grafus ir ērti attēlot grafiski. Piemēram, šis ir grafs:

Kā jau var nojaust, grafiem ir ļoti daudz pielietojumu.

Tātad, kas ir izomorfisms? Iedomājieties, ka mēs paņemam kādu konkrētu virsotni, un tad to “bīdām” kaut kur apkārt, bet visas ar to saistītās šķautnes saglabājās (tā kā tās būtu piesietas šai virsotnei). Divi grafi ir izomorfi, ja mēs varam no viena grafa iegūt otru kaut kā pārbīdot tā virsotnes. Piemēram, grafi

ir izomorfi, jo sekojošās pārbīdes pārveido pirmo par otro.

Savukārt grafi

nav izomorfi. Tas ir tādēļ, ka pirmajam grafam katrai virsotnei eksistē divi “kaimiņi”, kuri ir arī savstarpēji kaimiņi, bet otrajam grafam tas tā nav, un nekādas virsotņu pārbīdes šo īpašību nemaina.

Mūsu mērķis ir atrast algoritmu (darbības priekš datora), kas spēj noteikt vai divi grafi ir izomorfi vai nav, pie tam, var to izdarīt “pietiekami” ātri. Šāda algoritma atrašana būtu pārāk augsts mērķis priekš manis (varbūt kādu dien :D), tāpēc es mēģināju risināt šķietami vieglāku problēmu.

Datora atmiņā grafi parasti netiek uztverti kā grafiskas bildes, bet, piemēram, kā tabulas. Tādēļ ir ļoti ērti kaut kā sanumurēt virsotnes. Divi šādi grafi ar vienādu virsotņu skaitu ir izomorfi, ja eksistē tāds saraksts, kuru virsotni par kuru jāpārbīda, lai no pirmā grafa iegūtu otro. Šķiet, ka tikko rakstīto varētu būt vieglāk saprast ar piemēru. Zemāk dotie grafi ir izomorfi, jo no pirmā grafa var iegūt otro ar pārbīdi 1->6 (virsotni 1 pārbīdām uz vietu 6), 2->3, 3->2, 4->1, 5->5, 6->4:

Mans uzdevums: uztaisīt efektīvu algoritmu, kurš, saņemot divus grafus un konkrētu sarakstu, kas apraksta kaut kādu pārbīdi, noskaidro, vai atkārtojot šo pārbīdi pēc patikas daudz reižu, mēs varam no pirmā grafa iegūt otro. Piemēram, pieņemsim, ka mums ir atkal doti tie paši tikko minētie grafi, un pārbīde 1->4, 2->3, 3->2, 4->6, 5->5, 6->1 . Atkārtojot šo pārbīdi piecas reizes, mēs patiesībā iegūstam jau minēto pārbīdi 1->6, 2->3, 3->2, 4->1, 5->5, 6->4, ar kuras palīdzību no pirmā grafa mēs dabūjām otro:

Sākumā lielākā daļa mēģinājumu uztaisīt šādu algoritmu man bija neveiksmīgi, bet, mēģinot to darīt, vismaz kaut ko jaunu iemācījos. Pirms divām nedēļām, svētdienā, mēs plānojām braukt kāpt klintīs pie Niagāras upes. Sestdienas vakarā čammājoties, sanāca vēlu iet gulēt, bet nākamajā rītā taču agri jāceļas. Guļot gultā un domājot visādas lietas, īsti nesanāca aizmigt. Tad nu es izdomāju, ka jāmēģina domāt kaut kas garlaicīgāks, lai aizmigtu (un tas bieži nostrādā). Sāku domāt par savu pētījumu problēmu :D Bet kā izrādījās tā vietā, lai aizmigtu, pēc divām stundām ap pusčetriem naktī problēma bija atrisināta :)

Tiesa, atrisinājums, manuprāt, ir samērā vienkāršs. Tad nu ir visdrīzāk ir viens no diviem variantiem: vai nu tas ir jau izdarīts iepriekš, vai arī neviens par šādu problēmu iepriekš nav interesējies. Tā kā manam profesoram ir daudz kontaktu, tad nu viņš mēģinās noskaidrot. Un vispār šķiet, ka mans profesors ir vairāk iepriecināts par manu sniegumu līdz šim, kā es pats. Man šķiet, ka man jādara vairāk.

P.S. Tas, ka algoritms strādā pietiekami ātri (jeb efektīvi), nozīmē, ka tas strādā polinomiālā laikā (no grafa virsotņu skaita). Bet es diemžēl atturēšos šeit skaidrot ko tas īsti nozīmē.