Laiuti otsing

Laiuti otsingut saab rohkem kui ühte moodi kirjutada, näiteks on lineaaralgebraline laiuti otsing, mis on teada umbes 1970 aastast, kuid mida pole eriti kasutatud, kuna maatriksi kujul graafis otsimine ei ole siiani olnud effektiivne ei ajas ega ruumis.

Seoses täiesti mõttetu teemaga – moore-i seadus ei tööta – on 2016 uus 1970. Laiuti otsing on sellisel kujul R = AT x, kus A on graaf(tavaline adjacency matrix) ja x on vektor, mis näitab kus otsing toimub, pannes sinna number ühe. R annab sellisel kujul antud kõrgusel oleva tipu naabrid. Tegelikult palju lihtsam kirjutada ja paralleelne  – vektoriseeritav ja suudab kasutada olemasolevaid hajusaid maatrikseid.

BFS üldine probleem ongi suured graafid ja suure hulga mälu tarbimine, sest BFS salvestab kõik eelnevad sügavuselt väiksemad tipud, kui kasutada seda graafis otsinguks, siis on mälu endiselt probleem, kuid kiiruselt paremaid lahendusi on võimalik leida.. TL;TR; Graph algorithms in the language of linear algebra.

Üks mälu säästev laiuti otsingu algoritm on Divide and Conquer BFS, kus mälu kasutatakse ainult O(lg n), aeg siis O(n^3). 2001 aastal vist alles mõeldud selline üllitis antud lingi järgi.

Kirjas hetkel siin lingil https://books.google.ee/books?id=qkFsCQAAQBAJ&pg=PA171&lpg=PA171&dq=log+n+space+BFS&source=bl&ots=Ma9y04537Q&sig=MsvANB8AxeKq_kYFY11yBtqAzq8&hl=et&sa=X&ved=0ahUKEwiHrLKBlbTOAhWDjSwKHcXvAvcQ6AEINTAD#v=onepage&q=log%20n%20space%20BFS&f=false

Veel üks moodus kuidas BFS kirjutada on IDS. See on üks sügavuti otsingu variantidest, kus piiratakse otsingu sügavust. Samuti mälu suhtes efektiivne.

Lõpuks on https://en.wikipedia.org/wiki/Breadth-first_search e. tavaline BFS, mida kasutatakse kõige rohkem minuarust. Tüüpiline O(b^d) ajaline keerukus tähendab, et lahend on d sügavusel, mis võib tähendada, et d on lõpmata suur, kui graaf on lõpmata suur. Kuid lõpmata suures graafis väga tihti ei otsita, pigem on see käepärane notatsioon üleüldise graafi hargnemise ja sügavuse suhte näitamiseks. Lõpmata suure graafi hargnemise tegurit võib olla võimatu arvutada, sest see on lõpmata suur graaf(nali). Selgem on O(n^2), kus graaf on lõpliku suurusega.

 

Advertisements