35. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.

Алгоритм ближайшего соседа — один из простейших эвристических методов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов.

Формулируется следующим образом:

Пункты обхода плана последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута.

Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма нижней граничной оценки.

Для любого количества городов большего трех в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение.

\

1. Эк.-мат. модель ТЗ

2. Общая форм-ка ТЗ

3. Теорема (о ранге сист. огранич.ТЗ) и след-е из нее. Откр. ТЗ

4. Оценка свободной клетки, ее экономический смысл, критерий оптимальности базисного распределения поставок.

5. Теорема о потенциалах свободных клеток. Вычисление оценок свободных клеток методом потенциалов.

6. Понятие об игровых моделях.

7. Классификация игр.

8. Формальное представление игр.

9. Принцип минимакса для антагонистических игр.

10. Фундаментальное неравенство для цен антагонистических игр.

11. Седловая точка. Теорема о седловой точке.

12. Понятие о смешанной стратегии, чистой стратегии, активной стратегии.

13. Теорема об активных стратегиях. Решение игры 2*2 (формулы).

14. Графический метод решения игры 2*2.

15. Доминирующие стратегии, заведомо невыгодные стратегии, упрощение игр.

16. Сведение игры m*n к двойственным задачам ЛП.

17. Игры с природой: постановка задачи, матрица рисков.

18. Критерии принятия решений в условиях риска (Байеса I и II). Лемма (показатели эффективности и неэффективности стратегии). Теорема об эквивалентности критериев Байеса.

19. Критерии принятия решений в условиях неопределенности: критерии Лапласа и Севиджа.

20. Критерии принятия решений в условиях неопределенности: критерии Вальда и Гурвица. Показатель оптимизма.

21. Общая постановка задачи динамического программирования (ДП). Особенности задачи ДП.

22. Принцип оптимальности и уравнения Бэллмана.

23. Задача о распределении средств между N предприятиями (основные уравнения).

24. Понятие графа и способы его задания. Степень вершины. Инцедентность. Матрица смежности.

25. Понятие маршрута, цепи, простой цепи, цикла для графа. Связные и несвязные графы. Дерево, лес.

26. Пленарные и плоские графы. Изоморфные графы. Полные графы.

27. Эйлеровы графы. Критерий существования эйлерова цикла в графе. Полуэйлеров граф. Задача о Кенигсберских мостах.

28. Гамильтонов граф. Достаточные признаки существования гамильтонова цикла (связь с полиотой графа, теоремы Оре и Дирака). Полугамильтонов граф.

29. Оргафы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.

30. Комбинаторная постановка задачи коммивояжера.

31. Постановка задачи коммивояжера в виде задачи целочисленного программирования. Условие наличия одного цикла.

32. Постановка задачи коммивояжера на языке теории графов.

33. Теорема о приведении матрицы расстояний в ЗК. Оценка маршрута снизу (нижняя граница).

34. Ветвление, оценки нулевых переходов, уточнение нижней границы маршрута.

35. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.