Sissejuhatus julma jõu algoritmi
"Andmed on uus õli" - see on uus mantra, mis valitseb maailmamajanduses. Me elame digitaalses maailmas ja iga ettevõte keerleb andmete ümber, mis teenivad kasumit ja aitavad tööstustel konkurentsist ees hoida. Kiire digiteerimise, rakendusepõhise ärimudeli hüppelise kasvu tõttu on küberkuriteod pidev oht. Üks selline tavaline tegevus, mida häkkerid täidavad, on Brute Force.
Brute Force on katse-eksituse meetod, kus ründajad kasutavad programme, et proovida mitmesuguseid kombinatsioone, et tungida mis tahes veebisaitidele või süsteemidesse. Nad kasutavad automatiseeritud tarkvara kasutaja ID ja paroolide kombinatsioonide korduvaks genereerimiseks, kuni see lõpuks genereerib õige kombinatsiooni.
Jõhkrate jõudude otsing
Jõhkrate jõudude otsing on kõige levinum otsingu algoritm, kuna see ei nõua domeeni tundmist, vaja on ainult oleku kirjeldust, juriidilisi operaatoreid, lähteseisundit ja eesmärgi oleku kirjeldust. See ei paranda jõudlust ja tugineb võimalike kombinatsioonide proovimiseks täielikult arvutusvõimsusele.
Jõhkra jõu algoritm otsib teksti kõiki positsioone vahemikus 0 kuni nm, kas mustri ilmnemine algab seal või mitte. Pärast iga katset nihutab see mustrit paremale täpselt ühe asendi võrra. Selle algoritmi ajaline keerukus on O (m * n). nii et kui otsime n tähemärki jada m tähemärki, võtab see aega n * m katset.
Vaatame klassikalist näidet reisimüüja kohta, et algoritmi hõlpsalt mõista.
Oletame, et müügimees peab reisima riigi 10 erinevat linna ja ta soovib kõigist võimalikest kombinatsioonidest kindlaks teha võimalikult lühikese marsruudi. Siin arvutab jõhkra jõu algoritm lihtsalt kõigi linnade vahelise vahemaa ja valib kõige lühema.
Veel üks näide on proovida 5-kohalist parooli murda, siis võib jõhker jõud koodi purunemiseks võtta kuni 10 5 katset.
Jõhkra jõu sorteerimine
Julma jõu sorteerimistehnikas skannitakse andmete loetelu mitu korda, et leida loendist väikseim element. Pärast iga itereerimist loendi kohal asendab see väikseima elemendi virna ülaosas ja alustab järgmist iteratsiooni loendi teisest väikseimast andmest.
Ülaltoodud avalduse saab pseudokoodina kirjutada järgmiselt.
Siin on probleem suurusega n ja põhitoiming on "if" test, kus igas iteratsioonis võrreldakse andmeühikuid. Halvimal ja paremal juhul vahet ei tehta, sest vahetustehingute arv on alati n-1.
Brute Force keelpillide sobitamine
Kui kõik mustri märgid on ainulaadsed, saab Big O (n) keerukusega rakendada ka jõhkra jõu stringi sobitamist. kus n on stringi pikkus. Jõhker jõud Stringi sobitamine võrdleb mustrit tekstimärgi alamstringiga tähemärgi kaupa, kuni see saab sobimatu tähemärgi. Niipea, kui leitakse mittevastavus, langeb alamstringi järelejäänud märk ja algoritm liigub järgmisele alamstringile.
Allpool olevad pseudokoodid selgitavad stringide sobitamise loogikat. Algoritm püüab siin tekstis T (0… .n-1) otsida mustrit P (0… m-1).
halvim juhtum oleks siis, kui teisele alamstringile nihutataks alles enne M Th võrdlust.
Lähim paar
Probleemilause: n-punktikomplekti kahe lähima punkti väljaselgitamiseks kahemõõtmelises Descartes'i tasapinnas. Selle probleemi ilmnemisel on n stsenaariumi. Tegeliku elu näide oleks lennuliikluse juhtimissüsteemis, kus peate jälgima üksteise lähedal lendavaid lennukeid ja leidma kõige turvalisema minimaalse vahemaa, mida need lennukid peaksid hoidma.
Allikas: Vikipeedia
Pöördjõu algoritm arvutab iga eraldiseisva punktikomplekti vahelise vahemaa ja tagastab selle punkti indeksid, mille vahemaa on väikseim.
Jõhker jõud lahendab selle probleemi aja keerukusega (O (n2)), kus n on punktide arv.
Pseudokoodi allpool kasutatakse lähima punkti leidmiseks jõhkra jõu algoritmi.
Kumer korp
Probleemiavaldus : kumer kere on väikseim hulknurk, mis sisaldab kõiki punkte. Punkti komplekti kumer kere on väikseim kumer polügoon, mis sisaldab punkte.
Selle punktide komplekti kumer kere on kumer hulknurk, mille tipud on P1, P5, P6, P7, P3
N-punktilise komplekti sirgjoon P1 ja Pn on kumera kere osa ainult siis, kui kõik ülejäänud komplekti punktid asuvad joonelõigu moodustatud hulknurgapiiris.
Seostame selle kummiribaga,
Punkt (x1, y1), (x2, y2) teeb sirge telje + võrra = c
Kui a = y2-y1, siis b = x2-x1 ja c = x1 * y2 - x2 * y1 ning jagab tasapinna teljega + c-c-ga 0
Seega peame teiste punktide jaoks kontrollima ax + by-c.
Jõhker jõud lahendab selle probleemi keerukusega O (n 3 )
Põhjalik otsing
Diskreetsete probleemide korral, mille jaoks pole teada tõhusat lahendust, on vaja katsetada kõiki võimalikke lahendusi järjestikku.
Põhjalik otsing on tegevus, mille eesmärk on süstemaatiliselt leida probleemile kõik võimalikud lahendused.
Proovime lahendada reisimüüja (TSP) probleemi Brute ammendava otsingu algoritmi abil.
Probleemikirjeldus: Müügimehel on n linna, mida on vaja reisida. Ta soovib teada saada kõige lühema marsruudi, mis hõlmab kõiki linnu.
Kaalume selle probleemi lahendamiseks Hamiltoni vooluringi. Kui vooluahel on olemas, võib mis tahes punkt alustada tippe ja lõpp-tippe. Kui alguspunktid on valitud, vajame järjekorda ainult ülejäänud tipude jaoks, st n-1
Siis oleks (n-1)! Võimalikud kombinatsioonid ja tee arvutamise kogumaksumus oleks O (n). seega oleks kogu aja keerukus O (n!).
Järeldus
Nüüd, kui oleme jõudnud selle õppematerjali lõppu, loodan, et te, kutid, olete nüüd saanud aimu, mis on Brute Force. Oleme näinud ka mitmesuguseid Brute Force algoritme, mida saate oma rakenduses rakendada.
Soovitatavad artiklid
See on olnud julma jõu algoritmi juhend. Siin arutasime julma jõu algoritmi põhimõisteid. Lisateavet leiate ka meie muudest soovitatud artiklitest -
- Mis on algoritm?
- Algoritmi intervjuu küsimused
- Sissejuhatus algoritmi
- Algoritm programmeerimisel