Лабораторна робота 2
Тема: Розв’язок задач методами неінформативного та інформативного пошуку.
Мета: Навчитися розв’язувати задачі методами неінформативного пошуку, орієнтуватися в поняттях неінформативного пошуку, пошук у ширину, пошук за критерієм вартості, пошук у глибину, пошук з обмеженням глибини, пошук у глибину з ітераційним збільшенням глибини, двонаправлений пошук. Навчитися розв’язувати задачі методами інформованого пошуку, досліджувати простір станів, ознайомитися з видами інформованого пошуку.
Завдання:
1. Потрібно побудувати маршрут проїзду між містами. Відома топологія зв’язків між містами. Виконати: пошук у ширину; пошук у глибину; пошук з обмеженням глибини; пошук у глибину з ітераційним збільшенням глибини; двонаправлений пошук. Зобразити рух по дереву пошуку на його графі та вказати складність кожного виду пошуку. Відстань до пункту призначення з’ясувати за географічною картою.
2. Існує транспортна мережа України. Зв’язки є двосторонніми, тобто передбачають рух у двох напрямах. Відстань до пункту призначення з’ясувати за географічною картою. Виконати: жадібнийпошук за першим найкращим співпаданням; пошук А*: мінімізація сумарної вартості між обраними містами. Зобразити на графі обраний маршрут. Зробити висновки.
Мета: Навчитися розв’язувати задачі методами неінформативного пошуку, орієнтуватися в поняттях неінформативного пошуку, пошук у ширину, пошук за критерієм вартості, пошук у глибину, пошук з обмеженням глибини, пошук у глибину з ітераційним збільшенням глибини, двонаправлений пошук. Навчитися розв’язувати задачі методами інформованого пошуку, досліджувати простір станів, ознайомитися з видами інформованого пошуку.
Завдання:
1. Потрібно побудувати маршрут проїзду між містами. Відома топологія зв’язків між містами. Виконати: пошук у ширину; пошук у глибину; пошук з обмеженням глибини; пошук у глибину з ітераційним збільшенням глибини; двонаправлений пошук. Зобразити рух по дереву пошуку на його графі та вказати складність кожного виду пошуку. Відстань до пункту призначення з’ясувати за географічною картою.
2. Існує транспортна мережа України. Зв’язки є двосторонніми, тобто передбачають рух у двох напрямах. Відстань до пункту призначення з’ясувати за географічною картою. Виконати: жадібнийпошук за першим найкращим співпаданням; пошук А*: мінімізація сумарної вартості між обраними містами. Зобразити на графі обраний маршрут. Зробити висновки.