Технология программирования стр.66

• определение метода преобразования исходных данных в результат, т. е. метода решения задачи.

Для многих задач, которые часто встречаются на практике, в математике определены как модели, так и методы решения. К таким задачам, например, относится большинство задач аналитической геометрии на плоскости и в пространстве, задачи моделирования дискретных систем и т. д.

Основная проблема в подобных случаях - обоснование применимости той или иной математической модели для решения конкретной задачи.

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

•    особенности данных конкретной задачи, связанные с предметной областью (погрешность, возможные особые случаи и т. п.);

•    требования к результатам (допустимую погрешность);

•    характеристики метода (точный или приближенный, погрешности результатов, вычислительную и емкостную сложности, сложность реализациии т. п.).

Пример 4.8. Выполнить формальную постановку задачи поиска цикла минимальной длины (задачи коммивояжера).

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

Анализ условия задачи показывает, что математической моделью объектов системы и существующих или возможных связей между ними может являться взвешенный ориентированный или неориентированный граф G(X, <U, L>), где X, U, L - множества вершин, ребер и весов ребер соответственно.

Для перехода от объектов задачи к их математическим моделям необходимо [55]:

•    сформулировать правила соответствия компонентов объекта компонентам модели;

•    определить вид этих соответствий (взаимно однозначные, однозначные, многозначные);

•    определить способ отображения свойств и характеристик компонентов объекта в характеристики выбранной математической абстракции.

Все это определяется, исходя из отношений, существующих между компонентами объекта, а также свойств объекта и характеристик его компонентов.

В графе G множество Э объектов системы (городов) поставлено во взаимно однозначное соответствие множеству X, а множеству связей С между парами объектов (дорог) поставлено в такое же соответствие множество ребер U. Расстояние между городами (Sj, эj ) интерпретируется как вес соответствующего ребра w[xi, x j )

Таким образом, в терминах теории графов рассматриваемая задача - это поиск в ориентированном или неориентированном графе гамильтонова цикла минимальной длины.

В противном случае граф может не иметь гамильтонова цикла, что для нас означает, что в некоторых случаях задача может не иметь решения.

Задача относится к классу NP-сложных - задач, вычислительная сложность которых не выражается в виде полинома от размерности ее входа (количества городов), а носит экспоненциальный характер, т. е. очень быстро возрастает при увеличении размерности задачи. Известно, что точное решение задачи коммивояжера может быть получено алгоритмами, реализующими полный перебор или метод ветвей и границ. Приближенное решение дают методы поиска в глубину и двоичной свертки.

Поскольку по техническому заданию необходимо обеспечить получение точного решения, следует реализовать хотя бы по одному методу из указанных групп. Для выбора методов нужно провести дополнительные исследования.


⇐ назад к прежней странице | | перейти на следующую страницу ⇒

Читайте также:

Яркая жизнь с компьютерными программами

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

AlgoMusic M51 Galaxy - виртуальный инструмент на основе PD-синтеза

Виртуальный инструмент M51 Galaxy позволяет синтезировать "космические" звуки, обладает завораживающим звучанием. Обычно музыканты не очень жалуют инструменты, созданные с помощью SynthEdit. Однако M51, хоть и относится к их числу, действительно очень хорош. Секрет его звучания кроется в оригинальной архитектуре синтеза. На M51 Galaxy распространяется поговорка, что "все новое - это хорошо забытое старое". Идеи, заложенные в M51, уже были успешно реализованы в 80-х годах XX века.

Помоги себе сам

Что может быть обыденней интернета в наши дни? Он стал незаменимой частью жизни всех нас. И это можно понять, ведь с его помощью люди работаю во всевозможных сферах деятельности, является очень эффективным. Но очень часто стоит вопрос о том, с помощью чего лучше всего добиваться лучших результатов и делать это более оперативно и с комфортом.