Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов
Рассмотрена задача выбора наилучшего элемента для случая, когда элементы разбиты на группы и за один шаг осуществляется одновременный просмотр элементов всей группы. Вначале доказывается две леммы относительно вида оптимального порядка просмотра групп, позволяющие понять структуру оптимального решен...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и вычислительная техника |
|---|---|
| Datum: | 2014 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84503 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Об оптимальном порядке просмотра групп в задаче выбора наилучшего элемента с групповым просмотром кандидатов / С.И. Доценко, П.А. Негадайлов // Кибернетика и вычислительная техника. — 2014. — Вип. 175. — С. 31-39. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Zusammenfassung: | Рассмотрена задача выбора наилучшего элемента для случая, когда элементы разбиты на группы и за один шаг осуществляется одновременный просмотр элементов всей группы. Вначале доказывается две леммы относительно вида оптимального порядка просмотра групп, позволяющие понять структуру оптимального решения. Затем, в рамках найденной структуры, строится генетический алгоритм, приближенно находящий оптимальное решение.
Розглянуто задачу оптимального вибору у випадку, коли елементи розбито на групи та за один крок здійснюється одночасний перегляд елементів групи. Спочатку доведено дві леми, щодо оптимального порядку перегляду груп, які дозволяють зрозуміти структуру оптимального розв’язку. Потім, з урахуванням знайденої структури, знайдено генетичний алгоритм, що знаходить оптимальний розв’язок.
Purpose: We try to find the best order of viewing groups which maximize the probability of selecting the best candidate, provided that optimal stopping rule, based on the “Bruce’s theorem” is applied and we compare this probability for the best and the worst cases. As may be expected, the lower bound for the worst case is the probability to find the best element at the classical secretary problem, i.e. 1/e.
|
|---|---|
| ISSN: | 0452-9910 |