Главная  Полное построение алгоритма 

[0] [ 1 ] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

Шаг 2. [Проверка каждого числа] For /С-<-2 to N do шаг 3 od; and STOP.

Шаг 3. [Сравнение] If M<:R (К) then set MR (K); and JK fi (теперь M - наибольшее число из проверенных, а К - его номер в массиве).

Алгоритм МАХ не закодирован на каком-то языке, а записан в форме, которую легче воспринять; он выражен в виде шагов, которые легко реализуются в каждом общепринятом языке программирования. От такого представления нетрудно перейти к кодовой форме. Однако так бывает не всегда. Некоторые алгоритмы слишком сложны, чтобы перейти за один шаг от предварительного словесного описания к кодам машины. Может потребоваться ввести по крайней мере один промежуточный этап разработки.

1.3. Основные этапы полного построения алгоритма

Теперь мы кратко рассмотрим основные этапы, перечисленные в конце разд. 1.1. Прежде всего определим назначение каждого этапа и выясним, как эти этапы объединяются в единое целое.

Постановка задачи

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

Обычно процесс точной формулировки задачи сводится к постановке правильных вопросов. Перечислим некоторые полезные вопросы для плохо сформулированных задач:

Понятна ли терминология, используемая в предварительной формулировке? Что дано? Что нужно найти? Как определить решение?

Каких данных не хватает и все ли они нужны? Являются ли какие-то имеющиеся данные бесполезными? Какие сделаны допущения?

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

Пример. Джек - агент по продаже компьютеров (коммивояжер); на его территории 20 городов, разбросанных по всему Техасу. Компания возмещает ему только 50% стоимости деловых автомобильных поездок. Джек вычислил, сколько ему будет стоить переезд на машине



между каждыми двумя городами на его территории. Ему, естественно, хотелось бы снизить свои дорожные расходы.

Что дано? Исходная информация задана в виде перечня городов на территории Джека и соответствующей матрицы стоимостей, т. е. двумерного массива с элементами Ctj, равными стоимости переезда из города i в город /. В данном случае матрица стоимостей имеет 20 строк и 20 столбцов.

Что мы хотим найти? Мы хотим Помочь Джеку снизить его дорожные расходы. Это звучит несколько туманно. Действительно, вопрос о том, каким будет решение, выглядит неуместным. Обдумав ситуацию, мы придем к выводу, что ничего не можем сделать без дополнительной информации от Джека. Имеет ли Джек в одних городах больше покупателей, чем в других? Если да или если есть какие-то особые покупатели, то Джек, возможно, захочет посещать какие-то города чаще. Могут быть и такие города, в которые- Джек специально не поедет, а заедет туда, когда окажется в соседнем городе. Другими словами, нам надо знать больше о приоритетах Джека и учитывать предпочтения при составлении графика поездок.

Поэтому мы возвращаемся к Джеку и требуем у него дополнительную информацию. Он сообщает, что хотел бы иметь маршрут, начинающийся и оканчивающийся в его базовом городе и проходящий по одному разу через все остальные города на его территории. Следовательно, нам требуется список городов, содержащий каждый город только один раз, за исключением базового города, который стоит в списке первым и последним. Порядок городов в этом списке представляет собой маршрут, по которому Джек должен объезжать города на своей территории. Сумма стоимостей проезда между каждыми двумя последовательными городами списка - это общая стоимость маршрута, представленного списком. Мы решим задачу Джека, если представим ему список с наименьшей возможной общей стоимостью.

Это хорошая исходная постановка задачи. Мы знаем, что мы имеем и что хотим найти.

Построение модели

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

Как вы можете догадаться, невозможно предложить набор правил, автоматизирующих стадию моделирования. Большинство задач должно рассматриваться индивидуально. -Тем не менее существует несколько полезных руководящих принципов. Выбор модели - в большей степени дело искусства, чем науки, и, вероятно, эта тенденция сохранится. Изучение удачных моделей - это наилучший способ приобрести опыт п моделировании.



Приступая к разработке модели, следует задать по крайней мере два основных вопроса:

1. Какие математические структуры больше всего подходят для задачи?

2. Существуют ли решенные аналогичные задачи?

Второй вопрос, возможно, самый полезный во всей математике. В контексте моделирования он часто дает ответ на первый вопрос. Действительно, большинство решаемых в математике задач, как правило, являются модификациями ранее решенных. Большинство из нас просто не обладает талантом Ньютона, Гаусса или Эйнштейна, и для продвижения вперед нам приходится руководствоваться накопленным опытом.

Сначала нужно рассмотреть первый вопрос. Мы должны описать математически, что мы знаем и что хотим найти. На выбор соответствующей структуры будут оказывать влияние такие факторы, как: 1) ограниченность наших знаний относительно небольшим количеством структур, 2) удобство представления, 3) простота вычислений, 4) полезность различных операций, связанных с рассматриваемой структурой или структурами.

Сделав пробный выбор математической структуры, задачу следует переформулировать в терминах соответствующих математических объектов. Это будет одна из возможных моделей, если мы можем утвердительно ответить на такие вопросы, как:

Вся ли важная информация задачи хорошо описана математическими объектами?

Существует ли математическая величина, ассоциируемая с искомым результатом?

Выявили мы какие-нибудь полезные отношения между объектами модели?

Можем мы работать с моделью? Удобно ли с ней работать?

Пример. Возвращаемся к задаче агента по продаже компьютеров, рассмотренной ранее в этом разделе. Начинаем с постановки задачи, данной в конце примера.

Решали ли мы ранее аналогичные задачи? В математическом смысле, вероятно, нет. Однако все мы сталкивались с задачами выбора пути по дорожным картам или в лабиринтах. Можем ли мы прийти к удобному представлению нашей задачи наподобие карты?

Очевидно, нужно взять лист бумаги и нанести на нем по одной точке, соответствующей каждому городу. Мы не собираемся изображать точки так, чтобы расстояние между каждой парой точек, соответствующих городам i и /, было пропорционально стоимости проезда Cjj. Расположим точки любым удобным способом, соединим точки i и / линиями и проставим иа них «веса» сц.



[0] [ 1 ] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0011