Полный перебор
При данном подходе должен выполняться полный перебор, перечисляя все возможные пути и выбирая путь(и) с самой низкой стоимостью. Любой метод, используемый, чтобы создать эти пути может быть иллюстрирован деревом решений.
Мы могли бы например выполнять полный перебор, используя алгоритм 'поиска в глубину', см. [CORM90] стр. 477 .. 483. Кратко: начнем 'трассировку' пути решения с листа в дереве решений, производящем первый путь. Затем мы создадим указатель возврата на первую точку решения, где мы еще не исследовали все возможные 'решения' и наченм новый перебор по дереву для нового пути. Чтобы ограничивать число путей для перебора, мы можем непосредственно отбрасывать любые пути, которые имели бы 'циклы'. Продолжайте по этому способу, пока все дерево пройдено. Другими словами, начните в исходной вершине, перейдите по граням к другим вершинам (которые еще не прошли), и повторяйте, пока вершина адресата не достигнута.В каждой точке решения, мы имеем выбор из восьми направлений. Назовем число вершин N. Поскольку любая ячейка может быть посещена больше, чем один раз (иначе имелся бы цикл), мы можем устанавливать, что каждый возможный путь имеет в большинстве случаев N-1 граней, то есть дерево поиска имеет глубину O(N). Так как число ветвей восемь на каждом уровне, мы получаем в большинстве 8N -1 возможных путей, то есть мы имеем O(8N) путей, чтобы исследовать в самом плохом случае. Таким образом, этот подход берет экспоненциальное время, чтобы найти решение. Это ясно не очень хорошо. Алгоритм очень плохой так как не различает между огромным большинством возможных путей, которые, вряд ли, будут оптимальны и те очень немногие, которые являются вероятными кандидатами.
7.1.2
Еще по теме Полный перебор:
- СЕМАНТИКО-СИНТАКСИЧЕСКИЕ РАЗЛИЧИЯ В УПОТРЕБЛЕНИИ ВАРИАНТОВ ПОЛНЫЙ Ч Е Г О И ПОЛНЫЙ ЧЕМ
- Баронова М.М.. Русский язык: полный справочник /М.М. Баронова. - М.: Владимир,2010. - 286, [2] с. - (Полный комплект пособий для подготовки к единому государственному экзамену), 2010
- Метод лексикографического перебора
- Метод неявного перебора по векторной решетке
- 20. Полный комплект финансовой отчетности в соответствии с МСФО.
- Мир, полный различий
- Тема 7 ПОЛНЫЙ ЛЕВЕРИДЖ[4]
- 8.5.1 Полный факторный эксперимент
- Полный набор потребительских услуг
- Глава 2. Мир, полный различий
- Полный лексический анализ текста
- Полное приращение и полный дифференциал.
- Анализ полный и выборочный. Роль отдельных языковых категорий и явлений.
- Задание 18. Дайте полный ответ на вопросы.
- Жаворонкова А.С.. Шпаргалка по философии: ответы на экзаменационные билеты.Полный зачет, 2011
- II. Полный перечень услуг и работ по содержанию и ремонту общего имущества в многоквартирном доме,
- Валгина Нина Сергеевна и др.. Полный академический справочник РОССИЙСКАЯ АКАДЕМИЯ НАУК 2005, 2005
- Николай Владимирович Адамчик. Самый полный курс русского языка / Авт. Н. В. Адамчик. — Минск: Харвест,2008. — 848 с., 2008
- Желание иметь больше свободного времени — один из трех основных мотивов открытия собственного on-line бизнеса. Однако, в действительности желание это редко исполняется. Полный рабочий день быть начальником самому себе — занятие, отнимающее и время, и нервы. Поэтому предлагаю вам насколько советов, как снять излишнее напряжение в работе и сэкономить время:
- ЭВРИСТИКА