Войти  |  Регистрация
Авторизация

Комбинаторный поиск



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

Примеры

Пример №1 (простейший комбинаторный поиск): В конкурсе участвуют 6 учеников, обозначим их 1,2,3,4,5,6. Как могут распределиться места между участниками в конкурсе? (1,2,3,4,5,6) (3,5,6,1,2,4) (2,4,3,1,6,5) Вариантов существует, ровно столько сколько существует вариантов перестановок из шести чисел.

Пример №2: Та же задача, но теперь для 6 участников конкурса есть три призовых места. Может быть призовые места распределятся 4,6,1, или 5,2,3, очевидно, что вариантов распределения в тройке победителей, может быть ровно столько, сколько существует способов выбора трех чисел из шести.

Пример №3: Усложняем задачу, когда для участников конкурса появляется возможность занять 1, 2 или 3 призовое место. Теперь нужно рассмотреть не только варианты, когда участник попадает в призовую тройку, но и то, как распределятся 1, 2 и 3 место между призерами.

Простейшие комбинации, с которыми имеет дело комбинаторный поиск - сочетания, размещения, перестановки.

Сочетанием из n элементов по m при 1 ≤ m ≤ n – называется всякая комбинация, объединяющая m каких-нибудь элементов из числа данных n элементов. Две такие комбинации считаются различными, если какой-нибудь из данных n элементов входит в одну из них, но не входит в другую комбинацию.

Размещением из n элементов по m при 1 ≤ m ≤ n - называется всякая комбинация, объединяющая в определенном порядке m каких-нибудь элементов из числа данных n элементов. Две такие комбинации считаются различными, если они отличаются либо своим составом, либо порядком следования входящих в них элементов. Либо и тем и другим.

Размещение из n элементов по n элементов называется перестановкой из данных n элементов.

Принципы комбинаторики

Существуют два основных принципа:

Принцип сложения

Предположим, что та или иная задача решается любым из k методов, причем первый метод можно применить n1 способами, второй метод n2 способами, ……., k-й метод nk способами. Тогда задача решается n1 + n2 + ……. nk способами.

Принцип умножения

Предположим, что та или иная задача решается за k последовательных этапов, причем число способов решения задачи на каждом следующем этапе не зависит от того, какими именно возможными способами она решалась на всех предыдущих этапах, и составляет n1 способов на первом этапе, n2 на втором этапе …nk способов на k-м этапе. Два решения считаются разными, если они получены по-разному хотя бы на одном из этапов. В этих условиях задачу можно решить n1 + n2 + ····· nk способами.


Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent