1 Московскии государственныи университет информационных технологии, радиотехники и электроники (МИРЭА), г. Москва, Россия 2 Московскии политехническии университет (МПУ), г. Москва, Россия 3 Институт проблем управления РАН им. В.А. Трапезникова, г. Москва, Россия 4 ФКН НИУ Высшая школа экономики, г. Москва, Россия

Abstract

На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности.

-

взрослого человека из i аэропорта в j аэропорт (данные получены на саите kayak.com). В случае отсутствия прямого реиса в качестве стоимости перелета использовалась минимальная цена перелета с пересадками, наиденная на том же саите.

В качестве элементов матрицы стоимостеи индивидуальнои TSP использовались нормально распределенные случаиные величины X ij  N (aij , ij ) , параметр  ij  Kaij , где K  0.1, K  0.5 , а также равномерно распределенные на отрезке [0.5aij ,1.5aij ] случаиные величины (с округлением до целых чисел), что порождает индивидуальные задачи трех типов.

Для каждого типа задач коммивояжера объем выборки (число экспериментов) для получения статистически значимых результатов был выбран равным 105 . Полученные при проведении вычислительных экспериментов значения сложности индивидуальных задач были использованы для подбора вероятностного распределения, удовлетворительно описывающего распределение величины m — десятичного логарифма сложности. Расчеты показали, что в качестве приближения для вероятностного распределения m можно использовать нормальное распределение.

Для предварительного анализа данных для выборки каждого из трех типов были вычислены выборочные коэффициенты асимметрии и эксцесса [ 4,11,13 ], как для всеи выборки объема 105 , так и для ее первои и второи половины и для каждои четверти. На рис. 1 в системе координат коэффициент асимметрии-коэффициент эксцесса черным ромбом изображается точка, соответствующая выборочным коэффициентам асимметрии и эксцесса для выборки объема 105 , синии и голубои кружок соответствуют первои и второи половине выборки, треугольники – четвертям выборки. Нормальные случаиные величины имеют равные нулю коэффициенты асимметрии и эксцесса, что изображает фиолетовыи ромб в начале координат. Для большеи наглядности на рис. 1 также изображены точки, соответствующие выборкам из нормального распределения, полученным генератором псевдослучаиных чисел (желтые точки для выборок 5 4 объема 10 , голубые – 2.5 10 ). где Ei  pi /8  F 1(i / 8) , i  1,2,...,7 октили непрерывнои функции распределения F (x) [ 8-10 ]. формулам, вместо Ei используются выборочные квантили.

Квантильные коэффициенты асимметрии и эксцесса выборок логарифма сложности примерно такие же, какие наблюдаются у выборок того же объема из стандартного нормального распределения (рис. 2), обозначения такие же, как на рис. 1. распределением попадает с вероятностью 1 n . Для сравнения изобразим на гистограмме плотность стандартного нормального распределения (см. рис. 3, красная линия).

Как видно, гистограмма удовлетворительно аппроксимирует плотность стандартного нормального распределения в случае каждои из трех выборок. нормального распределения, q - квантиль выборки, элементы которои равны сложности решения индивидуальнои задачи коммивояжера с элементами платежнои N (aij , ij  0.1aij ) , уровень квантилеи принимает значения из (0,1). матрицы вида Рис. 4. Q-Q plot (график квантилей) Как видно из рис. 4, самые большие и самые маленькие значения в выборке наблюдаются несколько чаще, чем это характерно для нормального распределения, в целом же нормальное распределение можно считать удовлетворительным приближением. Уточнение параметров распределения выборки

Определив, что нормальное распределение достаточно хорошо описывает распределение логарифма сложности индивидуальных задач коммивояжера при их решении классическим алгоритмом методом ветвеи и границ (при фиксированнои длине входа), подберем параметры распределения, согласующиеся с выборкои.

Грубую оценку параметров можно провести по методу моментов, точечные оценки и доверительные интервалы приведены в табл. 2.

Более робастные оценки можно получить с использованием квантилеи, в качестве оценки параметра a используем выборочную медиану. Параметр  оценим, используя линеиное преобразование выборки L : Lx  kx  b , при котором интерквантильныи размах E6  E2 преобразованнои выборки равен интерквантильному размаху стандартного нормального * распределения. Учитывая, что при линеином преобразовании новые выборочные квантили Ei (1) В качестве оценки параметра  используем k , значения, вычисленные для каждои из трех выборок также приведены в табл. 2.

*

Ei  kEi  b , k  E6*  E*

2 E6  E2

. Доверит. Выборочн интервал . медиана a (2.847, 2.850) (2.636, 2.640) (2.904, 2.908)

выборка Как видно из табл. 2, значения параметров, вычисленные по методу моментов и с помощью квантилеи, очень близки. Табл. 2 Оценки параметров нормального распределения

 Выборочное среднеквадр

атическое отклонение

Примерно 99.7% выборки (достаточно большого объема) из нормального распределения попадает в интервал a3,a3, 99.99% попадает в интервал a4,a4 , далее будем называть эти интервалы соответственно 3 и 4 . Границы интервалов 3 и 4 , минимальное и максимальное значения в выборке, а также доля выборки, попавшеи в эти интервалы, приведены в табл. 3. Для удобства приведены сами значения сложности, а не их десятичные логарифмы. Интервал 90% обозначает интервал между 5% и 95% квантилями, так что примерно 5% выборки попадает левее этого интервала и 5% правее.

Табл. 3. Границы выборки и интервалов 90%, 3 и 4 равномерн. [0.5aij ,1.5aij ]

Будем рассматривать «слишком большие» и «слишком маленькие» значения, не попавшие в интервал 3 и 4 , как исключения из правила, погрешность эксперимента и т.п. Исключим такие значения из выборки и по полученнои новои выборке вычислим медиану, среднее и среднеквадратическое отклонение, а также отношение интерквантильных размахов выборки и стандартного нормального распределения, коэффициенты асимметрии и эксцесса, в том числе квантильные. Результаты расчетов приведены в табл. 4 и 5.

Табл. 4 Характеристики усеченной выборки (медиана, среднее, среднеквадратическое отклонение) выборка  a  2.630 2.898 2.638 2.906 асимметрии и эксцесса практически одинаковы у исходнои и усеченнои выборок.

Таким образом, удовлетворительным приближением для вероятностного распределения логарифма сложности индивидуальных задач коммивояжера классическим алгоритмом метода ветвеи и границ можно считать нормальное распределение с параметрами a и  , равными соответственно выборочнои медиане и отношению интерквантильных размахов (1) или коэффициентам b0 и k0 линеинои регрессии стандартного нормального распределения на выборку (см. табл. 1). Заключение

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

Поскольку тип аппроксимирующего распределения логарифма сложности оказался одинаковым в случае нормально и равномерно распределенных элементов платежнои матрицы, возможно, класс распределении элементов платежнои матрицы, приводящии к нормальному распределению логарифма сложности, содержит еще какие-то типы распределении. Работа выполнена при поддержке гранта РФФИ №16-07-160.

Литература

References Жукова Московского университета (МПУ), Фомичев Михаил Игоревич, студент магистратуры ФКН НИУ Высшая школа экономики, [e-mail].

References

1. Dantzig G. B. , Fulkerson R. , Johnson S. Solution of a large scale traveling salesman problem . Technical Report P-510. RAND Corporation , Santa Monica, California, USA. - 1954 .

2. Dantzig , G. B. , Fulkerson D. R. , Johnson S. M. « On a linearprogramming, combinatorial approach to the traveling-salesman problem » // Operations Research 1959. №7, pp. 58 - 66 .

3. Eastman , W. L. Linear Programming with Pattern Constraints . Ph.D. Thesis . Department of Economics, Harvard University, Cambridge, Massachusetts, USA. - 1958 .

4. Jonhnson N.L. , Kotz S. , and Balakrishnan N. Continuous Univariate Distributions . Vol. 2 , Wiley, 1995 .

5. Knuth , D. E. « Estimating the efficiency of backtracking programs » // Mathematics of Computing, 1975 . Vol. 29 , pp. 121 - 136 .

6. Land , A. H. , Doig A. G. « An automatic method of solving discrete programming problems » // Econometrica 1960. №28, pp. 497 - 520 .

7. Little , J. D. C. , Murty K. G. , Sweeney D.W. , Karel C. « An algorithm for the traveling salesman problem » // Operations Research, 1963 . №11, pp. 972 - 989 .

8. Moors J. J. A. A quantile alternative for kurtosis// The Statistician, 1988 . Vol. 37 , pp. 25 - 32 .

9. Moors J. J. A. , Coenen V. M. J. , Heuts R. M. J. « Limiting distributions of moment- and quantile-based measures for skewness and kurtosis» . School of Economics and Management , Tilburg University, Res. Mem. FEW 620 , 1993 .

10. Moors J. J. A. , Wagemakers R. Th . A., Coenen V. M. J. , Heuts R. M. J. , Janssens M. J. B. T. « Characterizing systems of distributions by quantile measures » // Statistica Neerlandica, 1996 . Vol. 50 , № 3, pp. 417 - 430 .

11. Pearson , K. «Contributions to the Mathematical Theory of Evolution . III. Regression, Heredity and Panmixia» // Philosophical Transactions of the Royal Society of London, 1896 . 187 , pp. 253 - 318 .

12. Головешкин В.А. , Жукова Г .Н., Ульянов М .В., Фомичев М .И. « Сравнение ресурсных характеристик традиционного и модифицированного метода ветвей и границ для TSP» // Современные информационные технологии и ИТ- образование , 2015 . Т. 2 , № 11. С. 151 - 159 .

1. Dantzig G. B. , Fulkerson R. , Johnson S. Solution of a large scale traveling salesman problem . Technical Report P-510. RAND Corporation , Santa Monica, California, USA. - 1954 .

2. Dantzig , G. B. , Fulkerson D. R. , Johnson S. M. « On a linearprogramming, combinatorial approach to the traveling-salesman problem » // Operations Research 1959. №7, pp. 58 - 66 .

3. Eastman , W. L. Linear Programming with Pattern Constraints . Ph.D. Thesis . Department of Economics, Harvard University, Cambridge, Massachusetts, USA. - 1958 .

4. Jonhnson N.L. , Kotz S. , and Balakrishnan N. Continuous Univariate Distributions . Vol. 2 , Wiley, 1995 .

5. Knuth , D. E. « Estimating the efficiency of backtracking programs » // Mathematics of Computing, 1975 . Vol. 29 , pp. 121 - 136 .

6. Land , A. H. , Doig A. G. « An automatic method of solving discrete programming problems » // Econometrica 1960. №28, pp. 497 - 520 .

7. Little , J. D. C. , K. G. Murty , D.W. Sweeney , C. Karel «An algorithm for the traveling salesman problem » // Operations Research, 1963 . №11, pp. 972 - 989 .

8. Moors J. J. A. A quantile alternative for kurtosis// The Statistician, 1988 . Vol. 37 , pp. 25 - 32 .

9. Moors J. J. A. , Coenen V. M. J. , Heuts R. M. J. « Limiting distributions of moment- and quantile-based measures for skewness and kurtosis» . School of Economics and Management , Tilburg University, Res. Mem. FEW 620 , 1993 .

10. Moors J. J. A. , Wagemakers R. Th . A., Coenen V. M. J. , Heuts R. M. J. , Janssens M. J. B. T. « Characterizing systems of distributions by quantile measures » // Statistica Neerlandica, 1996 . Vol. 50 , № 3, pp. 417 - 430 .

11. Pearson , K. «Contributions to the Mathematical Theory of Evolution . III. Regression, Heredity and Panmixia» // Philosophical Transactions of the Royal Society of London, 1896 . 187 , pp. 253 - 318 .

12. Goloveshkin V.A. , Zhukova G.N. , Ul'yanov M .V., Fomichev M.I. « Sravnenie resursnykh kharakteristik traditsionnogo i modifitsirovannogo metoda vetvey i granits dlya TSP» // Sovremennye informatsionnye tekhnologii i IT-obrazovanie , T. 2 , № 11 , 2015 , S. 151 - 159 .

13. Kramer G . Matematicheskie metody statistiki . M.: Mir , 1975 . - 648 s.

14. Ul'janov M .V., Fomichev M.I. « Resursnye harakteristiki sposobov organizacii dereva reshenij v metode vetvej i granic dlja zadachi kommivojazhera » // Biznes - informatika, 2015 . № 4 ( 34 ). S. 38 - 46

15. Ul'janov M .V. Resursno-jeffektivnye komp'juternye algoritmy . Razrabotka i analiz. - M.: FIZMATLIT , 2008 . - 304 s.