АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Перебор в ширину в деревьях И – ИЛИ

Читайте также:
  1. Влияние различных факторов на ширину запрещенной зоны и подвижность носителей
  2. Изменения при переборе в произвольных графах.
  3. Метод направленного перебора.
  4. Перебор элементов массива
  5. Переборный метод решения задач
  6. Плоские переборки. Отбойные переборки
  7. Сказка о деревьях-Характерах
  8. Случайный перебор (метод проб и ошибок).
  9. Технике прыжка согнув ноги через коня в ширину

Рассмотрим алгоритм поиска в ширину в деревьях И-ИЛИ, а потом обобщим его на произвольный граф.

1) Начальную вершину помещаем в список OPEN.

2) Взять первую вершину из OPEN и поместить её в CLOSED. Обозначить её через n.

3) Раскрыть вершину n и поместить пораженные вершины в конец списка OPEN. Провести указатели к n. Если порожденных вершин нет, то пометить n, как неразрешимую и перейти к п.4., иначе к п.8.

4) Применить к дереву процедуру на неразрешимость.

5) Если начальная вершина неразрешима, то решения нет. Выход

6) Изъять из OPEN все вершины, имеющие неразрешимые предшествующие вершины.

7) Перейти к п.2.

8) Если все порожденные вершины заключительные, то пометить их как разрешимые и перейти к п.2. Заключительные вершины - это разрешимые и концевые.

9) Применить к дереву разметку на разрешимость.

10) Если начальная вершина разрешима, то выдать решение используя указатели. Выход.

11) Изъять из OPEN все разрешимые вершины и разрешимые предшествующие вершины.

12) Перейти к п.2.

Построение потенциального дерева решений t0. d:\111allrefs\MY\ЗГИА\ОИИ\Метода\Lecture\Lecture_course.htm - cod#cod Эвристический поиск в деревьях И-ИЛИ


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)