Brute Force vs Exhaustive Search: atšķirība un salīdzinājums

Datorzinātnēs dažādi izstrādātāji ir izstrādājuši daudzus meklēšanas algoritmus, lai meklētu dažādus aspektus (virknes, skaitļus, modeļus, risinājumus).

Meklēšana tiek veikta dažādos veidos. Brute force un Exhaustion search ir divi virkņu meklēšanas algoritmi, ko izmanto kodētāji. Šīs metodes darbojas pēc katra iespējamā risinājuma meklēšanas principa.

Atslēgas

1. Brutāla spēka uzbrukumi sistemātiski pārbauda visas iespējamās kombinācijas, lai uzlauztu paroles vai šifrēšanu.
2. Izsmeļoši meklēšanas algoritmi novērtē visus iespējamos risinājumus, lai atrastu optimālāko.
3. Abas metodes var būt resursietilpīgas, bet efektīvi atrisināt problēmas bez īpašas heiristikas.

Brute Force vs Exhaustive Search

Brutālu spēku ir neviendabīga meklēšana, kas izmanto izmēģinājumu un kļūdu, lai uzminētu pieteikšanās informāciju, šifrēšanas atslēgas vai atrastu slēptu tīmekļa lapu. Izsmeļošā meklēšana ir brutālā spēka meklēšanas veids, ko izmanto, lai atrisinātu problēmas, kas saistītas ar permutācija un kombinācija. Tā ir vienota meklēšana un aizņem mazāk laika.

Brutālā spēka algoritms ir izstrādātāju kodēts paņēmiens, lai iegūtu virknes, un pat to izmanto astoņu dāmu mīklu risināšanā (mīkla astoņu dāmu novietošanai uz astoņu dāmu šaha galda).

Tomēr tā ir intuitīva stratēģija, kas prasa daudz salīdzinājumu, lai atrisinātu problēmu.

Izsmeļošā meklēšana ir brutāla spēka meklēšanas veids, ko izmanto, lai atrisinātu problēmas, kas saistītas ar permutāciju un kombināciju.

Galvenais mērķis ir meklēt katru risinājumu optimālajam risinājumam, apmierinot ierobežojumus. Var atrisināt arī citas problēmas, piemēram, ceļojošā pārdevēja un mugursomas problēmas.

Salīdzināšanas tabula

Salīdzināšanas parametri	Brutālā spēka meklēšana	Izsmeļoša meklēšana
Meklēšanas veids	Brute Force ir nevienmērīga meklēšana.	Izsmeļošs ir vienota meklēšana, jo mēs zinām, kādā virzienā tiek veikta ienešana.
Meklējumi	Brute Force ir paredzēts stīgu raksta meklēšanai.	Izsmeļošais meklēšanas algoritms ir paredzēts permutāciju, kombināciju un apakškopu iegūšanai.
Procedūra	Brute Force algoritms meklē vajadzīgo modeli, virzoties pa labi dotajā tekstā.	Izsmeļošais meklēšanas algoritms pārbauda katru mezglu, līdz tas sasniedz gala mezglu.
Laiks	Brutālais spēks ir laikietilpīga metode.	Izsmeļošais meklēšanas algoritms aizņem mazāk laika salīdzinājumā.
Aplikācijas	Brute Force meklēšanas algoritms tiek izmantots astoņu dāmu novietošanai uz astoņiem reiz astoņiem dēļiem.	Izsmeļošais meklēšanas algoritms tiek izmantots ceļojošā pārdevēja problēmas risināšanai.

Kas ir brutālā spēka meklēšana?

Brute Force algoritms ir viena no meklēšanas metodēm Datorzinātnes. Tā kā tā ir intuitīva metode, tā ir ļoti vienkārša pieeja tādu problēmu risināšanai, kuru pamatā ir tikai prognozes.

Šajā metodē risinājuma atrašanai netiek izmantota sarežģīta tehnika.

Process ir turpināt atkārtot tekstu, lai meklētu virkni. Ja virkne neatbilst, pārvietojiet vienu soli pa labi un atkārtojiet procesu, līdz tiek atrasta atbilstošā atbilstība.

Tagad procedūra ir vienkārša. Pieņemsim, ka mums ir jāmeklē virkne PLANT.

Saskaņojiet katra rindkopas vārda pareizrakstību ar virkni AUGS. Pārvietojieties pa labi, ja frāze rindā neatbilst. Ja virkne atbilst, mūsu meklēšana ir bijusi veiksmīga. Esam saņēmuši vēlamos rezultātus.

Tāpēc mēs varam teikt, ka šī ir ļoti laikietilpīga meklēšanas metode, ja teksta garums ir garāks. Salīdzinājumu skaita aprēķināšanas triks ir N x M reizināšana, kur N ir teksta garums un M ir virknes garums.

Piemēram,

Teksts =10

String= PLANT tā, virknes izmērs =5

Kombinācijas = NXM = 10 x 5 = 50

Praktiskajā dzīvē mēs varam izmantot brutālā spēka meklēšanu. Piemērs ir astoņu dāmu novietošana uz 8 × 8 šaha dēļiem. Noteikums ir sakārtot karalienes tādā pakāpē, lai neviena karaliene neaizsprosto ceļu citai.

Kas ir izsmeļošā meklēšana?

Izsmeļošā meklēšana ir Brute Force meklēšanas algoritma apakškopa, kas paredzēta kombināciju un permutāciju meklēšanai. Šis algoritms koncentrējas uz katra konkrētās problēmas risinājuma atrašanu, izpildot visus ierobežojumus.

Tā kā izsmeļošs nozīmē nogurdinošu, šāda veida meklējumi ir akli, bet vienveidīgi. Stratēģijas mērķis ir palielināt vai samazināt problēmu.

Daudzas problēmas var atrisināt, izmantojot visaptverošu meklēšanu, piemēram, ceļojošā pārdevēja problēmu un mugursomas problēmu.

Ceļojošā pārdevēja problēma ir tā, ka pirms atgriešanās starta vietā pārdevējam ir jāapmeklē N pilsētas (tikai vienu reizi), izmantojot īsāko ceļu.

Šeit N ir pilsētu skaits, un šīs problēmas ierobežojumi ir šādi:

1. Ejot pa īsāko ceļu no pilsētas uz pilsētu.
2. Pirms atgriešanās apmeklējiet visas pilsētas.
3. Apmeklējiet visas pilsētas tikai vienu reizi.

Piemēram,

Ir piecas pilsētas: A, B, C, D un E. Sākuma pilsēta tiek izvēlēta saprātīgi, izmantojot kombinācijas. Tātad, lai visi ierobežojumi tiktu izpildīti.

Izvēloties piemērotu ceļu, mēs izmēģināsim vairākas kombinācijas, kas būs nogurdinoši un laikietilpīgi. Citiem vārdiem sakot, mums ir jāveido cikliska kustība, lai sasniegtu mērķi.

Galvenās atšķirības starp brutālu spēku un izsmeļošu meklēšanu

1. Brute Force meklēšanas algoritms ir nevienmērīga metode. No otras puses, visaptverošs meklēšanas algoritms ir vienota metode.
2. Brute Force meklēšanas algoritms ir metode virknes meklēšanai tekstā. Gluži pretēji, izsmeļošs meklēšanas algoritms meklē permutāciju un kombināciju risinājumu.
3. Brutālā spēka tehnika darbojas, saskaņojot visus virknes burtus. Tomēr izsmeļoša meklēšana tiek veikta pēc katra blokshēmas mezgla pārbaudes, līdz tiek izpildīti ierobežojumi.
4. Brute Force metode ir laikietilpīgāka un ir piemērojama, ja datu apjoms ir īss. No otras puses, izsmeļošs algoritms ir piemērojams pat sarežģītos scenārijos.
5. Tā kā izsmeļošajā meklēšanas paņēmienā tiek izmantota brutālā spēka metode, tā ir populārāka par izsmeļošu meklēšanu.

Atsauces

1. https://ieeexplore.ieee.org/abstract/document/4640789/
2. https://link.springer.com/chapter/10.1007/3-540-44411-4_2

Pēdējo reizi atjaunināts: 13. gada 2023. jūlijā