Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 16

8.6. Эвристические алгоритмы

Рассмотрим одну знаменитую задачу. Коммивояжер должен посетить N городов и возвратиться в исходный пункт, при этом требуется минимизировать общую протяженность путешествия. Переезжая из города i в город j, он преодолевает расстояние C_ij.

Эта задача коммивояжера может, например, ставиться, когда требуется определить маршрут лиц, занимающихся выемкой монет из таксофонов. Длиной дуги в этом случае может быть расстояние или время в пути между двумя таксофонами на маршруте. В общем случае матрица расстояний несимметрична, но часто рассматривают симметричную матрицу расстояний.

Для решения задачи проще всего организовать поиск в глубину на заданном графе, но это крайне трудоемко при большой размерности графа. Можно использовать метод ветвей и границ, возвращаясь всякий раз, когда длина текущего частного решения превосходит длину лучшего решения, найденного до сих пор. Эта проверка устраняет просмотр некоторых частей дерева решений, но на самом деле она достаточно слабая. Более того, произвольный фиксированный порядок городов является причиной того, что много времени теряется, например, на исследование путей, которые начинаются с маршрута 1 – 2, когда города 1 и 2 отделяет большое расстояние. Имеет смысл начинать исследование с пары ближайших городов. Но и это соображение не спасает полностью положения, как и некоторые другие подходы в рамках метода ветвей и границ.

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

Часто такие алгоритмы строятся на основе некоторых разумных предложений, которые называют эвристиками, а сами алгоритмы – эвристическими. Обычно невозможно доказать, что эвристический алгоритм всегда находит решение близкое к оптимальному. Качество эвристического алгоритма проверяется на практике.

Рассмотрим некоторые эвристические алгоритмы для решения задачи коммивояжера. Наиболее известный из них - алгоритм ближайшего соседа. В качестве начальной точки произвольно выбираем один из городов. Среди всех еще не посещавшихся городов в качестве следующего выбираем ближайший к только что выбранному. Так продолжаем, пока не придем в последний город, после чего возвращаемся в исходный город. Алгоритм ближайшего соседа можно реализовать за время, пропорциональное N².

Есть более эффективные алгоритмы, использующие идеи алгоритмов Прима и Крускала построения остовного дерева графа. Алгоритм включения ближайшего города на каждом шаге добавляет город, еще не вошедший в маршрут, но ближайший к некоторому городу, уже принадлежащему маршруту. Новый город включается после того города из маршрута, который был ближайшим к нему. Этот алгоритм сложнее предыдущего, но также может быть реализован за время O(N²). Доказано, что если матрица симметрична и удовлетворяет неравенству треугольника (C_ij = C_ji и C_ij ≤ C_ik + C_kj для любых i, j, k), то найденный путь не более, чем в 2 раза длиннее оптимального.

В "жадном” алгоритме, как и в алгоритме Крускала, сначала рассматриваются самые короткие ребра. Очередное ребро принимается в том случае, если не приводит к появлению вершины со степенью 3 и более и не образует цикл, за исключением присутствия в цикле всех вершин. Совокупности ребер, выбранных в соответствии с этими критериями, образуют множества несоединенных путей. Такое положение сохраняется до последнего шага, когда единственный путь замыкается, образуя маршрут.

Рассмотрим для примера шесть "городов” A, B, C, D, E, F, заданных координатами A(0, 0), B(4, 3), C(1, 7), D(15, 7), E(15, 4), F(18, 0). Сначала выбирается ребро DE, имеющее кратчайшую длину 3. Затем включаются ребра AB, BC, EF, имеющие длину 5. Следующим кратчайшим ребром является AC, длина которого 7.08. Однако это ребро образует цикл с ребрами AB и BC, поэтому отвергается. Следующее ребро BE повышает степени вершин B и E до 3, поэтому тоже отвергается, как и ребро BD. Затем рассматривается и принимается ребро CD. Образовался путь A, B, C, D, E, F. Завершая маршрут, выбираем ребро AF.

C D

E

B

A F

В результате получен маршрут протяженности 50. Оптимальным является маршрут A, C, D, E, F, B, A, имеющий длину 48.39. Эвристический алгоритм привел к маршруту, который всего на 4 % больше оптимального.

Заключение

Опыт показывает, что необходимое для применения на практике понимание основных структур данных и алгоритмов их обработки достигается только после написания собственных программ. Имеет смысл привести наиболее распространенные ошибки на стадиях проектирования и разработки программ.

1. Постановка задачи понимается неправильно. Порой это выясняется только при сдаче учебной программы. Часто студентами предъявляются претензии о некорректной или недостаточно полной формулировке задачи. Следует иметь в виду, что реальные задания на создание программного обеспечения как правило неполны, неточны и противоречивы. Достаточная ясность возможна только при тесном контакте с заказчиком. При обучении в роли такого заказчика выступает преподаватель.

2. Алгоритмическая проработка задачи проводится поверхностно. В результате при тестировании выявляются принципиальные ошибки.

3. Отсутствует проектирование структуры программы. В итоге с трудом просматривается логическая схема программы, неоправданно употребляются операторы безусловной передачи управления (goto), встречаются дублирующие друг друга фрагменты текста, затруднены тестирование и модификация программы.

4. Текст программы сложен для восприятия и проверки. Для повышения "удобочитаемости” программы рекомендуется [7,8]:

   • применять осмысленные имена переменных;

   • резко ограничивать использование одних и тех же идентификаторов для различных целей;

   • вставлять подробные комментарии, поясняющие назначение и функционирование программных фрагментов;

   • применять отступы в тексте программы, выделяющие группы операторов и показывающие вложенность программных единиц.

Существенные трудности вызывает этап тестирования. В литературе до сих пор встречается следующее определение: ”Тестирование – это процесс, подтверждающий правильность программы и демонстрирующий, что ошибок в программе нет”. Это определение обладает серьезными недостатками. Во-первых, невозможно доказать отсутствие ошибок в любой достаточно сложной программе. Во-вторых, определение психологически настраивает программиста на подбор таких тестов, на которых программа выполняется правильно.

Более точное определение: "Тестирование – это процесс выполнения программы с целью нахождения ошибок” [7, 8]. Следуя данному определению, цель тестирования – заставить программу сбиться, "сломать” программу.

Обычно тестирование и отладка требуют большей трудоемкости, чем разработка программы. Рекомендуется придерживаться следующих правил тестирования [7, 8].

1. Выбор теста должен преследовать цель обнаружения ошибки, а не демонстрации правильности работы программы.

2. Тесты должны проверять как соответствие получаемых результатов условиям задачи, так и внутреннюю логику программы. Минимальный критерий при тестировании логики программного модуля: в каждой точке ветвления следует по крайней мере один раз пройти все пути (это не сводится к исследованию всех возможных путей программы).

3. Необходимая часть всякого теста – описание ожидаемых результатов. Желательно прогнозировать результаты до выполнения теста.

4. Тесты должны охватывать как правильные, так и неправильные данные.

5. Результаты выполнения каждого теста должны тщательно анализироваться и объясняться. Необходимо фиксировать все тесты, на которых выявились ошибки. Распространенной порочной практикой является изменение теста при появлении ошибок.

6. Необходимо учитывать известный парадокс тестирования: чем больше ошибок найдено в некоторой части программы, тем больше вероятность обнаружения в этой части новых ошибок.

Литература

1. Кнут Д. Искусство программирования. Тома 1-3. - М.: Издат. дом "Вильямс”, 2003.

2. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1980. - 406 c.

3. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. - 360 с.

4. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. - 476 с.

5. Лэнгсам И., Огенстайн М., Тенебаум А. Структуры данных для персональных ЭВМ. -М.: Мир, 1989. - 568 с.

6. Трамбле Ж., Соренсон П. Введение в структуры данных. - М.: Машиностроение, 1982. - 784 с.

7. Майерс Г. Надежность программного обеспечения. - М.: Мир, 1980. - 360 с.

8. Хьюз Дж., Мичтом Дж. Структурный подход к программированию. - М.: Мир, 1980. - 278 с.

9. Фараонов В.В. Турбо Паскаль 7.0. Практика программирования: Учебное пособие. – М.: Нолидж, 1997.- 432 с.

10. Нильсон Н. Искусственный интеллект. Методы поиска решений. – М.: Мир, 1973. – 270 с.

11. Автоматизация поискового конструирования / Под ред. А.И. Половинкина. – М.: Радио и связь, 1981. – 344 с.

12. Топп У., Форд У. Структуры данных в С++. – М.: Бином, 2000. – 815 с.

13. Галочкин В.И. Структуры и организация даннных в ЭВМ: Методические указания к выполнению лабораторных и расчетно-графических работ для студентов второго курса специальности 2204. – Йошкар-Ола: 1994. – 42 с.

14. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Издат. дом "Вильямс”, 2003. – 382 с.