Алгоритм.

⇐ Предыдущая 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; просмотров: 535. Нарушение авторских прав; Мы поможем в написании вашей работы!

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

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

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

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

Педагогическая структура процесса социализации Характеризуя социализацию как педагогический процессе, следует рассмотреть ее основные компоненты: цель, содержание, средства, функции субъекта и объекта...

Типовые ситуационные задачи. Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической нагрузке. Из медицинской книжки установлено, что он страдает врожденным пороком сердца....

Толкование Конституции Российской Федерации: виды, способы, юридическое значение Толкование права – это специальный вид юридической деятельности по раскрытию смыслового содержания правовых норм, необходимый в процессе как законотворчества, так и реализации права...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

Постинъекционные осложнения, оказать необходимую помощь пациенту I.ОСЛОЖНЕНИЕ: Инфильтрат (уплотнение). II.ПРИЗНАКИ ОСЛОЖНЕНИЯ: Уплотнение...

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