[size=20][color=maroon]Программаuuuu

[/color][/size]

[size=20][color=purple]Программа uuuu

DELPHI 7[/color][/size]

[size=20][color=green]Скачать[/color][/size]

https://yadi.sk/d/P91561Ui3Lk5mX

[size=20][color=navy]1. Постановка задачи

[/color][/size]

[size=18]Есть множество женихов.

Всегоn.

Каждому жениху - вершина во множестве A.

Есть множество невест.

Всегоn.

Каждой невесте- вершина во множестве B.

Каждый юноша согласен на брак с m невестами.

Выбор невест случаен.

Каждая невестасогласна на брак с m женихами.

Выбор жениховслучаен.

От каждой вершины множества A – m голубых ребер к m вершинам

множества B.

От каждой вершины множества B– m розовыхребер к m вершинам

множества A .

Если между двумя вершинами множеств A и B и голубое ребро,и розовое ребро,

то вершины соединяются красным ребром.

При заключении брака две вершины множеств A и B соединяются пурпурным ребром.

Множество пурпурных ребер подмножество красных ребер.

Каждой вершине инцидентноодно пурпурное ребро.

Или не одного.

Находится максимальное число пурпурных ребер (число браков).[/size]

[size=20][color=navy]2. Исходные данные[/color][/size]

[size=18]g- число циклов для сбора статистики

S – число женихов (невест)

n1, m1 – число женихов (невест) и число предпочтений женихов (невест),

комбинация для вывода промежуточногорасчёта

[/size]

[size=20][color=navy]3.Массивы[/color][/size]

[size=18]c1 – голубые ребра для n1, m1

c2 – вспомогательный массив

c3 – розовые ребра для n1, m1

z - Пурпурные и красные ребра для n, m

Пурпурные: совпадение предпочтений женихов и невест

Пурпурные отмечены цифрой 1.

Красные – браки.

Отмечены цифрой 2.[/size]

[size=20][color=navy]4. Алгоритм

[/color][/size]

[size=18]4.1.Находятся предпочтения женихов

4.2. Находятся предпочтения невест.

4.3. Находятся совпадения предпочтений женихов и невест.

4.4. Находятся браки по предпочтениям женихов и невест.

То есть некоторое допустимое паросочетание.

Есть стандартные алгоритмы отыскания максимального паросочетания

http://studopedia.ru/2_106771_parosochetaniya-v-dvudolnih-...

http://www.studfiles.ru/preview/1619036/

А как в реальной жизни?

Брачные конторы или свахи имеют цель заключить наибольшее число браков.

Просматривают комбинации для увеличения числа сочетающихся.

Индивидуальные пары естественно сочетаются без оглядок на общее число сочетающихся.

Условно назовем такой выбор:

«Увидел, взял».

Такой алгоритм в данной программе.

[/size]

[size=20][color=navy]5.Статистика[/color][/size]

[size=18]Единичные расчёты дают результаты с большим разбросом.

Поэтому введен цикл статистика.

Расчёты повторяются g раз.

Полученные результаты усредняются.[/size]

[size=20][color=navy]5. Конечные результаты в двух таблицах.[/color][/size]

[size=18]Для сочетаний

nи m: число женихов (невест) и число предпочтений одногожениха (невесты).

nи m:n>=m, nи m от 1 до s

[/size]

[size=18]Таблица 4. Частное от деления числа удвоенного числа допустимых браков на(сумма женихов и невест *n * g).

Массив f2.

Таблица 5

Массив x2

Частное от деления числа браков на (число женихов (невест) * n * g).

Для сочетанийn и m.

[/size]

/////////////////////////////////////////////

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

[size=20][color=navy]Программа vvvvvv

[/color][/size]

[size=20][color=maroon]1.Распознавание[/color][/size]

[size=18][color=blue]Математическая модель – паросочетание соответствует задаче распознавание.

Соответствие.

Множество женихов – эталонная модель образа.

Множество невест – образ объекта на распознавание.

Ребра (дуги) от женихов к невестамзадают множество признаков эталонного образа.

Ребра (дуги) от невест к женихам задаютмножество признаков распознаваемого объекта.

Соответствие противоположно направленных дуг (ребер женихов, невест) соответствует совпадению признака эталонного и реального объектов.

По каким критериям определять соответствие эталонного и реального объекта, зависит от конкретной ситуации.

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

[/color][/size]

[size=20][color=maroon]2.Программа uuuu.[/color][/size]

[size=18][color=blue]Выше описана программа uuuu.

По этой программе.

От каждого жениха отходит mдуг.

Это соответствует числу сравнений некоторого признака с признаками реального объекта.

От каждого невестыотходит mдуг.

Это соответствует числу сравнений некоторого признака реального объекта с эталонным.

При полном совпадении противоположно направленных дуг реальный объект 100% соответствует эталонному.

По жизни реальный образ маскируют помехи.

То естьнесовпадение противоположно направленных дуг.

В задаче uuuu дуги от невест выбираются случайным образом.

Изучается:какая вероятность ошибочного опознавания случайного объекта как эталонного.

Сравнение проводится по двум критериям.

А) d(n,m) – браки.

Число случаев совпадения противоположно направленных дуг.

По одному совпадению для каждого признака.

Б) f1(n,m) – отношение удвоенного числа совпадения дуг к общему числу дуг.

[/color][/size]

[size=20][color=maroon]3.Программа vvvvvv

[/color][/size]

[size=18][color=blue]В программе vvvvvv число дуг по каждому признаку (жених, невеста) определяется случайно.

По случайным направлениям.

Равновероятно в диапазоне 1 … m.

Математическое ожидание ряда натуральных чисел 1 … mравно (m+1) : 2.

Следовательно число дуг впрограммах uuuu и vvvvvv будет равно при выполнении

условия АА:

uuuum=k

vvvvv m= (k+1) :2[/color][/size]

[size=20][color=maroon]4.Результат[/color][/size]

[size=18][color=blue]Для условия АА

d(n,m) почти совпадают.

f1(n,m)для uuuu f1(n,m)для vvvvvv[/color][/size]

[size=18][color=blue]Пример

q = 30

s = 20

n1= 17

m1 = 6[/color][/size]

[size=18][color=blue]uuuu

d(17,6)= 0,0200

f1(17,6) = 0,7451[/color][/size]

[size=18][color=blue]vvvvvv

d(17,6)= 0,0205

f1(17,6) = 0,6647[/color][/size]

[size=18][color=blue]uuuu

скачать

https://yadi.sk/d/P91561Ui3Lk5mX[/color][/size]

[size=18][color=blue]vvvvvv

скачать

https://yadi.sk/d/Gd0YJKE-3Mq8aV

[/color][/size]

////////////////////////////////////////////////////////////////////

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

[size=20][color=red]Программа 1-tttt

[/color][/size]

[size=18][color=maroon]Дальнейшее исследование разных способов задания паросочетаний.

Программа работает в нескольких режимах:[/color][/size]

[size=18][color=purple]Режим 1.

Переключатели

k1 =0 (для женихов)

k2 =0 (для невест)

Каждый жених (невеста): заданное число предпочтений.

[/color][/size]

[size=18][color=lime]Режим2 Переключатели

k1 = 2 (для женихов)

k2 = 2 (для невест)

Каждый жених (невеста): случайное число предпочтений.

[/color][/size]

[size=18][color=olive]Режим 3

k1 =0

k2 = 2

Женихи – фиксированное число предпочтений, невесты - случайное.[/color][/size]

[size=18][color=teal]Режим 4

k1 =2

k2 = 0

Женихи – случайное предпочтение, невесты - фиксированное.

[/color][/size]

[size=18][color=navy]Режим 5 в дополнении к режимам 1-4

(каприз невесты)

Если выполняется соотношение

V>(random (w)+ 1)

Предпочтение аннулируется.

v и w задаются

[/color][/size]

[size=18][color=blue]Введена величина k – сумма браков по всему циклу статистика.

[/color][/size]

[size=20][color=green]Скачать программу 1-tttt[/color][/size]

https://yadi.sk/d/ByJKa-nU3NymEZ

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||