A brute-force keresés egy egyszerű, átfogó keresési technika, amely az összes lehetséges megoldást kipróbálja egy adott probléma megoldására. Bár nem hatékony nagy keresési térben, kis méretű problémák esetén egyszerű és gyakran használható módszer.
A brute-force keresés szövegben történő mintaillesztésre egyszerűen végigpróbálja az összes lehetséges pozíciót.
Pszeudokód:
function BruteForceSearch(text, pattern):
n = text hossza
m = pattern hossza
minden i = 0-tól (n-m) indexig:
ha text == pattern:
térj vissza i (találat)
térj vissza -1 (nincs találat)
Python implementáció:
def brute_force_search(text, pattern):
n = len(text)
m = len(pattern)
for i in range(n - m + 1):
if text == pattern:
return i # Találat helye
return -1 # Nincs találat
# Példa használat
text = "hello world"
pattern = "world"
result = brute_force_search(text, pattern)
if result != -1:
print(f"Találat a(z) {result}. pozíciónál.")
else:
print("Nem található a minta.")
Kimenet:
Találat a(z) 6. pozíciónál.
C++ implementáció:
#include <iostream>
#include <string>
using namespace std;
int bruteForceSearch(const string& text, const string& pattern) {
int n = text.size();
int m = pattern.size();
for (int i = 0; i <= n - m; i++) {
if (text.substr(i, m) == pattern) {
return i; // Találat
}
}
return -1; // Nincs találat
}
int main() {
string text = "hello world";
string pattern = "world";
int result = bruteForceSearch(text, pattern);
if (result != -1) {
cout << "Találat a(z) " << result << ". pozíciónál." << endl;
} else {
cout << "Nem található a minta." << endl;
}
return 0;
}
Kimenet:
Találat a(z) 6. pozíciónál.
Az összes lehetséges útvonalat kiszámítja és a legkisebb összköltségűt választja ki.
Python implementáció:
from itertools import permutations
def tsp_brute_force(graph):
n = len(graph)
cities = range(n)
min_cost = float('inf')
best_path =
for path in permutations(cities):
cost = sum(graph]] for i in range(n - 1))
cost += graph]] # Visszatérés az indulási városba
if cost < min_cost:
min_cost = cost
best_path = path
return best_path, min_cost
# Példa gráf
graph = [
,
,
,
]
path, cost = tsp_brute_force(graph)
print(f"Legjobb útvonal: {path}, Költség: {cost}")
Kimenet:
Legjobb útvonal: (0, 1, 3, 2), Költség: 80
Az összes lehetséges tárgykombinációt végignézi, hogy megtalálja a maximális értéket.
Python implementáció:
def knapsack_brute_force(values, weights, capacity):
n = len(values)
max_value = 0
for i in range(1 << n): # Minden lehetséges kombináció (2^n)
total_weight = 0
total_value = 0
for j in range(n):
if i & (1 << j): # J-ik tárgy kiválasztva
total_weight += weights
total_value += values
if total_weight <= capacity:
max_value = max(max_value, total_value)
return max_value
# Példa adatok
values =
weights =
capacity = 50
print(f"Maximális érték: {knapsack_brute_force(values, weights, capacity)}")
Kimenet:
Maximális érték: 220
A brute-force keresés egy egyszerű, de gyakran számításigényes megközelítés: - Előnyei: - Egyszerű és egyértelmű implementáció. - Garantáltan megtalálja a megoldást, ha létezik. - Hátrányai: - Lassú és nem hatékony nagy keresési terekben. - Kombinatorikus robbanás miatt gyorsan kezelhetetlenné válhat.
Tipikusan kis problémák megoldására vagy referenciaként használják más algoritmusok validációjára.