рефераты конспекты курсовые дипломные лекции шпоры

Раздел Философия
/
Отслеживание в обратном порядке. Понятие

Реферат Курсовая Конспект

Выберите учебное заведение

Отслеживание в обратном порядке. Понятие

Отслеживание в обратном порядке. Понятие - раздел Философия, Recursive factorials Отслеживание В Обратном Порядке Является Проблемой, Решая Метод, Который Вклю...

Отслеживание в обратном порядке является проблемой, решая метод, который включает исследование всех возможностей в поиске решения. Пример отслеживания в обратном порядке может быть замечен в процессе обнаружения решения лабиринта. Во время исследования лабиринта мы должны принять решения, включающие который путь исследовать. Когда сталкиваешься с выбором путей, мы решаем, пойти ли на север, юг, восток, или запад. Подход отслеживания в обратном порядке, чтобы найти путь через лабиринт включает рассмотрение всех возможных путей, пока мы не находим решения.

Рисунок 1 лабиринт

Отслеживание в обратном порядке включает преследование одного возможного решения, пока алгоритм не решает, что оно не является решением. Если алгоритм отслеживания в обратном порядке обнаруживает, что выбранная возможность не является решением, алгоритм "backs up" рассматривает другую возможность возможных решений. Например, мышь должна найти решение лабиринта, чтобы добраться до сыра в рисунке 1. Давайте займем место мыши в ситуации и увидем, как мы можем использовать отслеживание в обратном порядке, чтобы найти решение. Сразу, в позиции A, у нас есть выбор между севером или югом. Например, мы выберем север, но мы будем помнить, что есть другой путь, ведущий на юг, который мы не исследовали. Идя на север, мы быстро узнаем, что этот путь приводит в тупик. В этой ситуации мы должны вернуться в обратном порядке в позицию A и пойти по другому. Двигаясь на юг от позиции A в позицию B, где мы можем продолжать перемещаться на юг или исследовать путь на восток. Если мы хотим идти на восток, мы должны будем, конечно, принять много других решений. Если один из этих путей приводит к решению, наш поиск завершен. Если все пути, отклоняющиеся на восток приводят в тупики, мы должны вернуться в обратном порядке в позицию B и исследовать путь, который ведет на юг. Этот процесс гарантирует решение лабиринта, так как он рассматривает все возможные пути.

Алгоритмы «отслеживание в обратном порядке», которые используют рекурсию, управляет в основном тем же самым путем как другие рекурсивные алгоритмы. Подобный любому другому рекурсивному алгоритму, программисты разрабатывают алгоритмы отслеживания в обратном порядке вокруг base case, которые решаются без рекурсии. В примере лабиринта существует base case, когда мышь рядом с выходом лабиринта (в позиции C). В этой ситуации выбор пойти на восток очевиден, и рекурсивный поиск не нужен. Рекурсивные алгоритмы отслеживания в обратном порядке также уменьшают проблему до наименьшей подзадачи. Рекурсия, примененная в примере лабиринта, эффективно делает лабиринт меньшего размера и меньшим, пока это не достигает основного случая.

Пример: Восемь Королев

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Recursive factorials

Example contains the output of the factorial program after the addition of the output statements to function factorial factorial begin... The output in Example shows that the program first calls function factorial... Problem Solving with Recursion Divide and...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Отслеживание в обратном порядке. Понятие

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

The Call Stack
The call stack is an area of a program's memory used to manage the currently executing function and all pending function calls. Figure 3 lends some insight into what is meant by a "pend

Removing Recursion
Recursion comes with a price: the run time system has to maintain a complicated call stack, on top of having to perform the usual evaluations contained in the function. Often, we can eliminate recu

Divide and Conquer
Divide and conquer is a problem solving technique that utilizes recursion to solve a problem by "dividing" the problem into smaller and smaller sub-problems. The base case of the r

Backtracking. The Concept
Backtracking is a problem solving technique that involves examining all possibilities in the search for a solution. An example of backtracking can be seen in the process of finding the solution to

The Problem
A classic problem that we can solve using backtracking is the Eight Queens problem. This difficult problem deals with placing eight queens on a chessboard such that no two queens are attacking each

The Solution
To solve the Eight Queens problem, we use a backtracking algorithm. The algorithm involves placing queens, column by column, onto the chessboard. The algorithm terminates when it places all eight q

The Call Stack
Call Stack это область памяти программы, используемая, чтобы управлять выполняющейся функцией и всеми последующими вызовами находящиеся в ожидании. Рисунок 3 отражает то понимание, которое принято

Замена рекурсии
Рекурсия имеет собственное решение: т.е. система времени выполнения должна поддержать сложный стек вызовов, сверх необходимости выполнять обычные оценки в функции. Часто бывает выгодно заменить рек

Проблема
Классической проблемой, решения задачи методом «отслеживание в обратном порядке», является проблема Восьми Королев. Эта трудная проблема соглашения с размещением восьми королев на шахматной доске т

Решение
Чтобы решить проблему Восьми Королев, мы используем алгоритм отслеживания в обратном порядке. Алгоритм включает размещения королев, столбец за столбцом, на шахматную доску. Алгоритм завершается, ко