Понятие задачи выбора

Теоретическая часть

Лабораторная работа №3.Разработка полно-переборных алгоритмов решения задач выбора.

Способ оценки результатов

Критерии оценки результатов совпадают с критериями, определенными при описании лабораторной работы №1 в разделе «Способ оценки результатов».

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

Требования к содержанию, оформлению и порядку выполнения

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

Теоретические сведения, необходимые для выполнения лабораторной работы, представлены в разд.2.1-2.2 и 3.1. Также дадим дополнительные понятия необходимые для выполнения данной лабораторной работы.

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

Пример 1. Есть множество камней, для каждого из которых задана масса. Нужно ответить на вопрос, можно ли разделить данное множество на две равные по массе части.

Пример 2 (Задача коммивояжера). Коммивояжер (агент по сбыту), отправляясь из своего города, должен ровно по одному разу посетить n -1 заданных городов и вернуться назад, затратив при том минимальную сумму на поездку. Какой маршрут ему выбрать, если затраты на проезд между городами заданы.

Пример 3. Заданные n масс m ₁, m ₂,..., m_n, требуется распределить в пространстве, в точках M ₁, M ₂,…, M_n, так, чтобы их центр тяжести был максимально близок к фиксированной точке M ₀.

Для задач выбора характерно:

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

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

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

Варианты выбора называются траекториями. Числовая характеристика варианта называется его функционалом.

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

Дата добавления: 2014-12-27