1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 30
Текст из файла (страница 30)
Минимальная раскраска связного графа С получается последовательностью склеиваний, при которой суммарное число исчезнувших ребер оказывается не меньшим этого числа для всех других последовательностей. Этот вывод для нас хорош тем, что он дает разумную опору для более эффективных эвристик: рассматривая окрестность Вг(о), мы не знаем наверняка, какая из вершин является соцветной. Однако если мы выберем из Лг(о) вершину ю, имеющую с о наиболыпее среди остальных вершин Лг(о) число рааделяющих вершин, мы обеспечим на данном шагу наибольшее доступное нам убывание числа ребер.
Будем нааывать этот алгоритм 2-й эвристикой. Более точно этот алгоритм выглядит так. Пусть задан какой-то порядок вершин графа. Берем очередную вершину и в ее окрестности 2-го порядка ищем вершину ю с максимальным числом разделяющих. Склеиваем и с ш, полученную вершину считаем очередной. Поступаем так до тех пор, пока очередная вершина не станет звездой, после чего переходилг к следующей по порядку вершине-незвезде и т. д. Рнс.
3.18 показывает сяучай, когда 2-я эвристика (3.18, в) оказывается эффективнее 1-й (рис. 3.18, б), а на рис. 3.19 показан случай, когда вершина, выбираемая по 2-й эвристике, не оказывается соцветной. Во 2-й эвристике мы фиксировали очередную вершину и в ее окрестности искали кандидата на склеивание с максимумом разделяющих вершин. Можно усовершенствовать алгоритм, вводя 3-ю эвристику, не связанную с жестким порядком вершин графаз Гл. З.алгогитмиэация перед каждым склеиванием искать в графе пару вершин с максимальным числом разделяющих среди всех пар вершин, находя-, щихся друг от друга на расстоянии два. Пример рис.
3.49 лишаев рвс. 8.18. Пример удачного применения 2-й эвристпкп. е) Граф. 6) 1-я вврвсткка. «) 2-я вврясткка. нас надежд на получение минимальной раскраски и для этой эвристики, однако в среднем можно надеяться на ее большую аффективность по сравнению с первыми двумя. Правда, это возможное улучшение требует, вообще говоря, порядка ие операций для~ выполнения одного склелвания. ш бг' Рве. 2.19. Пример неудачного пркмекеквв 2-й эвркствкн. а) 2-я эврвсткка. 6) Мквяма «ьная раскраска. Автором был взят граф из 50 вершин, построенный на ЭВМ случайным образом, лишь бы он оказался связным и подери<а.т бы 400 ребер.
Для этого графа были получены и нанесены яа рис. 3.17 три траектории убывания числа ребер, полученные по 1 й, 2 й и 3-й эвристикам. Они подтверждают наше интуитивное представление как об их относительной эффективности, так и о приличном «запасе мощностив этих алгоритмов по сравнению о оценкой (2), достигаемой для заданных и и р только на графах довольно специального вида — какого, читателю предлагается додуматься самому ГЛАВА 4 РЕАЛИЗАЦИЯ з 4.1. Вступление В этой главе мы сделаем еще один шаг в конкретизации нашего исследования и в приближении к его аавершению.
Мы превратим найденные в предыдущей главе алгоритмы над абстрактными объек-' тами в реально выполнимые процедуры. В наших условиях «реальное выполнение» означает выполнение на ЭВМ. Это значит, что алгоритмы должны быть запрограммированы, выражены на алгоритмическом яаыке. Мы уже обещали мимоходом, что этим языком будет алгол.
Первый и весьма важный этап работы по программированию— это найти подходящие представления для введенных ранее в интересах нашей задачи абстрактных объектов: операторной схемы, информационного графа и его компонент связности, графа несовместимости н его раскраски. Выбор этих представлений подчиняется двум очевидным требованиям: (1) в основе представлений должны лежать объекты алгола: целые и вещественные числа, логические значения и их возможные объединения в массивы; (2) представления должны быть «естественными» для рассматриваемых абстрактных объектов, в частности, в представлении составного объекта долинины легко усматриваться представления его компонент.
Заметим, что алгол (имеется в виду яаык алгол 60) довольно скуден в отношении раанообразия своих объектов и в более современных языках мы могли бы выбрать более естественные представления для некоторых наших абстрактных объектов. Тем' не менее алгола 60 хватит для того, чтобы на примере нашей задачи познакомиться с одним из наиболее универсальных способов ларифметизации» абстрактных объектов, т. е. их представления в виде чисел и их комбинаций. В основе этой арифметизацин лежит предположение, что все рассматриваемые множества конечны, причем их мощность в момент работы с ними известна. В таком случае все эти множества занумеровываются, после чего в качестве представления элемента множества берется его номер. Тот факт, что в результате' такого соглашения элементы самых разиых множеств представляются одним и тем же объектом,— целым числом,— никого не беспо- 444 гл.
«. Рвллизация конт. Считается, что в любой момент работы программы вы знаете, с номером чего имеете дело: с номером переменной величины, или номером оператора, или номером аргумента. При атом мы будем говорить «элемент г» или ««-й элементе, как нам будет удобнее, заранее понимая, что речь идет об одном и том же. Второе универсальное правило задает способ изображения множеств, являющихся подмножеством некоторого общего занумерованного множества М = (т,, ..., т„).
В этой символике любое М' с: М имеет вид М' = (т;„т;„..., т,„) /с~ )О, 1 ( гь ~~ и. Тогда для представления берется логический вектор длины и, в котором каждая иа компонент с номерами «и»«,..., ~„ равна истина, а все остальные компоненты равны ложь. Во многих задачах вместо логических значений ложь и истина берут соответственно О и 1. В литературе такие векторы иногда называются логическими шкалами. В некоторых случаях представление элемента множества должно показывать, алементом какого множества является данное представление. Пусть этн множества суть М,, М, ..., М .
Тогда для этих множеств образуется числовое множество (1,... к), называемое привнаковым множеством, а его алемевты называются признаками. Прианак есть просто номер одного яз множеств М„..., Мю Тогда т-й элемент множества М, изображается парой (1, т). Непосредственное применение этих правил ариф»4етизацни будет покааано на соответствующих этапах программирования. При построении программ, реализующих экономию памяти в операторных схемах, мы продемонстрируем одну методику программирования, которая в последние годы получила широкое распространение. Эта методика называется «структурированноо программирование».
Этот термин — не единственный. Даже только в литературе на русском языке можно найти термины «структурное», «систематическое», «деталнзирующее», «нисходящее» программпрование, которые обоаначают примерно одно и то же. Схему структурированного программирования мы объясним в следующем параграфе, а пока скан«ем лишь, какие трудности программирования пытается преодолеть эта методика.
В апреле 1975 г. в Лос-Анджелесе (Соединенные 1Птаты) состоялась международная конференция по программированию. Один пз докладов, в котором излагалась сущность структурированного программирования, назывался «Как писать программы правильно и знать об этом?». Здравомыслящему читателю, но не очень близкому к практике программирования, такая тема научного доклада может даже показаться наивностью или кокетством. Однако более тесное знакомство с программированием делает вполне понятной постановку такого вопроса. Составление программы — зто предсказание поведения ЭВМ для всех случаев упот- » ах ст»гиту»иРОВАннон п»ог»ьммигованнн ребления программы, для всего разнообразия входных данных.
Бели программист составляет программу, скажем, из 1000 команд, работающую на ЭВМ (например, БЭСМ-6) 1 минуту, то зто значит, что при написании текста этой программы объемом в 20 страниц он должен вообрааить и точно предсказать выполнение 60 млн. арифметических и логических действий. Ни одна из этих операций не возьмется «неважно откуда», а должна быть явно и недвусмысленно аадана программистом наперед. Формально, программа — это текст, состоящий из букв, цифр- и знаков.
Процесс написания программы можно представить себе как последовательность принятия решений: какую букву написать„какой знак использовать и т. д. Конечно, буквальная попытка написать программу как текст, скажем, из 10 тысяч символов„ записывая символы слева направо буква за буквой и выбирая 10 000 раз в каждом месте нужный символ из нескольких десятков возможных, может рассматриваться лишь как крайний, теоретический предел процесса принятия решений. Программист пишет. программу уже отправляясь от некоторого организованного знания решаемой задачи. Однако на пути передачи машине этого значения стоит очень много преград.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
