Задача об оптимальной последовательности проверки независимых гипотез

Автор(ы): Новиков Д.А.

Выпуск: 94

Рубрика: Системный анализ

Год: 2021

Библиография: Новиков Д.А. Задача об оптимальной последовательности проверки независимых гипотез // Управление большими системами. Выпуск 94. М.: ИПУ РАН, 2021. С.5-32. DOI: https://doi.org/10.25728/ubs.2021.94.1

Дата опубликования: 30.11.2021

Ключевые слова: креативная деятельность, проверка гипотез, теория расписаний, past-sequence-dependent scheduling problem, эффекты научения и износа

Аннотация: Сформулирована задача минимизации времени освоения предметной области в процессе креативной деятельности за счет выбора последовательности проверки независимых гипотез. В условиях наличия эффектов износа и научения, с учетом зависимости времен проверки от предыстории, получены достаточные условия, при которых оптимальным является монотонное расписание «от простого – к сложному» (упорядочение гипотез по убыванию априорной вероятности проверки в единицу времени).

Author(s): Novikov D.

Article title: Optimal schedule to test independent hypotheses

Issue: 94

Year: 2021

Keywords: schedule theory; past-sequence-dependent scheduling problem; time-dependent processing times; learning and deterioration effects; creative activity; hypotheses testing

Abstract: The first stage of any creative activity consists in generating a set of hypotheses and testing them. Generally, the time, required for testing a hypothesis is random and depends on its complexity (the prior probability of testing per unit time) and on acquired experience, determined by the set of hypotheses, successfully tested before. The problem is to choose an optimal schedule of testing, i.e. minimizing the sum of expected testing times, which are essentially nonlinear past-sequence-dependent and take into account learning and deterioration effects. For this aim, the general model of creative activity is formulated and the corresponding problem of optimal scheduling is stated; the classification of subproblems is introduced. Analysis of related works demonstrates the absence of methods to find computationally “simple” solution of the problem in hand. The used method of analytical proof of certain monotonic schedule optimality consists in reordering of two adjacent hypothesis, violating monotonicity. Main result is a set (for different subproblems) of sufficient conditions, under which the monotonic “simple-to-complex” schedule is optimal: the hypotheses are arranged in ascending order of their complexity.