Основные этапы разработки алгоритма1. Определение операций выполнения преобразований исходного графа в граф результата. Определяются по результатам анализа математической постановки задачи. Исходные данные: граф, его характеристики и свойства, целевая функция и ограничения. Анализируя эту информацию, определяем элементарные теоретико-множественные и алгебраические операции над графами, необходимые для преобразования исходного графа в граф результата. 2. Выбор способа представления графа и его представления в памяти ЭВМ, т.е. структур данных. Организация данных в памяти ЭВМ должна обеспечить высокую эффективность их обработки и экономное использование объема. От способа представления графа и его реализации в значительной степени зависят как вычислительная, так и емкостная сложность алгоритма. Выбор способа представления графа определяется главным образом видом операций его преобразования. 3. Конструирование или выбор решающих правил, обеспечивающих удовлетворение оценочной функции. Осуществляется исходя из критериев оценки оптимальности решения. 4. Анализ возможных способов решения задачи и выбор или модификация приемлемого. Анализ опирается на априорные представления о вычислительной и емкостной сложности и точности алгоритмов, построенных на их основе, и должен учитывать максимальную размерность задачи. 5. Разработка алгоритмической модели процесса решения задачи. Алгоритмическая модель – описание процесса решения задачи, отражающее основные этапы. Главная идея алгоритмической модели – описать идею алгоритма с такой полнотой и степенью детализации, которая позволила бы оценить ожидаемую вычислительную и емкостную сложность алгоритма, возможно доказать его точность и получить ее оценки. 6. Доказательство точности алгоритма оценка погрешности разработанного алгоритма. 7. Оценка вычислительной и емкостной сложности. 8. Детальная проработка алгоритма. Детальное описание алгоритма отличается от алгоритмической модели, в нем нельзя опускать операции, которые не существенны с точки зрения вычислительной и емкостной сложности. Форма записи операций над графами должна быть в максимальной степени приближена к конструкциям выбранного языка программирования, а алгоритм должен строится в соответствии с принципами структурного программирования. Структуру алгоритма рекомендуется представлять в виде блок-схем. Выбираются методы снижения вычислительной сложности: - использование рекуррентных процедур для определения состава таких множеств некоторых объектов, состав которых в результате преобразований меняется частично - применение рекуррентных формул или процедур для определения новых критериев и оценочных функций - исключение повторного расчета значений критериев / оценочных функций для тех подмножеств, для которых они не меняются - заблаговременное исключение вариантов решений, не отвечающих ограничениям задачи
|
