Изучение алгоритмов поиска
Исследование алгоритмов решения задач методом поиска
Имеется транспортная сеть, связывающая города СНГ. Сеть представлена в виде таблицы связей между городами. Связи являются двусторонними, т.е. допускают движение в обоих направлениях. Необходимо проложить маршрут из одной заданной точки в другую.
На этом этапе известна только топология связей между городами.
Выполнить:
- поиск в ширину;
- поиск глубину;
- поиск с ограничением глубины;
- поиск с итеративным углублением;
- двунаправленный поиск.
Отобразить движение по дереву на его графе с указанием сложности каждого вида поиска. Сделать выводы.
Воспользовавшись информацией о протяженности связей от текущего узла, выполнить:
- жадный поиск по первому наилучшему соответствию;
- затем, использую информацию о расстоянии до цели по прямой от каждого узла, выполнить поиск методом минимизации суммарной оценки А*.
Отобразить на графе выбранный маршрут и сравнить его сложность с неинформированным поиском. Сделать выводы.
| city1 | city2 | r |
|---|---|---|
| Вильнюс | Брест | 531 |
| Витебск | Брест | 638 |
| Витебск | Вильюс | 360 |
| Воронеж | Витебск | 869 |
| Воронеж | Волгоград | 581 |
| Волгоград | Витебск | 1455 |
| Витебск | Ниж.Новгород | 911 |
| Вильнюс | Даугавпилс | 211 |
| Калининград | Брест | 699 |
| Калиниград | Вильнюс | 333 |
| Каунас | Вильнюс | 102 |
| Киев | Вильнюс | 734 |
| Киев | Житомир | 131 |
| Житомир | Донецк | 863 |
| Житомир | Волгоград | 1493 |
| Кишинев | Киев | 467 |
| Кишинев | Донецк | 812 |
| С.Петербург | Витебск | 602 |
| С.Петербург | Калининград | 739 |
| С.Петербург | Рига | 641 |
| Москва | Казань | 815 |
| Москва | Ниж.Новгород | 411 |
| Москва | Минск | 690 |
| Москва | Донецк | 1084 |
| Москва | С.Петербург | 664 |
| Мурманск | С.Петербург | 1412 |
| Мурманск | Минск | 2238 |
| Орел | Витебск | 522 |
| Орел | Донецк | 709 |
| Орел | Москва | 368 |
| Одесса | Киев | 487 |
| Рига | Каунас | 267 |
| Таллинн | Рига | 308 |
| Харьков | Киев | 471 |
| Харьков | Симферополь | 639 |
| Ярославль | Воронеж | 739 |
| Ярославль | Минск | 940 |
| Уфа | Казань | 525 |
| Уфа | Самара | 461 |
Задание по варианту №9 — SOURCE:"Брест" DESTINATION:"Казань"