поговорим о ЛОНИИС

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.

Вы здесь » поговорим о ЛОНИИС » КОММЕНТАРИИ к ПРОГРАММАМ » Моделирование паросочетаний

Моделирование паросочетаний

Страница: 1

Сообщений 1 страница 3 из 3

1

  • Автор: ABC
  • Активный участник
  • Зарегистрирован: 2010-09-27
  • Приглашений: 0
  • Сообщений: 5915
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    2 месяца 25 дней
  • Последний визит:
    Сегодня 14:32:18

Программа  uuuu

Программа uuuu
DELPHI 7

Скачать
https://yadi.sk/d/P91561Ui3Lk5mX

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

Есть множество женихов.
Всего  n.
Каждому жениху - вершина во множестве A.
Есть множество невест.
Всего  n.
Каждой невесте  - вершина во множестве B.
Каждый юноша согласен на брак с m невестами.
Выбор невест случаен.
Каждая невеста  согласна на брак с m женихами.
Выбор женихов  случаен.
От каждой вершины множества A – m голубых ребер к m вершинам
множества B.
От каждой вершины множества B  – m розовых  ребер к m вершинам
множества A .
Если между двумя вершинами множеств A и B и голубое ребро,  и розовое ребро,
то вершины соединяются красным ребром.
При заключении брака две вершины множеств A и B соединяются пурпурным ребром.
Множество пурпурных ребер подмножество красных ребер.
Каждой вершине инцидентно  одно пурпурное ребро.
Или не одного.
Находится максимальное число пурпурных ребер (число браков).

2. Исходные данные

g- число циклов для сбора статистики
S – число женихов (невест)
n1, m1 – число женихов (невест) и число предпочтений женихов (невест),
комбинация для вывода промежуточного  расчёта

3.  Массивы

c1 – голубые ребра для n1, m1
c2 – вспомогательный массив
c3 – розовые ребра для n1, m1
z - Пурпурные и красные ребра для n, m
Пурпурные: совпадение предпочтений женихов и невест
Пурпурные отмечены цифрой 1.
Красные – браки.
Отмечены цифрой 2.

4. Алгоритм

4.1.Находятся предпочтения женихов
4.2. Находятся предпочтения невест.
4.3. Находятся совпадения предпочтений женихов и невест.
4.4. Находятся браки по предпочтениям женихов и невест.
То есть некоторое допустимое паросочетание.
Есть стандартные алгоритмы отыскания максимального паросочетания
http://studopedia.ru/2_106771_parosoche … rafah.html
http://www.studfiles.ru/preview/1619036/
А как в реальной жизни?
Брачные конторы или свахи имеют цель заключить наибольшее число браков.
Просматривают комбинации для увеличения числа сочетающихся.
Индивидуальные пары естественно сочетаются без оглядок на общее число сочетающихся.
Условно назовем такой выбор:
«Увидел, взял».
Такой алгоритм в данной программе.

5.  Статистика

Единичные расчёты дают результаты с большим разбросом.
Поэтому введен цикл статистика.
Расчёты повторяются g раз.
Полученные результаты усредняются.

5. Конечные результаты в двух таблицах.

Для сочетаний 
n  и m: число женихов (невест) и число предпочтений одного  жениха (невесты).
n  и m:  n>=m, n  и m от 1 до s 

Таблица 4. Частное от деления числа удвоенного числа допустимых браков на  (сумма женихов и невест *n * g).
Массив f2.
Таблица 5 
Массив x2
Частное от деления числа браков на (число женихов (невест) * n * g).
Для сочетаний  n и m.

Отредактировано ABC (2021-12-06 20:52:19)

0

2

  • Автор: ABC
  • Активный участник
  • Зарегистрирован: 2010-09-27
  • Приглашений: 0
  • Сообщений: 5915
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    2 месяца 25 дней
  • Последний визит:
    Сегодня 14:32:18

Программа vvvvvv

1. Распознавание

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

2. Программа uuuu.

Выше описана программа uuuu.
По этой программе.
От каждого жениха отходит m  дуг.
Это соответствует числу сравнений некоторого признака с признаками реального объекта.
От каждого невесты  отходит m  дуг.
Это соответствует числу сравнений некоторого признака реального объекта с эталонным.
При полном совпадении противоположно направленных дуг реальный объект 100% соответствует эталонному.
По жизни реальный образ маскируют помехи.
То есть  несовпадение противоположно направленных дуг.
В задаче uuuu дуги от невест выбираются случайным образом.
Изучается:  какая вероятность ошибочного опознавания случайного объекта как эталонного.
Сравнение проводится по двум критериям.
А) d(n,m) – браки.
Число случаев совпадения противоположно направленных дуг.
По одному совпадению для каждого признака.
Б) f1(n,m) – отношение удвоенного числа совпадения дуг к общему числу дуг.


3. Программа vvvvvv

В программе vvvvvv число дуг по каждому признаку (жених, невеста) определяется случайно.
По случайным направлениям.
Равновероятно в диапазоне 1 … m.
Математическое ожидание ряда натуральных чисел 1 … m  равно (m+1) : 2.
Следовательно число дуг в  программах uuuu и vvvvvv будет равно при выполнении
условия АА:
uuuu  m=k
vvvvv m= (k+1) :2

4. Результат

Для условия АА
d(n,m) почти совпадают.
f1(n,m)для uuuu f1(n,m)для vvvvvv 

Пример
q = 30
s = 20
n1= 17
m1 = 6

uuuu
d(17,6)  = 0,0200
f1(17,6) = 0,7451

vvvvvv
d(17,6)  = 0,0205
f1(17,6) = 0,6647

uuuu
скачать
https://yadi.sk/d/P91561Ui3Lk5mX

vvvvvv
скачать
https://yadi.sk/d/Gd0YJKE-3Mq8aV

Отредактировано ABC (2017-09-12 23:21:32)

0

3

  • Автор: ABC
  • Активный участник
  • Зарегистрирован: 2010-09-27
  • Приглашений: 0
  • Сообщений: 5915
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    2 месяца 25 дней
  • Последний визит:
    Сегодня 14:32:18

Программа 1-tttt

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

Режим 1.
Переключатели
k1 =0 (для женихов)
k2 =0 (для невест)
Каждый жених (невеста): заданное число предпочтений.

Режим  2 Переключатели
k1 = 2 (для женихов)
k2 = 2 (для невест)
Каждый жених (невеста): случайное число предпочтений.

Режим 3
k1 =0
k2 = 2
Женихи – фиксированное число предпочтений, невесты - случайное.

Режим 4
k1 =2
k2 = 0
Женихи – случайное предпочтение, невесты - фиксированное.

Режим 5 в дополнении к режимам 1-4
(каприз невесты)
Если выполняется соотношение
V  >  (random (w)+ 1)
Предпочтение аннулируется.
v и w задаются

Введена величина k – сумма браков по всему циклу статистика.

Скачать программу 1-tttt

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

Отредактировано ABC (2017-10-23 01:43:03)

0

Страница: 1

Вы здесь » поговорим о ЛОНИИС » КОММЕНТАРИИ к ПРОГРАММАМ » Моделирование паросочетаний