Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
Значения эвристической функции для задачи поиска маршрута
| Город | Расстояние по прямой до Рима (Р), км | Город | Расстояние по прямой до Рима (Р), км |
| A – Алессандрия | K – Модена | ||
| B – Генуя | L – Пиза | ||
| C – Милан | M – Флоренция | ||
| D – Пьяченца | N – Гроссето | ||
| E – Бергамо | O – Перуджа | ||
| F – Брешиа | P – Рим | ||
| G – Верона | R – Л’Акуила | ||
| H – Падуя | S – Анкона | ||
| I – Венеция | T – Римини | ||
| J – Болонья | - | - |
Рис.2. Пространство состояний задачи поиска маршрута
На рис.3 показан процесс применения жадного поиска с использованием значений h(n) для определения пути из Венеции в Рим.
Процедура жадного поиска не всегда приводит к поиску оптимального пути и может вызывать развертывание ненужных узлов. Жадный поиск напоминает поиск в глубину в том отношении, что этот алгоритм предпочитает на пути к цели постоянно следовать по единственному пути, но возвращается к предыдущим узлам после попадания в тупик.
Рис.3. Применение жадного поиска
Таблица 2
| <== предыдущая страница | | | следующая страница ==> |
| Жадный поиск по первому наилучшему совпадению | | | Значения эвристической функции |
Дата добавления: 2015-07-26; просмотров: 197; Нарушение авторских прав
Мы поможем в написании ваших работ!