Готовые Домашние Задания

Рефераты по теме Экологическое право

Реферат AGraph: библиотека классов для работы с помеченными графами

Скачать реферат↓ [36.62 KB]



Текст реферата AGraph: библиотека классов для работы с помеченными графами

AGraph: библиотека классов для работы с помеченными графами
§1. Актуальность разработки библиотек для работы с графами
К настоящему времени накоплен большой опыт решения теоретикографовых
задач на ЭВМ. Программы для решения многих задач можно найти в
глобальной сети Интернет. В то же время, использование независимо
разработанных программ сопряжено с большими трудностями. К их числу
относятся как общие, не зависящие от предметной области, технические
проблемы (различные языки программирования, несовместимость
программных и аппаратных средств), так и проблемы, связанные со
спецификой теоретикографовых задач (использование различных внутренних
представлений графов). В связи с этим актуальной задачей является
разработка более или менее универсальных библиотек, которые, с одной
стороны, предоставляли бы пользователю высокоуровневые средства для
работы с графами, а с другой, избавляли его от необходимости ручного
программирования рутинных операций вводавывода или преобразований
между различными внутренними представлениями графов.
Разработка универсальной библиотеки для работы с графами является
сложной задачей. Одной из проблем является большое разнообразие задач
теории графов. Поскольку теоретические исследования и разработка новых
алгоритмов непрерывно продолжаются, очевидно, что никакая библиотека
не сможет решать все существующие задачи. Другой проблемой является
обеспечение эффективности. Нередко существует несколько алгоритмов для
решения одной и той же задачи, причем не всегда можно указать
алгоритм, оптимальный во всех случаях: для одних графов более
эффективным может быть один алгоритм, для других другой. Разработчик
универсальной библиотеки обычно не может позволить себе реализацию
нескольких алгоритмов для решения одной задачи, поэтому ему приходится
идти на компромиссы между эффективностью и универсальностью. При
разработке библиотек для работы с графами возникают также
многочисленные технические трудности. Для приемлемой с точки зрения
эффективности реализации многих алгоритмов программисту необходимо
иметь в своем распоряжении такие структуры данных, как динамические
массивы, списки, стеки, очереди, приоритетные очереди, деревья поиска.
Реализация всех необходимых структур данных в рамках одной библиотеки
вряд ли возможна и оправдана, поэтому универсальная библиотека для
работы с графами требует серьезной программной "инфраструктуры" в виде
других библиотек.
Перечисленные проблемы могут вызвать сомнения относительно
целесообразности создания универсальных библиотек для работы с
графами, однако существуют весомые аргументы в пользу их создания.
Вопервых, реализованные в подобной библиотеке базовые алгоритмы могут
служить хорошей основой для создания более специализированных
алгоритмов и программ, направленных на решение конкретных прикладных
задач. Вовторых, соображения эффективности не всегда являются
определяющими постоянный рост производительности ЭВМ все чаще выводит
на первый план технологичность и скорость разработки