Алгоритм.

⇐ Предыдущая 1 2 3 4 5 678 9 10 Следующая ⇒

Введем следующие обозначения:

s – узел начального состояния;

g – узел конечного (целевого) состояния;

OPEN – список выбранных, но необработанных узлов;

CLOSED – список обработанных узлов.

Шаги:

1. .

2. Если , то прекратить выполнение. Пути к целевому состоянию на графе не существует.

3. Удалить из списка OPEN узел n, для которого для любого узла m, уже присутствующего в списке OPEN, и перенести его в список CLOSED.

4. Сформировать список очередных узлов, в который возможен переход из узла n, и удалить из него все узлы, образующие петли; с каждым из оставшихся связать указатель на узел n.

5. Если в сформированном списке очередных узлов присутствует g, то завершить выполнение. Сформировать результат – путь, порожденный прослеживанием указателей от узла g до узла s.

6. В противном случае для каждого очередного узла , включенного в список выполнить следующую последовательность операций:

6.1 Вычислить .

6.2 Если не присутствует ни в списке OPEN, ни в списке CLOSED, добавить его в список, присоединить к нему оценку и установить обратный указатель на узел n.

6.3 Если уже присутствует в списке OPEN или в списке CLOSED, сравнить новое значение с прежним .

6.4 Если , прекратить обработку нового узла.

6.5 Если , заменить новым узлом прежний в списке, причем, если прежний узел был в списке CLOSED, перенести его в список OPEN.

⇐ Предыдущая 1 2 3 4 5 678 9 10 Следующая ⇒

Дата добавления: 2015-08-30; просмотров: 552. Нарушение авторских прав; Мы поможем в написании вашей работы!

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при которых тело находится под действием заданной системы сил...

Общая и профессиональная культура педагога: сущность, специфика, взаимосвязь Педагогическая культура- часть общечеловеческих культуры, в которой запечатлил духовные и материальные ценности образования и воспитания, осуществляя образовательно-воспитательный процесс...

Устройство рабочих органов мясорубки Независимо от марки мясорубки и её технических характеристик, все они имеют принципиально одинаковые устройства...

Ведение учета результатов боевой подготовки в роте и во взводе Содержание журнала учета боевой подготовки во взводе. Учет результатов боевой подготовки - есть отражение количественных и качественных показателей выполнения планов подготовки соединений...

Метод Фольгарда (роданометрия или тиоцианатометрия) Метод Фольгарда основан на применении в качестве осадителя титрованного раствора, содержащего роданид-ионы SCN...

Потенциометрия. Потенциометрическое определение рН растворов Потенциометрия - это электрохимический метод исследования и анализа веществ, основанный на зависимости равновесного электродного потенциала Е от активности (концентрации) определяемого вещества в исследуемом растворе...

Гальванического элемента При контакте двух любых фаз на границе их раздела возникает двойной электрический слой (ДЭС), состоящий из равных по величине, но противоположных по знаку электрических зарядов...

Studopedia.info - Студопедия - 2014-2026 год . (0.012 сек.) русская версия | украинская версия