Чтение онлайн

Опыт применения этого условия для графов с п = 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. Схема алгоритма «а-оптимум»

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

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