| dbo:abstract
|
- البحث الشامل (بالإنجليزية: Brute-force search) في علوم الحاسب، تدل على طريقة البحث عن الجواب لمسألة، ما تعتمد على توليد الحل واختباره، تعتبر من أبسط الطرق وأكثرها انتشاراً في حل المسائل العامة بحيث تأخذ بعين الاعتبار كافة الطرق الممكنة للحل وتجريبها. (ar)
- Řešení hrubou silou je způsob řešení problému či úlohy, při kterém se systematicky prochází celý problému. Jeho výhodou je nalezení opravdu nejlepšího řešení či případný důkaz o nemožnosti řešení problému. Jeho nevýhodou bývá velká složitost hledání, a tedy časová, případně paměťová náročnost algoritmu. Velmi často čas potřebný k nalezení řešení roste exponenciálně či dokonce s faktoriálem, takže i pro velmi malé prostory možných řešení je tato metoda v praxi nepoužitelná. Někdy se jako řešení hrubou silou nesprávně označují také slovníkové útoky při prolamování hesel. Ty ale prohledávají již velmi zredukovaný prostor možných řešení a zároveň negarantují nalezení řešení. (cs)
- Die Brute-Force-Methode (von englisch brute force ‚rohe Gewalt‘) bzw. Methode der rohen Gewalt, auch Exhaustionsmethode (kurz Exhaustion von lateinisch exhaurire ‚ausschöpfen‘), ist eine Lösungsmethode für Probleme aus den Bereichen Informatik, Kryptologie und Spieltheorie, die auf dem Ausprobieren aller möglichen (oder zumindest vieler möglicher) Fälle beruht. Sowohl der Begriff erschöpfende Suche (engl. exhaustive search), als auch vollständige Suche sind in Gebrauch. (de)
- In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement. A brute-force algorithm that finds the divisors of a natural number n would enumerate all integers from 1 to n, and check whether each of them divides n without remainder. A brute-force approach for the eight queens puzzle would examine all possible arrangements of 8 pieces on the 64-square chessboard and for each arrangement, check whether each (queen) piece can attack any other. While a brute-force search is simple to implement and will always find a solution if it exists, implementation costs are proportional to the number of candidate solutions – which in many practical problems tends to grow very quickly as the size of the problem increases. Therefore, brute-force search is typically used when the problem size is limited, or when there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than speed. This is the case, for example, in critical applications where any errors in the algorithm would have very serious consequences or when using a computer to prove a mathematical theorem. Brute-force search is also useful as a baseline method when benchmarking other algorithms or metaheuristics. Indeed, brute-force search can be viewed as the simplest metaheuristic. Brute force search should not be confused with backtracking, where large sets of solutions can be discarded without being explicitly enumerated (as in the textbook computer solution to the eight queens problem above). The brute-force method for finding an item in a table – namely, check all entries of the latter, sequentially – is called linear search. (en)
- En informática, la búsqueda por fuerza bruta, búsqueda combinatoria, búsqueda exhaustiva o simplemente fuerza bruta es una técnica trivial pero a menudo usada, que consiste en enumerar sistemáticamente todos los posibles candidatos para la solución de un problema, con el fin de chequear si dicho candidato satisface la solución al mismo. Por ejemplo, un algoritmo de fuerza bruta para encontrar el divisor de un número natural n consistiría en enumerar todos los enteros desde 1 hasta n, chequeando si cada uno de ellos divide n sin generar resto. Otro ejemplo de búsqueda por fuerza bruta, en este caso para solucionar el problema de las ocho reinas (posicionar ocho reinas en el tablero de ajedrez de forma que ninguna de ellas ataque al resto), consistiría en examinar todas las combinaciones de posición para las 8 reinas (en total 64!/8!(64-8)! = 4.426.165.368 posiciones diferentes), comprobando en cada una de ellas si las reinas se atacan mutuamente. La búsqueda por fuerza bruta es sencilla de implementar y, siempre que exista, encuentra una solución. Sin embargo, su coste de ejecución es proporcional al número de soluciones candidatas, el cual es exponencialmente proporcional al tamaño del problema. Por el contrario, la búsqueda por fuerza bruta se usa habitualmente cuando el número de soluciones candidatas no es elevado, o bien cuando este puede reducirse previamente usando algún otro . Es un método utilizado también cuando es más importante una implementación sencilla que una mayor rapidez. Este puede ser el caso en aplicaciones críticas donde cualquier error en el algoritmo puede acarrear serias consecuencias; también es útil como método "base" cuando se desea comparar el desempeño de otros algoritmos metaheurísticos. La búsqueda de fuerza bruta puede ser vista como el método metaheurístico más simple. La búsqueda por fuerza bruta no se debe confundir con backtracking, método que descarta un gran número de conjuntos de soluciones, sin enumerar explícitamente cada una de las mismas. (es)
- La recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles. Par exemple pour trouver le maximum d'un certain ensemble de valeurs, on consulte toutes les valeurs. En cryptanalyse on parle d'attaque par force brute, ou par recherche exhaustive pour les attaques utilisant cette méthode. (fr)
- 力まかせ探索（ちからまかせたんさく、英: Brute-force search）またはしらみつぶし探索（英: Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 通りの配置を全て順にチェックしていく。バックトラッキングでは、2つのクイーンが互いに取り合える状態なら他のクイーンがどう配置されていても考慮に値しないという事実を使って、チェックすべき配置数を大幅に減らし、高速に解くことができる。 力まかせ探索は実装が簡単で、解があるなら絶対それを発見できる。しかし、そのコストは潜在的な解候補数に比例し、多くの実際の問題では、問題の規模に対して解候補数が組合せ爆発を起こして急激に増大する傾向がある。従って力まかせ探索が使われるのは、問題の大きさが限定されている場合か、解候補数を処理可能な程度に縮小できる問題固有のヒューリスティクスがある場合である。 また、実装の単純さが問題を解く速度よりも重要な場合にも使われる。これは例えば、アルゴリズムの間違いが深刻な影響を及ぼすような重要なアプリケーションや、数学的定理をコンピュータで証明するときである。力まかせ探索は、各種アルゴリズムやメタヒューリスティクスのベンチマーク比較を行うときの基準値としても用いられる。実際、力まかせ探索は最も単純なメタヒューリスティクスと見ることもできる。 (ja)
- Wyszukiwanie wyczerpujące (ang. exhaustive search), metoda siłowa (ang. brute force) – metoda polegająca na analizie wszystkich potencjalnych rozwiązań zadania w celu wybrania tego, które spełnia warunki zadania. Złożoność obliczeniowa algorytmów realizujących wyszukiwanie wyczerpujące jest zazwyczaj bardzo duża, często wykładnicza. Metodę tę stosuje się do rozwiązywania problemów, dla których znalezienie rozwiązania za pomocą innych dokładnych metod jest niemożliwe lub zbyt trudne. (pl)
- Metodo forza bruta (anche ricerca esaustiva), nella sicurezza informatica, indica un algoritmo di risoluzione di un dato problema che consiste nel verificare tutte le soluzioni teoricamente possibili fino a che si trova quella effettivamente corretta. Il suo principale fattore positivo è che esso consente teoricamente di trovare sempre la soluzione corretta ma, per contro, questa è sempre la soluzione più lenta o dispendiosa: viene utilizzato come ultima risorsa sia in crittanalisi, sia in altre parti della matematica, ma solamente in quei casi in cui esso sia l'unico procedimento conosciuto o nei casi in cui altri algoritmi più performanti, tipo l'attacco a dizionario, abbiano fallito. (it)
- Em ciência da computação, busca por força bruta ou busca exaustiva, também conhecido como gerar e testar, é uma técnica de solução de problemas trivial, porém muito geral que consiste em enumerar todos os possíveis candidatos da solução e checar cada candidato para saber se ele satisfaz o enunciado do problema. Por exemplo, um algoritmo de força bruta que acha os divisores de um número natural n enumera todos os inteiros de 1 até a raiz quadrada de n, e os checa para saber se dividem n sem deixar resto. Outro exemplo, considere o popular problema das oito damas, no qual é preciso colocar 8 damas em um tabuleiro de xadrez de maneira que nenhuma rainha ataque outra. Uma abordagem por força bruta examinaria todas as possíveis combinações das 8 peças nos 64 quadrados, e, para cada arranjo, checar se alguma rainha está atacando outra. Busca por força bruta é de simples implementação, e sempre vai achar a solução se esta existir. Entretanto, ele custará proporcionalmente ao número de candidatos à solução, o que, em muitos problemas práticos, tende a crescer muito rápido à medida que o tamanho do problema aumenta. Desta maneira, busca por força bruta é tipicamente usada quando o tamanho do problema é limitado, ou quando há heurísticas específicas para o problema que podem ser usadas para reduzir a coleção de candidatos á solução a um tamanho manejável. Este método também é usado quando a simplicidade de implementação é mais importante que a velocidade. Este é o caso de, por exemplo, em aplicações críticas onde qualquer erro no algoritmo teria consequências sérias; ou quando estiver usando um computador para provar um teorema matemático. Busca por força bruta também é útil como "método de base" para benchmarking outros algoritmos ou meta-heurísticas. De fato, busca por força bruta pode ser visto como a mais simples meta-heurística. Busca por força bruta não deve ser confundido com backtracking, onde grandes coleções de soluções podem ser descartadas sem serem explicitamente enumerados. O método de força bruta para achar um item em uma tabela — ou seja, checar todas as entradas da tabela, sequencialmente — é chamado busca linear. (pt)
- Вичерпний пошук (англ. exhaustive search) або метод грубої сили (англ. brute-force) - загальний метод розв'язання задач та , суть якого в систематичному перенумерованні всіх можливих кандидатів на розв'язок і перевірці кандитата на виконання умов. Для прикладу, алгоритм повного перебору для пошуку дільників натурального числа n. Перераховуємо всі натуральні числа від 1 до n, і перевіряємо кожен з них чи буде він ділити n без остачі. У задачі про вісім ферзів повний перебір полягає в тому, щоб розглянути всі можливі розташування 8 місць з 64 клітин шахової дошки, і, для кожного з них, перевірити, чи може кожна (королева) місце атакувати будь-яке інше. Хоча повний перебір легко реалізувати і він завжди буде знаходити відповідь (за умови її існування), час виконання при цьому буде пропорційним кількості кандидатів на розв'язок. А в більшості пратичних задач це призводить до дуже швидкого зростання кількості кандидатів, коли зростає розмір задачі (це називається комбінаторним вибухом). Тому пошук повним перебором зазвичай використовується, тільки для задач невеликого розміру. Наприклад, евристичний алгоритм може скоротити кількість кандидатів на розв'язок до прийнятного розміру. Також метод повного перебору можна використовувати коли простота реалізації важливіше за швидкість. (uk)
- Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу . Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий. Любая задача из класса NP может быть решена полным перебором. При этом, даже если вычисление целевой функции от каждого конкретного возможного решения задачи может быть осуществлено за полиномиальное время, в зависимости от количества всех возможных решений полный перебор может потребовать экспоненциального времени работы. В криптографии на вычислительной сложности полного перебора основывается оценка криптостойкости шифров. В частности, шифр считается криптостойким, если не существует метода «взлома» существенно более быстрого чем полный перебор всех ключей. Криптографические атаки, основанные на методе полного перебора, являются самыми универсальными, но и самыми долгими. (ru)
- 暴力搜索或穷举搜索，在计算机科学中也称生成与测试，是一种非常低效的解决问题的技术，方法包括了系统地枚举解决方案的所有可能候选项，以及检查每个候选项是否符合问题描述。 找出自然数n的约数的暴力搜索算法将枚举出从1到n的所有整数，并检查它们中的每一个是否除n后没有余数。针对八皇后问题的暴力搜索算法会检查所有在8X8棋盘上八个“皇后”可能的摆放方法，并且，对每一种摆放方法，检查其每一个“皇后”是否能攻击到其它人。 虽然暴力搜索很容易实现，并且如果解决方案存在，它就一定能够找到。但是它的代价是和候选方案的数量成正比，由于这一点，在很多实际问题中，消耗的代价会随着问题规模的增加而快速地增长。因此，当问题规模有限，或当存在可用于将候选解决方案的集合减少到可管理大小的针对特定问题的启发式算法时，通常使用暴力搜索。另外，当实现方法的简单度比速度更重要的时候，也会用到这种方法。 例如，在关键的应用中，或当用计算机证明数学定理时，算法中的任何错误将会导致严重的后果。暴力搜索也可在其他和启发式算法里用作基准方法。事实上，暴力搜索可以被看作最简单的启发式算法。暴力搜索与回溯概念是不相同的，在回溯算法中，大量的解决方案并没有被枚举而直接被丢弃（例如上文提到的“八皇后问题”的解决方案）。用于在表中查找一个项目，也就是说顺序地检查表中所有条目的暴力方法被称为线性搜索。 (zh)
|
| rdfs:comment
|
- البحث الشامل (بالإنجليزية: Brute-force search) في علوم الحاسب، تدل على طريقة البحث عن الجواب لمسألة، ما تعتمد على توليد الحل واختباره، تعتبر من أبسط الطرق وأكثرها انتشاراً في حل المسائل العامة بحيث تأخذ بعين الاعتبار كافة الطرق الممكنة للحل وتجريبها. (ar)
- Die Brute-Force-Methode (von englisch brute force ‚rohe Gewalt‘) bzw. Methode der rohen Gewalt, auch Exhaustionsmethode (kurz Exhaustion von lateinisch exhaurire ‚ausschöpfen‘), ist eine Lösungsmethode für Probleme aus den Bereichen Informatik, Kryptologie und Spieltheorie, die auf dem Ausprobieren aller möglichen (oder zumindest vieler möglicher) Fälle beruht. Sowohl der Begriff erschöpfende Suche (engl. exhaustive search), als auch vollständige Suche sind in Gebrauch. (de)
- La recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles. Par exemple pour trouver le maximum d'un certain ensemble de valeurs, on consulte toutes les valeurs. En cryptanalyse on parle d'attaque par force brute, ou par recherche exhaustive pour les attaques utilisant cette méthode. (fr)
- Wyszukiwanie wyczerpujące (ang. exhaustive search), metoda siłowa (ang. brute force) – metoda polegająca na analizie wszystkich potencjalnych rozwiązań zadania w celu wybrania tego, które spełnia warunki zadania. Złożoność obliczeniowa algorytmów realizujących wyszukiwanie wyczerpujące jest zazwyczaj bardzo duża, często wykładnicza. Metodę tę stosuje się do rozwiązywania problemów, dla których znalezienie rozwiązania za pomocą innych dokładnych metod jest niemożliwe lub zbyt trudne. (pl)
- Metodo forza bruta (anche ricerca esaustiva), nella sicurezza informatica, indica un algoritmo di risoluzione di un dato problema che consiste nel verificare tutte le soluzioni teoricamente possibili fino a che si trova quella effettivamente corretta. Il suo principale fattore positivo è che esso consente teoricamente di trovare sempre la soluzione corretta ma, per contro, questa è sempre la soluzione più lenta o dispendiosa: viene utilizzato come ultima risorsa sia in crittanalisi, sia in altre parti della matematica, ma solamente in quei casi in cui esso sia l'unico procedimento conosciuto o nei casi in cui altri algoritmi più performanti, tipo l'attacco a dizionario, abbiano fallito. (it)
- 暴力搜索或穷举搜索，在计算机科学中也称生成与测试，是一种非常低效的解决问题的技术，方法包括了系统地枚举解决方案的所有可能候选项，以及检查每个候选项是否符合问题描述。 找出自然数n的约数的暴力搜索算法将枚举出从1到n的所有整数，并检查它们中的每一个是否除n后没有余数。针对八皇后问题的暴力搜索算法会检查所有在8X8棋盘上八个“皇后”可能的摆放方法，并且，对每一种摆放方法，检查其每一个“皇后”是否能攻击到其它人。 虽然暴力搜索很容易实现，并且如果解决方案存在，它就一定能够找到。但是它的代价是和候选方案的数量成正比，由于这一点，在很多实际问题中，消耗的代价会随着问题规模的增加而快速地增长。因此，当问题规模有限，或当存在可用于将候选解决方案的集合减少到可管理大小的针对特定问题的启发式算法时，通常使用暴力搜索。另外，当实现方法的简单度比速度更重要的时候，也会用到这种方法。 例如，在关键的应用中，或当用计算机证明数学定理时，算法中的任何错误将会导致严重的后果。暴力搜索也可在其他和启发式算法里用作基准方法。事实上，暴力搜索可以被看作最简单的启发式算法。暴力搜索与回溯概念是不相同的，在回溯算法中，大量的解决方案并没有被枚举而直接被丢弃（例如上文提到的“八皇后问题”的解决方案）。用于在表中查找一个项目，也就是说顺序地检查表中所有条目的暴力方法被称为线性搜索。 (zh)
- Řešení hrubou silou je způsob řešení problému či úlohy, při kterém se systematicky prochází celý problému. Jeho výhodou je nalezení opravdu nejlepšího řešení či případný důkaz o nemožnosti řešení problému. Jeho nevýhodou bývá velká složitost hledání, a tedy časová, případně paměťová náročnost algoritmu. Velmi často čas potřebný k nalezení řešení roste exponenciálně či dokonce s faktoriálem, takže i pro velmi malé prostory možných řešení je tato metoda v praxi nepoužitelná. (cs)
- In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement. (en)
- En informática, la búsqueda por fuerza bruta, búsqueda combinatoria, búsqueda exhaustiva o simplemente fuerza bruta es una técnica trivial pero a menudo usada, que consiste en enumerar sistemáticamente todos los posibles candidatos para la solución de un problema, con el fin de chequear si dicho candidato satisface la solución al mismo. La búsqueda por fuerza bruta no se debe confundir con backtracking, método que descarta un gran número de conjuntos de soluciones, sin enumerar explícitamente cada una de las mismas. (es)
- 力まかせ探索（ちからまかせたんさく、英: Brute-force search）またはしらみつぶし探索（英: Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 通りの配置を全て順にチェックしていく。バックトラッキングでは、2つのクイーンが互いに取り合える状態なら他のクイーンがどう配置されていても考慮に値しないという事実を使って、チェックすべき配置数を大幅に減らし、高速に解くことができる。 力まかせ探索は実装が簡単で、解があるなら絶対それを発見できる。しかし、そのコストは潜在的な解候補数に比例し、多くの実際の問題では、問題の規模に対して解候補数が組合せ爆発を起こして急激に増大する傾向がある。従って力まかせ探索が使われるのは、問題の大きさが限定されている場合か、解候補数を処理可能な程度に縮小できる問題固有のヒューリスティクスがある場合である。 (ja)
- Em ciência da computação, busca por força bruta ou busca exaustiva, também conhecido como gerar e testar, é uma técnica de solução de problemas trivial, porém muito geral que consiste em enumerar todos os possíveis candidatos da solução e checar cada candidato para saber se ele satisfaz o enunciado do problema. Por exemplo, um algoritmo de força bruta que acha os divisores de um número natural n enumera todos os inteiros de 1 até a raiz quadrada de n, e os checa para saber se dividem n sem deixar resto. Outro exemplo, considere o popular problema das oito damas, no qual é preciso colocar 8 damas em um tabuleiro de xadrez de maneira que nenhuma rainha ataque outra. Uma abordagem por força bruta examinaria todas as possíveis combinações das 8 peças nos 64 quadrados, e, para cada arranjo, che (pt)
- Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу . Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий. (ru)
- Вичерпний пошук (англ. exhaustive search) або метод грубої сили (англ. brute-force) - загальний метод розв'язання задач та , суть якого в систематичному перенумерованні всіх можливих кандидатів на розв'язок і перевірці кандитата на виконання умов. (uk)
|
