Bevezetés a brute Force algoritmusba
„Az adatok az új olaj” - ez az új mantrák, amelyek a globális gazdaságot uralják. A digitális világban élünk, és minden üzlet olyan adatok körül forog, amelyek nyereségre fordulnak, és segítik az iparágokat, hogy verseny előtt álljanak. A gyors digitalizálás, az alkalmazás alapú üzleti modell exponenciális növekedése következtében a kiberbűnözés állandó veszélyt jelent. Az egyik ilyen közös tevékenység, amelyet a hackerek hajtanak végre, a Brute Force.
A Brute Force egy próba és hiba módszer, ahol a támadók programokat használnak különböző kombinációk kipróbálására, hogy bármilyen webhelyre vagy rendszerre belépjenek. Automatizált szoftvert használnak a felhasználói azonosító és a jelszavak kombinációjának ismételt előállítására, amíg végül a megfelelő kombinációt nem generálja.
Brute-Force keresés
A brute force keresés a leggyakoribb keresési algoritmus, mivel nem igényel semmilyen domain ismeretét, csak egy állapotleírás, a jogi szereplők, a kezdeti állapot és a célállapot leírása szükséges. Ez nem javítja a teljesítményt, és teljes mértékben támaszkodik a számítási teljesítményre a lehetséges kombinációk kipróbálására.
A nyers erő algoritmus megkeresi a szöveg összes helyzetét 0 és nm között, függetlenül attól, hogy a minta előfordulása ott kezdődik-e vagy sem. Minden egyes kísérlet után pontosan 1 pozícióval elmozdítja a mintát jobbra. Ennek az algoritmusnak az idő bonyolultsága O (m * n). tehát ha n karaktert keresünk m karakterláncban, akkor az n * m próbálkozást igényel.
Lássuk egy klasszikus példát egy utazó eladó számára, hogy az algoritmust könnyen megértse.
Tegyük fel, hogy egy eladónak 10 különféle városba kell utaznia egy országban, és az összes lehetséges kombináció közül meg akarja határozni a lehető legrövidebb útvonalakat. A brutális erő algoritmus itt egyszerűen kiszámítja a városok közötti távolságot, és kiválasztja a legrövidebbet.
Egy másik példa az öt számjegyű jelszó megtörésének megkísérlése, majd a brutális erő akár 10 5 5 kísérletre is szükség lehet a kód feltörésére.
Brute Force Sort
A brutális erő osztályozási technikában az adatok listáját többször átvizsgálják, hogy megtalálják a lista legkisebb elemét. A lista feletti minden iteráció után kicseréli a legkisebb elemet a verem tetejére, és elindítja a következő iterációt a lista második legkisebb adata alapján.
A fenti nyilatkozat pszeudo-kóddal az alábbiak szerint írható.
A probléma itt n méretű, és az alapművelet "if" teszt, ahol az adatelemeket összehasonlítják minden iterációban. Az akarat nem lesz különbség a legrosszabb és a legjobb eset között, mivel a swapszám mindig n-1.
Brute Force String mérkőzés
Ha a mintában az összes karakter egyedi, akkor a brutális erő karakterlánc-egyezés alkalmazható a Big O (n) összetettségével. ahol n a húr hossza. Brutális erő A karakterlánc-illesztés összehasonlítja a mintát a szöveges karakter alstringjével karakter szerint, amíg nem egyező karaktert nem kap. Amint eltérést találnak, az alsó karakterlánc megmarad a karaktere, és az algoritmus a következő alsó karakterláncra mozog.
Az alábbi álkódok magyarázzák a karakterlánc-illesztési logikát. Az algoritmus itt P (0… m-1) mintát próbál keresni a T (0… .n-1) szövegben.
itt a legrosszabb eset lenne, ha egy másik részsávra váltanánk, amíg az M Th összehasonlítást nem végezzük .
Legközelebbi pár
Problémamegjegyzés: A két legközelebbi pont megismerése egy n pontból álló sorozatban a kétdimenziós derékszögben. Nincs számos olyan eset, amikor ez a probléma felmerül. Valós életbeli példa lenne egy légiforgalmi irányító rendszerben, ahol figyelemmel kell kísérni az egymáshoz közel repülő gépeket, és meg kell találnia a legbiztonságosabb minimális távolságot, amelyet ezen síkoknak meg kell tartaniuk.
Forrás: Wikipedia
A brutális erő algoritmus kiszámítja a távolságot az egyes pontcsoportok között, és visszaadja annak a pontnak az indexét, amelynek a távolsága a legkisebb.
A brutális erő (O (n2)) időösszetettével oldja meg ezt a problémát, ahol n a pontok száma.
Az álnév alatt a brute force algoritmus használja a legközelebbi pont megkeresését.
Domború hajótest
Problémamegjegyzés : A konvex test a legkisebb sokszög, amely az összes pontot tartalmazza. A pont halmazának konvex héja a legkisebb konvex sokszög, amely s-t tartalmaz.
Ennek a pontoknak a domború része a konvex sokszög, amelynek csúcsai P1, P5, P6, P7, P3
Az n pontból álló sorozat P1 és Pn vonalszegmense a konvex test része akkor és csak akkor, ha a halmaz többi pontja a vonalszakasz által alkotott sokszög határán helyezkedik el.
Kapcsoljuk össze a gumiszalaggal,
Az (x1, y1), (x2, y2) ponttal az ax tengelye + c-vel növekszik
Ha a = y2-y1, b = x2-x1 és c = x1 * y2 - x2 * y1, és elosztja a síkot ax + by-c értékkel 0
Tehát ellenőriznünk kell az ax + by-c értéket a többi pontra vonatkozóan.
A brutális erő megoldja ezt a problémát O időbeli komplexitásával (n 3 )
Teljes körű keresés
A diszkrét problémák esetén, amelyekben nem ismert hatékony megoldás, szükségessé válik az egyes lehetséges megoldások egymást követő tesztelése.
A kimerítő keresés olyan tevékenység, amellyel szisztematikusan meg lehet találni a probléma összes lehetséges megoldását.
Próbáljuk megoldani az utazókereskedő problémáját (TSP) a Brute kimerítő keresési algoritmus segítségével.
Problémamegjegyzés: Nincs olyan város, amelyben az eladónak utaznia kell, és meg akarja találni a legrövidebb utat, amely az összes várost lefedi.
Fontoljuk, hogy a Hamilton Circuit megoldja a problémát. Ha létezik egy áramkör, akkor bármely pont elindíthat csúcsokat és végcsúcsokat. Miután kiválasztottuk a kezdő csúcsokat, akkor csak a fennmaradó csúcsok sorrendjére van szükségünk, azaz n-1
Akkor ott lenne (n-1)! A lehetséges kombinációk és az út kiszámításának teljes költsége O (n). így a teljes időösszetett O (n!) lenne.
Következtetés
Most, hogy elértük az oktatóanyag végét, remélem, srácoknak most már jó elképzelése van arról, hogy mi a Brute Force. Láttuk a különféle Brute Force algoritmust is, amelyet alkalmazni lehet alkalmazásában.
Ajánlott cikkek
Ez egy útmutató a brute Force algoritmushoz. Itt tárgyaltuk a Brute Force algoritmus alapvető fogalmait. A további javasolt cikkeken keresztül további információkat is megtudhat -
- Mi az algoritmus?
- Algoritmus interjú kérdései
- Bevezetés az algoritmusba
- Algoritmus a programozásban