Задача използваща алгоритъм на Дейкстра
Изтегляне 73 Kb.
|
- Навигация на страницата:
- Известни са две класически задачи
| Хамилтонови цикли
Хамилтонов цикъл в граф се нарича цикъл, съдържащ всеки връх от графа точно веднъж. Граф, съдържащ такъв цикъл, се нарича Хамилтонов. Известни са две класически задачи: - проверка, дали даден граф е Хамилтонов; - задача за търговския пътник (търсене на Хамилтонов цикъл с минимална дължина в тегловен граф). И двете задачи се определят като NP-пълни, което означава, че сложността им в най-лошия случай е експоненциална. Първата задача може да бъде решена чрез проверка на циклите в графа (пълно изчерпване на вариантите). Втората вече е разглеждана. Тя също може да се реализира чрез пълно изчерпване и практически е неприложима при големи n. Н апример, за следния граф е Хамилтонов. С червено е означен минималния Хамилтонов цикъл, който е 1 2 3 5 4 6 1 и има цена 28. Получен е чрез преглеждане на всички маршрути, започващи от даден базов възел ( в случая - 1). Ако на дадена стъпка получаваме междинна цена на изграждания маршрут, по-голяма от тази на минималния, изграждането на този маршрут се прекратява. Поради широкото си приложение, задачата е изследвана много подробно в литературата. За решението й съществуват десетки алгоритми, някои от които гарантират точно решение с полиномиална сложност (например, метод на клоните и границите). Известни са и евристични подходи за решаване на задачата. Изтегляне 73 Kb. Сподели с приятели:
|