алгоритм Гэйла — Шепли

Содержание

1. О проекте
2. Getting Started
3. Использование
4. Архитектура
5. Контакты

О проекте

Web-приложение симулирует работу алгоритма Гэйла — Шепли, предназначенного для поиска стабильных паросочетаний (мэтчингов).

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

---

Алгоритм заключается в следующем: каждый мужчина делает предложение первой женщине в своём списке. Каждая женщина отвечает «может быть» своему поклоннику, которого она предпочитает больше всего, и «нет» всем остальным женихам. Затем она временно «обручена» с женихом, которого она до сих пор предпочитает больше всего, и этот жених также временно обручен с ней.

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

Этот процесс повторяется до тех пор, пока все не будут задействованы.

---

(back to top)

Getting Started

Сборка и развертывание реализованы с использованием Github pages: https://github.com/avo-milas/matching_app

(back to top)

Использование

• Ознакомиться с описанием работы и основных функций можно, нажав на иконку информации на главном меню:

• В левой части экрана можно ознакомиться с текстовым описанием работы алгоритма.

Запуск по шагам:

Контейнер с результатами:

• В правой части экрана - визуализация:

На иконках представлены фотографии студентов потока HSE EDA'26, обработанные с помощью неройсети Шедеврум.

Могут быть установлены кастомизированные иконки путем добавления фотографий в папку images в формате [prefix][num].png, где prefix принимает два значения "m" и "w" в зависимости от стороны, а num (номер) - целочисленные значения от 1 до 10.

(back to top)

Архитектура

1. Основные функции:

• Функции визуализации:

  • showConnectionLine(manIndex, womanIndex, stepIndex): отображает линию соединения между мужчиной и женщиной на основе текущего шага алгоритма. Устанавливает координаты линии, цвет, стиль и анимацию.
  • clearConnectionLines(): удаляет все линии соединения на экране.
  • deleteConnectionLine(line_id): удаляет конкретную линию соединения по её ID.
  • createCircles(type, startCnt, endCnt): создает иконки для мужчин и женщин, используя фотографии или обезличенные иконки.
  • displayPairs(pairs): отображает таблицу с результатами после выполнения алгоритма.

• Функции инициализации и сброса:

  • resetAlgorithm(): очищает текущее состояние и готовит новые параметры для запуска алгоритма. Перемешивает массивы фотографий и создаёт иконки для мужчин и женщин.
  • clearResults(): очищает контейнер с результатами и сбрасывает стили иконок.

• Алгоритм Гейла-Шепли:

  • isEngaged(woman, stablePairs): проверяет, занята ли женщина на текущий момент.
  • galeShapleyWithSteps(menPrefs, womenPrefs): запускает алгоритм Гейла-Шепли по шагам - выполняет итерации, в которых мужчины делают предложения, а женщины выбирают из них лучшие варианты. Возвращает пары, шаги алгоритма и промежуточные состояния.

• Функции запуска алгоритма:

  • runAlgorithm(): запускает алгоритм и отображает конечные пары, использует кэшированные результаты, если предпочтения не изменились.
  • runAlgorithmWithSteps(): запускает алгоритм по шагам, отображая промежуточные состояния, использует кэшированные результаты, если предпочтения не изменились.

2. Вспомогательные функции:

   • getRandomInRange: случайное число из заданного промежутка
   • areSetsEqual: проверка на равенство сетов
   • isEqual: проверка на равенство двух объектов
   • shuffleArray: перемешивание массива в случайном порядке

3. Взаимодействие с DOM

Используются методы для работы с элементами DOM, такие как getElementById, createElement, appendChild, и setAttribute, чтобы динамически изменять содержимое страницы. Функции визуализации и сброса взаимодействуют с элементами SVG для отрисовки линий.

4. Глобальные переменные и константы

• cachedResults, cachedPreferences: кэшированные результаты выполнения алгоритма, чтобы избежать повторных вычислений.
• pairsCnt: количество пар, задаваемое пользователем через интерфейс.
• menIndToName, womenIndToName, menNameToInd, womenNameToInd: отображение индексов на имена мужчин и женщин.
• linesToDelete: набор для хранения ID линий, которые нужно удалить через шаг.
• menNamesArray, womenNamesArray: предопределенные имена

5. Логика проверки и обновления

Проверка корректности предпочтений и их изменений выполняется функциями mapNames и checkPreferencesChanged. Обновление состояния алгоритма и его визуализация управляется функциями runAlgorithm и runAlgorithmWithSteps.

(back to top)

Контакты

Alina Salimova - @avo_milas - avo_milas@mail.ru

Project Link: https://github.com/avo-milas/matching_app

(back to top)