Системная технология - Марат Телемтаев

Следовательно, правая часть системы (9.2.4) примет вид:

Итак, условие а-оптимальности примет вид:

для а ? 5.

После простых преобразований получаем

для а ? 5.

Отсюда получаем условие n-оптимальности (а=n):

И, далее, условие (n+1)-оптимальности (а=n+1), т.е. условие оптимальности собственно гамильтонова цикла, принимает вид

Можно усилить условие (9.2.7), введя вместо проверки суммарного неравенства проверку по всем k. Получим условия а-оптимальности гамильтонова цикла в виде:

Выше было показано, что а1-оптимальный гамильтонов цикл а2-оптимален, если а1 > а2. Поэтому условие оптимальности гамильтонова цикла можно преобразовать к виду (а=n+1):

9.3. Алгоритм

«Принцип обогащения» применительно к решению задачи о коммивояжере (ЗОК) заключается в следующем: с помощью некоторого условия проверить все ветви графа на наличие полезных свойств (в данном случае это «способность» участвовать в оптимальном гамильтоновом цикле) и для дальнейшего решения задачи оставить только эти «полезные» ветви. В случае, когда используемое условие достаточно сильно, после этой проверки останутся только ветви оптимального гамильтонова цикла. В другом случае из рассмотрения будет исключена часть ветвей графа, что дает возможность сократить время поиска решения с применением какого-либо алгоритма.

Таким образом, весь процесс решения задачи делится на 2 стадии: первая – «обогащение» исходного числового массива, вторая – применение алгоритма поиска на «обогащенном» массиве.

Реализация первой стадии при решении ЗОК возможна с применением полученного в разделе 9.2 условия оптимальности гамильтонова цикла в графе G с п вершинами.

Условие оптимальности можно использовать для «обогащения» исходного множества ветвей графа: после проверки всех ветвей графа на условие оптимальности число ветвей, которое целесообразно использовать при дальнейшем решении ЗОК, сократится. Ввиду очевидной простоты описание алгоритма не приводится.

Опыт применения этого условия для графов с п = 11–67 показал, что после однократного применения такой операции ко всем ветвям графа число ветвей в обогащенном массиве сокращается, как правило, до 15% от первоначального.

Для поиска оптимального гамильтонова цикла на обогащенном массиве использовался следующий метод. Известно, что существующие алгоритмы решения ЗОК не ставят целью обеспечение или проверку а-оптимальности получаемого гамильтонова цикла.

Предлагаемый алгоритм основан на последовательном обеспечении а-оптимальности решения ЗОК на обогащенном массиве исходных данных и состоит в выполнении следующих операций.

Алгоритм «а-оптимум».

0. Задаем произвольно исходный гамильтонов цикл i1, ..., ik, ..., in, i1 с весом ? (i1, ..., in, i).

1. 3адаем значение а; а=4,5, ...,п, п+1.

2. Задаем значение k; k=1,2,...,п,1,2, ...,п,2,... .

3. Для вершины ik сравниваем все последовательности на а вершинах, ik, ..., ik+a-1, получаемые перестановками а-2 промежуточных вершин между ik и iк+а-1 по их весам р(iк,..., ik+a-1), и выбираем последовательность с наименьшим весом. При этом последовательности, содержащие ветви с весом, равным бесконечности (между этой парой вершин нет соединения), отбрасываем сразу, не вычисляя веса.

Если веса всех последовательностей в операции 3 равны, либо вес ? (ik, ik+1, ..., ik+a-2, ik+a-1) является минимальным, оставляем в гамильтоновом цикле последовательность ik, ik+1, ik+a-1, имевшую место в начале операции 3 для данного k. Этот факт фиксируем и переходим к операции 4.

Если таких последовательностей несколько, то из них выбираем первую по счету, вводим ее в гамильтонов цикл вместо соответствующей прежней и переходим к операции 2, где задается очередное значение k.

4. Фиксируем значение k. Проверяем все зафиксированные ранее значения k. Если ранее зафиксированы не все значения k, то переходим к операции 2, где задается очередное значение k. Если ранее зафиксированы все значения k=1,2,..., п, то полученный гамильтонов цикл а-оптимален. Переходим к операции 5.

5. Проверка одинаковости решений при а-2, а-1, а.

Примечание. Оптимальный ((п+1)-оптимальный) гамильтонов цикл а-оптимален для всех значений а. Но такая проверка для больших значений а требует неприемлемых затрат времени. Поэтому для конкретных задач можно ограничиться обеспечением условия совпадения а-оптимальных гамильтоновых циклов для нескольких последовательных значений а, например трех (т.е., когда удлинение проверяемых последовательностей на одну, две ветви не дает улучшения результата).

Если хотя бы одно решение отличается от других, переходим к операции 1, где задается новое значение а. Если все три решения равны, считаем результат – полученный а-оптимальный гамильтонов цикл – удовлетворительным решением ЗОК. Последовательность выполнения операций алгоритма показана на графе (рис.9.1).

Работа алгоритма «а-оптимум» анализировалась для различных п.

При решении задач метод «обогащения» исходного множества ветвей и алгоритм «а-оптимум» использовались совместно. Во всех приведенных случаях такой совместный счет эффективнее алгоритма «а-оптимум» на необогащенном множестве ветвей графа.

С соответствующими изменениями предложенные методы «обогащения» и «а-оптимизации» могут использоваться и для задач поиска а-оптимальных простых путей и циклов (или их совокупностей), покрывающих т ? п вершин графа.

Рис.9.1. Схема алгоритма «а-оптимум»

Глава 10. Экология

10.1. Введение

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

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

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

В большинстве случаев экологию определяют, как науку о взаимоотношениях живых организмов между собой и со средой их обитания. Можно сказать, что экономика занимается финансовым хозяйством, а экология – «хозяйством» среды обитания [12]. Используем теорию системной технологии для развития этого тезиса в свете проблем управления общественным развитием. Исходя из сказанного, мы будем рассматривать проблемы экологической деятельности человека в сочетании с проблемами экономическими и социальными. Мы не будем рассматривать приложения системной философии деятельности к другим разделам экологии (напр., к экологии пресных вод, лиманов и моря, к экологии суши, к радиационной экологии и др.); все это предмет специальных работ.