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

Алгоритм равных цен

Читайте также:
  1. I.2.4. Алгоритм симплекс-метода.
  2. II. 4.1. Алгоритм метода ветвей и границ
  3. LU – алгоритм нахождения собственных значений для несимметричных задач
  4. QR- алгоритм нахождения собственных значений
  5. SALVATOR - это переход физического явления в семантико-нейронный алгоритм (инструкцию) освобождения человека от негативных последствий этого явления.
  6. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  7. Алгоритм
  8. Алгоритм
  9. Алгоритм
  10. Алгоритм
  11. Алгоритм
  12. Алгоритм 1.2. Выделение групп предприятий с помощью заливки контрастным цветом

Это модификация перебора в ширину, которая учитывает стоимость дуг. В этом случаи для каждой вершины, кроме указателя на родительскую вершину нужно запоминать и стоимость пути. Для дерева это минимальный путь. Особенностью метода является то, что вершины раскрываются в порядке возрастания стоимостей g(n).

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

2. Если OPEN пуст то решений нет.

3. Взять из OPEN ту вершину, для которой =min(). В случаи равенства значений - любую из них отдавая предпочтение целевой. Перенесём эту вершину в CLOSED и обозначим n как текущую вершину.

4. Если n - целевая вершина, то построить решение используя указатели.

5. Раскрыть вершину n, построить порождённые вершины, если таких нет то переходим к п2. . Поместить эти вершины в список OPEN вместе с ценами и указателями на n

6. Перейти к п2.

Если целевая вершина описана явно то процесс перебора можно построить в обратном порядке. Для этого нужно обратить оператор Г.

 

Алгоритм поиска в глубину

Раскрываем в первую очередь вершины, которые порождены последней. Глубина дерева определяется рекурсивно. Глубина корня=0. Глубина последующей вершины равна глубине родительской + 1. При переборе в глубину наибольшую глубину имеет вершина раскрытая последней в данный момент.

АЛГОРИТМ:

1. Поместить начальные вершины в OPEN.

2. Если OPEN пуст, то нет решений

3. Взять последнюю вершину из OPEN и переместить в CLOSED и обозначить через n

4. Если глубина n= граничной то перейти к п2.

5. Раскрыть вершину n, поместив все порожденные в конец списка OPEN и построить указатели к n.

6. Если одна из вершин целевая, то выдать решение, используя указатели. Иначе перейти к п2.

Для поиска в глубину часто используют стек, тогда не нужны указатели.


1 | 2 | 3 | 4 | 5 |

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

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