1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 8
Текст из файла (страница 8)
Не исключено, что он даже найдет индивидуальное доказательство этому примеру, но нам сейчас важно сделать другой, более общий вывод: ширина сечения уже не может быть для нас ориентиром в определении чвсла величин, требуемых для экономного распределения памяти. Все это, вместе взятое, окончательно хоронит попытку спасти нашу процедуру как способ наилучшего распределения памятиг $ ЬЗ. НАКОПЛЕНИЕ ФАКТОВ. ПРОГРАММЫ ОБШЕГО ВИДА 39 мы получаея с ее помощью некоторое распределение памяти, но уже не можем утверждать, что.оно наилучшее. Несовместимость. Однако суждение в такой негативной форме нас не устраивает.
Прежде чем расстаться с найденной для линейных программ и подправленной для общего случая процедурой экономии памяти, нам нужно более внимательно рассмотреть, что в ней достоверно, а что нет. Давайте еще раз посмотрим,чтб мы в ней делаем: двигаясь по операторной схеме с построенными информационными связями, мы: а) определяем, какие связки друг с другом конкурентны, а какие нет, и б) нааначаем связкам те или иные имена величин, стараясь обойтись их наименьшим количеством.
Мы уже увидели, что для определения взаимной конкурент- ности связок 1нам уже пора заменить это случайно появившееся образное название на специальный термин — давайте называть это несовместимостью связок) нам не нужны имена величин: две связки несовместимы, если начальный оператор какого-нибудь маршрута, реализующего какую-нибудь информационную свяаь одной связки, является начальным или внутренним оператором какого-нибудь маршрута, реализующего какую-нибудь информационную связь другой связки 1извините за длинную фразу— зато совершенно точно!). Таким образом, информация о несовместимости по операторной схеме обнаруживается однозначно, а свобода выбора и неоднозначность результатов у нас получается при назначении величин на связки. Сама по себе неоднозначность не страшна: она дает возможность строить разные варианты распределения памяти. Для линейных программ она также не мешала нам найти наилучший результат: там мы знали заранее наименьшее число величин и как его достичь.
При попытке сохранить алгоритм в общем случае.мы себя привязывали к выбранному направлению движения по схеме и старались назначить величину новому результату немедленно по его обнаружении. Из-за сложной структуры связок, мы, так сказать, опережая события, «аабрасывалиэ имена величин на еще не пройденные участки схемы и тем самым, когда впоследствии попадали туда, окааывались в тесных рамках ранее сделанных выборов. Действуя «в малом», в окрестности одного сечения, мы пользовались частичной информацией о несовместимости только данного нового результата с его конкурентами, не имея общей картины о несовместимости связок для программы в целом. Так у нас появляется мысль о разбиении процедуры распределения памяти на две части: а) получение общей информации о несовместимости и б) на основе анализа общей информации о несовместимости выбор того или иного распределения памяти, желательно наилучшего.
Попробуем немедленно проверить эту идею на нашем примере 10. Нам надо в каком-то наглядном виде представить информацию о гл. 1. содегжАтильныи АБАлиз зАЛАчи несовместимости связок..Соберем ее сначала, так сказать, в буквальном виде.
Сначала связки надо обозначить. Обоаначим их символами операторов, чьи результаты начинают эти связки. Это будут: (вв1Д, (ев2, Ьз), 1у, +, аЬз. Мы имеем (вв1?) несовместим с (вв2, ?и) и аЬв (ев2, (п) несовместим с (вв1,/) и гу 1у несовместим с (вв2, ?п) и + + несовместим с гу и аЬа аЬз несовместим с + и (вв1,!) Эта таблица не очень наглядна,но мы улавливаем какую-то цикличность в ее строении, которую хотелось бы представить в более доступном обоарению виде. Цикл — это окружность — или замкнутая ломаная.
Замкнутая ломаная в свою очередь — это вершины и стороны. Что у нас вершины и чтб стороны? Сторона соединяет две вершины, понятие неЖ7 1а д совместимости относится к двум связкам. Хорошо( Мы обозначаем связки большими точками — вершинами а а ломаной, а вершины неав1/ 1 совместимых связок соединяем линией. Получаем рис. 1.8. Граф иесовместимостя. Автор вправе рассчитывать, что большинство читателей знакомо с мад тематическим понятием ааз + графа.
Мы его формально введем в следующей главе, Рис. 1.8. Наглядное оредставлеиие ии- а для новичков скажем, формации о несовместимости связок. что (неориентированный) граф состоит из вершин и ребер, их соединяющих. На чертеже вершины изображаются точками (или кружками), а ребра — соединительными линиями. Вершины, соединенные ребрами, называются снелснмми. Вернемся к нашей задаче. Граф на рис. 1.8 изображает сводные данные о совместимости и несовместимости связок информационных свяаей. Сам граф можно в связи с этим назвать графом несовместимости.
Вершинами графа являются связки. Смежными вершинами в графе являются несовместимые связки, и наоборот, любые две несмеяные связки являются совместимыми. Распределение памяти на графе несовместимости выглядит так, что надо $ ьз. ИАкопленив ФАктоВ. ИРОРРАммы ОВЩВГО ВИДА 41 каждой вершине сопоставить величину, но так, чтобы никакой паре смежных вершин не сопоставлялась бы одна величина. Экономия будет достигаться тем, что разным несмежным вершинам будет сопоставляться одна и та же величина. Опять-таки автор может рассчитывать, что часть читателей, прочитав условие задачи зкономии памяти в атой формулировке, усмотрит в ней прямую связь со знаменитой задачей теории графов — задачей о раскраске вершин графа: надо раскрасить вершины графа в наименьшее число красок так, чтобы никакая пара смежных вершин не оказалась раскрашенной одной краской.
Этот факт сам по себе очень интересен, но сейчас мы не будем отвлекаться, а опять вернемся к нашему примеру. Распределим память для наших связок. Так как они в графе несовместимости обраауют цикл, то все равно, с какой вершины начинать. Сопоставив Вершине (ав1,!) величину а, мы неизбежно сопоставим смежной вершине (вв2, Ьх) величину Ь, но следующей связке гл можем опять сопоставить а. Величины а и Ь при движении по часовой стрелке будут чередоваться.
Так будет, пока мы не подойдем к вершине аЬя, замыкающей цикл. Мы не только видим, что ей неизбежно придется сопоставить третью величину, но и понимаем, когда бы мы могли обойтись только двумя: если последняя вершина 2 будет смыкать цепочку четного числа вершин, то ее концам будут сопоставлены разные величины, н вершине 2 понадобится третья величина; если 'цепочка содержит нечетное число вершин„то ее концам сопоставлена одна величина, тогда вершине У можно сопоставить вторую величину. Как видно, у нас благодаря введению такой новой конструкции, как граф несовместимости, появляется источник доказательства минимального расходования памяти совершенно другой природы, уже очень косвенно связанный со структурой программы, но зато выдающий исходную информацию для распределения памяти в «чистой» форме, не обремененной никакими деталями.
Получив эту новую форму нам, естественно, будет интересно перепроверить, как сна работает дл)г разобранных цдмн ранее примеров зкономии памяти. Автор рекомендует читателям самостоятельно построить графы несовместимости для примиряв 4-9, честно предупредив, что им придется немного повозиться, чтобы изобразить их на рисунке достаточно красиво н наглядно, Для контроля и небольшого последующего обсуждения все графы изображены на рис. 1.9. Связки в примерах 1, 2 и 9 обозначены именами величин, использованных в начальном варианте программы.
Величины, выбранные прн зкономном распределении, помещаются рядом с соответствующими вершинамн графа. Приоры 3 и 4 пропущены, так как нам еще не ясно, как строить операторную схему для программ, содержащих операторы цикла. В примерах 5 и 6; 7 и Э Гл. 1, содержАтельныи АЫАлиз задАчн связки обозначаются именами операторов, вырабатывающих относящиеся к этим связкам результаты. Во всех случаях мннимаиьность числа величин, испольаованных для «раскраски» вершин графа несовместимости, очевидна. Обращает на себя внимание наличие в примерах 5, б и 9 своего рода ядер в графах — групп вершин, попарно смежных друг другу н поэтому требующих заведомо разных величин. Все остальные вершины существенно у Ыу аГ Рис. $.9. Графы несовместимости. а) Примеры $, 2. 6) Примеры 5, 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
