| dbo:abstract
|
- الرجوع في الطريق هي خوارزمية عامة لإيجاد كل (أو بعض) حلول لبعض المسائل الحاسوبية، لا سيما في المسائل التي تحقق الشروط، أن البناء التدريجي للحلول المرشحة، والتخلي عن كل حل مرشح جزئي س («نرجع في الطريق») بمجرد أن يحدد أن س لا يمكن أن تكون حل كامل وصحيح. مثال الكتاب الكلاسيكي في استخدام هذه الخوارزمية هو لغز الوزراء الثمانية، التي تطلب كل الحلول الممكنة لترتيب ثمانية وزراء في لعبة الشطرنج بان يكونو جميع الوزراء بآمان ولا يستطيع أي وزير بأن يهاجم وزير آخر. على نهج هذه الخوارزمية المعروف، الحلول المرشحة الجزئية لترتيب ك وزراء في ك صفوف من اللوح، كلهم في صفوف وأعمدة مختلفة. أي حل جزئي يحتوي على وزيرين يهاجمان بعضهما البعض يمكن أن نتخلى عنه. خوارزمية الرجوع في الطريق يمكننا استخدامها فقط في المسائل التي تعترف بمفهوم «الحل المرشح الجزئي» وفحص سريع نسبياً إذا كان من الممكن أن يكون حل كامل وصحيح. ليس لها فائدة، مثلاً، لتحديد قيمة معينة في جدول غير مرتب. عندما تكون قابلة للتطبيق، هذه الخوارزمية هي اسرع بكثير من خوارزمية تعداد القوة العمياء لكل الحلول المرشحة، لانه من الممكن ازالة عدد كبير من الحلول المرشحة بفحص واحد. خوارزمية الرجوع في الطريق يمكننا استخدامها فقط في المسائل التي تعترف بمفهوم «الحل المرشح الجزئي» وفحص سريع نسبياً إذا كان من الممكن أن يكون حل كامل وصحيح. ليس لها فائدة، مثلاً، لتحديد قيمة معينة في جدول غير مرتب. عندما تكون قابلة للتطبيق، هذه الخوارزمية هي اسرع بكثير من خوارزمية تعداد القوة العمياء لكل الحلول المرشحة، لانه من الممكن ازالة عدد كبير من الحلول المرشحة بفحص واحد.خوارزمية الرجوع في الطريق هي أداة مهمة لحل المسائل التي تحقق الشروط، مثل الكلمات المتقاطعة، الحساب اللفظي، السودوكو، والكثير من الالغاز. هي غالباً من أنسب التقنيات (إذا لم تكن الأكثر فعالية) المستخدمة في التحليل، لمسئلة حقيبة السرقة وغيرها من مسائل الاندماج الامثل. وهي أيضاً أساس لما يسمى لغات البرمجة المنطقية مثل: Aslcon, Planner, Prolog. خوارزمية الرجوع في الطريق تعتمد على المستخدم المعطى «اجراءات الصندوق الاسود» التي تحدد المسائل التي يمكن حلها، طبيعة الحلول المرشحة الجزئية، وكيف يمكن أن نكمل الحلول المرشحة. لذلك فانها الأدلة العليا بدلاً من خوارزمية معينة، خلافاً لغيرها من الأدلة العليا، هي مضمونة لإيجاد جميع الحلول لمسائل محدودة في وقت محدود. المصطلح «الرجوع في الطريق» قد صيغ من عالم الرياضيات الأمريكي ديريك هينري ليمير في ال 1950. لغة معالجة الكلمات (SNOBOL) (1962) يمكن أن تكون الأولى التي أسست طريقة الرجوع في الطريق مبنية فيها. (ar)
- El Backtracking és una estratègia per trobar solucions a problemes que satisfan restriccions. El terme "backtrack" va ser encunyat per primera vegada pel matemàtic nord-americà Derrick Henry Lehmer en la dècada de 1950. (ca)
- Backtracking (česky zpětné vyhledávání, metoda pokusů a oprav, metoda zpětného sledování, metoda prohledávání do hloubky) je způsob řešení algoritmických problémů založený na prohledávání stavového prostoru problému. Jedná se o vylepšení hledání řešení hrubou silou v tom, že velké množství potenciálních řešení může být vyloučeno bez přímého vyzkoušení. Algoritmus je založen na prohledávání do hloubky možných řešení. Algoritmus je možné použít pro řešení velkého množství problémů, nicméně díky jeho (obecně) exponenciální časové složitosti se používá jen tehdy, kdy není znám efektivnější algoritmus (polynomiální) nebo je použit pro data malé velikosti, popřípadě pro něj existuje dobrá heuristika. (cs)
- Der Begriff Rücksetzverfahren oder englisch Backtracking (Rückverfolgung) bezeichnet eine Problemlösungsmethode innerhalb der Algorithmik. (de)
- Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned. Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute-force enumeration of all complete candidates, since it can eliminate many candidates with a single test. Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog. Backtracking depends on user-given "black box procedures" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than a specific algorithm – although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time. The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s. The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility. (en)
- Le retour sur trace ou retour arrière (appelé aussi backtracking en anglais) est une famille d'algorithmes pour résoudre des problèmes algorithmiques, notamment de satisfaction de contraintes (optimisation ou décision). Ces algorithmes permettent de tester systématiquement l'ensemble des affectations potentielles du problème. Ils consistent à sélectionner une variable du problème, et pour chaque affectation possible de cette variable, à tester récursivement si une solution valide peut-être construite à partir de cette affectation partielle. Si aucune solution n'est trouvée, la méthode abandonne et revient sur les affectations qui auraient été faites précédemment (d'où le nom de retour sur trace). En d'autres termes, le retour sur trace est un parcours en profondeur sur l'arbre de décision du problème. (fr)
- Vuelta atrás (Backtracking) es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en la década de 1950. (es)
- バックトラッキング （backtracking）は、制約充足問題の解を探索する戦略の一種で、力まかせ探索を改良したもの。「バックトラック」という用語は、アメリカの数学者が1950年代に作った造語である。 (ja)
- Il backtracking (in italiano, si può definire "monitoraggio a ritroso") è una tecnica per trovare soluzioni a problemi in cui devono essere soddisfatti dei vincoli. Questa tecnica enumera tutte le possibili soluzioni e scarta quelle che non soddisfano i vincoli. Una tecnica classica consiste nell'esplorazione di strutture ad albero e tenere traccia di tutti i nodi e i rami visitati in precedenza, in modo da poter tornare indietro al più vicino nodo che conteneva un cammino ancora inesplorato nel caso che la ricerca nel ramo attuale non abbia successo. I nodi a profondità uguale rappresentano i possibili valori di una variabile. Una applicazione del backtracking è nei programmi per giocare a scacchi, che generano tutte le mosse possibili per una profondità di N mosse a partire da quella attuale e poi esaminano con il backtracking le varie alternative, selezionando alla fine quella migliore. Il backtracking ha una complessità esponenziale, quindi è poco efficiente nell'affrontare problemi che non siano NP-completi. In generale, comunque, l'algoritmo integra euristiche che permettono di diminuirne la complessità. Questa tecnica è alla base del linguaggio di programmazione Prolog. (it)
- 퇴각검색(영어: backtracking, 한국어: 백트래킹)은 을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다. (ko)
- Backtracking is een methode die gebruikt wordt bij zoekproblemen in de informatica. Backtracking is handiger dan de brute force-methode, omdat niet alle oplossingen bekeken hoeven te worden. De term werd rond 1950 voor het eerst gebruikt door de wiskundige Derrick Henry Lehmer. Bij zoekproblemen moet er een oplossing geselecteerd worden uit een heel aantal plausibele mogelijkheden. Tijdens de oplossing van het probleem moet men keuzes maken. Als achteraf blijkt dat een genomen keuze niet leidt tot een oplossing, of niet tot een optimale oplossing, dan moet men terugkeren naar het keuzemoment. Dit terugkeren noemt men backtracking. Ook de oplossingsmethode als geheel (het algoritme) wordt backtracking genoemd.Na het maken van een nieuwe keuze gaat het algoritme verder tot opnieuw moet terugkeren, of een goede oplossing vindt. (nl)
- Algorytm z nawrotami (ang. backtracking) – ogólny algorytm wyszukiwania wszystkich (lub kilku) rozwiązań niektórych problemów obliczeniowych, który stopniowo generuje kandydatów na rozwiązanie, jednak gdy stwierdzi, że znaleziony kandydat c nie może być poprawnym rozwiązaniem, nawraca (ang. backtracks) do punktu, gdzie może podjąć inną decyzję związaną z jego budową. (pl)
- Backtracking é um tipo de algoritmo que representa um refinamento da busca por força bruta, em que múltiplas soluções podem ser eliminadas sem serem explicitamente examinadas. O termo foi cunhado pelo matemático estado-unidense D. H. Lehmer na década de 1950. O procedimento é usado em linguagens de programação como Prolog. Uma busca inicial em um programa nessa linguagem segue o padrão busca em profundidade, ou seja, a árvore é percorrida sistematicamente de cima para baixo e da esquerda para direita. Quando essa pesquisa falha, ou é encontrado um nodo terminal da árvore, entra em funcionamento o mecanismo de backtracking. Esse procedimento faz com que o sistema retorne pelo mesmo caminho percorrido com a finalidade de encontrar soluções alternativas. Um exemplo de algoritmo de Backtracking está representado abaixo: bool acabou = FALSE;backtrack(int a[], int k, int n) { int c[MAXCANDIDATOS]; /* Candidatos para a próxima posição */ int ncandidatos; /* Número de candidatos para a próxima posição */ int i; /* Contador */ if (e_uma_solucao(a, k, n)) { processar_solucao(a, k, n); } else { k = k + 1; construir_candidatos(a, k, n, c, &ncandidatos); for (i=0; i<ncandidatos; i++) { a[k] = c[i]; backtrack(a, k, n); if (acabou) return; } }} As principais aplicações desse tipo de algoritmo são para a construção de todos os 2^n subconjuntos de um conjunto S, com n elementos e todas as permutações desse conjunto. Abaixo seguem as sub-rotinas para cada situação, na linguagem C: (pt)
- Пошук з вертанням (англ. backtracking), також пошук з поверненням — загальний алгоритм для знаходження всіх (або деяких) розв'язків деякої обчислювальної задачі, який поступово будує кандидатів на розв'язок, і відкидає кожного неповного кандидата c («вертається») як тільки визначає, що c не може бути доповненим до вірного розв'язку. (uk)
- Поиск с возвратом, бэктрекинг (англ. backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило, позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п. Термин backtracking был введен в 1950 году американским математиком Дерриком Генри Лемером. Незначительные модификации метода поиска с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ, поиск в глубину, метод проб и ошибок и т. д. Поиск с возвратом практически одновременно и независимо был изобретен многими исследователями ещё до его формального описания. (ru)
- 回溯法（英語：backtracking）是暴力搜尋法中的一种。 对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于約束滿足問題（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。 在经典的教科书中，八皇后问题展示了回溯法的用例。（八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布，使得没有一个皇后能攻击到另外一个。） 回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现，现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
* 找到一个可能存在的正确的答案
* 在尝试了所有可能的分步方法后宣告该问题没有答案 在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。 (zh)
|
| rdfs:comment
|
- El Backtracking és una estratègia per trobar solucions a problemes que satisfan restriccions. El terme "backtrack" va ser encunyat per primera vegada pel matemàtic nord-americà Derrick Henry Lehmer en la dècada de 1950. (ca)
- Der Begriff Rücksetzverfahren oder englisch Backtracking (Rückverfolgung) bezeichnet eine Problemlösungsmethode innerhalb der Algorithmik. (de)
- Vuelta atrás (Backtracking) es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en la década de 1950. (es)
- バックトラッキング （backtracking）は、制約充足問題の解を探索する戦略の一種で、力まかせ探索を改良したもの。「バックトラック」という用語は、アメリカの数学者が1950年代に作った造語である。 (ja)
- 퇴각검색(영어: backtracking, 한국어: 백트래킹)은 을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다. (ko)
- Algorytm z nawrotami (ang. backtracking) – ogólny algorytm wyszukiwania wszystkich (lub kilku) rozwiązań niektórych problemów obliczeniowych, który stopniowo generuje kandydatów na rozwiązanie, jednak gdy stwierdzi, że znaleziony kandydat c nie może być poprawnym rozwiązaniem, nawraca (ang. backtracks) do punktu, gdzie może podjąć inną decyzję związaną z jego budową. (pl)
- Пошук з вертанням (англ. backtracking), також пошук з поверненням — загальний алгоритм для знаходження всіх (або деяких) розв'язків деякої обчислювальної задачі, який поступово будує кандидатів на розв'язок, і відкидає кожного неповного кандидата c («вертається») як тільки визначає, що c не може бути доповненим до вірного розв'язку. (uk)
- 回溯法（英語：backtracking）是暴力搜尋法中的一种。 对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于約束滿足問題（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。 在经典的教科书中，八皇后问题展示了回溯法的用例。（八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布，使得没有一个皇后能攻击到另外一个。） 回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现，现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
* 找到一个可能存在的正确的答案
* 在尝试了所有可能的分步方法后宣告该问题没有答案 在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。 (zh)
- الرجوع في الطريق هي خوارزمية عامة لإيجاد كل (أو بعض) حلول لبعض المسائل الحاسوبية، لا سيما في المسائل التي تحقق الشروط، أن البناء التدريجي للحلول المرشحة، والتخلي عن كل حل مرشح جزئي س («نرجع في الطريق») بمجرد أن يحدد أن س لا يمكن أن تكون حل كامل وصحيح. خوارزمية الرجوع في الطريق تعتمد على المستخدم المعطى «اجراءات الصندوق الاسود» التي تحدد المسائل التي يمكن حلها، طبيعة الحلول المرشحة الجزئية، وكيف يمكن أن نكمل الحلول المرشحة. لذلك فانها الأدلة العليا بدلاً من خوارزمية معينة، خلافاً لغيرها من الأدلة العليا، هي مضمونة لإيجاد جميع الحلول لمسائل محدودة في وقت محدود. (ar)
- Backtracking (česky zpětné vyhledávání, metoda pokusů a oprav, metoda zpětného sledování, metoda prohledávání do hloubky) je způsob řešení algoritmických problémů založený na prohledávání stavového prostoru problému. Jedná se o vylepšení hledání řešení hrubou silou v tom, že velké množství potenciálních řešení může být vyloučeno bez přímého vyzkoušení. Algoritmus je založen na prohledávání do hloubky možných řešení. (cs)
- Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s. The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility. (en)
- Le retour sur trace ou retour arrière (appelé aussi backtracking en anglais) est une famille d'algorithmes pour résoudre des problèmes algorithmiques, notamment de satisfaction de contraintes (optimisation ou décision). Ces algorithmes permettent de tester systématiquement l'ensemble des affectations potentielles du problème. Ils consistent à sélectionner une variable du problème, et pour chaque affectation possible de cette variable, à tester récursivement si une solution valide peut-être construite à partir de cette affectation partielle. Si aucune solution n'est trouvée, la méthode abandonne et revient sur les affectations qui auraient été faites précédemment (d'où le nom de retour sur trace). (fr)
- Il backtracking (in italiano, si può definire "monitoraggio a ritroso") è una tecnica per trovare soluzioni a problemi in cui devono essere soddisfatti dei vincoli. Questa tecnica enumera tutte le possibili soluzioni e scarta quelle che non soddisfano i vincoli. Una applicazione del backtracking è nei programmi per giocare a scacchi, che generano tutte le mosse possibili per una profondità di N mosse a partire da quella attuale e poi esaminano con il backtracking le varie alternative, selezionando alla fine quella migliore. Questa tecnica è alla base del linguaggio di programmazione Prolog. (it)
- Backtracking is een methode die gebruikt wordt bij zoekproblemen in de informatica. Backtracking is handiger dan de brute force-methode, omdat niet alle oplossingen bekeken hoeven te worden. De term werd rond 1950 voor het eerst gebruikt door de wiskundige Derrick Henry Lehmer. (nl)
- Backtracking é um tipo de algoritmo que representa um refinamento da busca por força bruta, em que múltiplas soluções podem ser eliminadas sem serem explicitamente examinadas. O termo foi cunhado pelo matemático estado-unidense D. H. Lehmer na década de 1950. Um exemplo de algoritmo de Backtracking está representado abaixo: As principais aplicações desse tipo de algoritmo são para a construção de todos os 2^n subconjuntos de um conjunto S, com n elementos e todas as permutações desse conjunto. Abaixo seguem as sub-rotinas para cada situação, na linguagem C: (pt)
- Поиск с возвратом, бэктрекинг (англ. backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило, позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п. Термин backtracking был введен в 1950 году американским математиком Дерриком Генри Лемером. (ru)
|
