Мультиэвристический подход к задачам дискретной оптимизации1



Скачать 475.48 Kb.
страница4/9
Дата17.01.2013
Размер475.48 Kb.
ТипДокументы
1   2   3   4   5   6   7   8   9

4. Об одном подходе к оценкам эффективности эвристических алгоритмов


Автор убеждён, что при сравнении эффективности двух эвристических алгоритмов, решающих одну и ту же ЗДО, совершенно не уместны сложные математические теории, в частности, теория сложности алгоритмов. Поэтому в предыдущих публикациях автора (некоторые из них приведены ниже в списке литературы, остальные цитируются в этих работах) специально опущены вопросы сложности тех алгоритмов, которые явно приводятся в этих работах или могут быть легко описаны на основе доказываемых там утверждений. Применительно, например, к вышеупомянутым задачам минимизации НКА это делается в связи со следующими обстоятельствами. (Отметим заранее, что каждый из приведённых аргументов легко переносится на случай любой другой задачи дискретной оптимизации.)

  • Функции разметки состояний и их таблицы соответствия [28], а также специальные бинарные отношения [30,32] при практическом программировании строятся в этих алгоритмах одновременно, одни из них применяются для быстрого построения других – поэтому применение стандартных методов оценки сложности в данном случае весьма затруднительно.

  • Формулы, полученные стандартным образом, согласно стандартным методам оценки сложности алгоритмов ([2–4] и мн.др.) в случае таких сложных объектов, которыми являются НКА, обязательно «включают комбинаторный взрыв» – и, следовательно, вряд ли представляют интерес для задач практического программирования. (А ведь именно для подобных задач и разрабатываются методы оценки сложности алгоритмов.)

  • Более того, существует много задач, в которых стандартные методы оценки сложности алгоритмов дают результаты, фактически противоречащие получаемым на практике. Среди многочисленных известных автору подтверждающих примеров приведём два наиболее показательных. Во-первых, при построении эвристических алгоритмов проверки эквивалентности двух состояний некоторого заданного НКА26 могут решаться подзадачи определения, существует ли выходное слово, допускаемое обоими данными состояниями, и существует ли слово, допускаемое ровно одним из этих состояний. При практическом программировании вторая из этих подзадач значительно проще (этот факт кажется очевидным) – однако формальные оценки сложности соответствующих алгоритмов дают обратный результат.27 Во-вторых, при построении по заданному НКА эквивалентного регулярного выражения28 возникает подзадача оптимального упорядочения вершин рассматриваемого НКА, рассматривающая всевозможные циклы между этими вершинами. Согласно классическим методам оценки сложности алгоритмов, число этих циклов факториально зависит от числа вершин – отсюда можно получить, что и любой эвристический алгоритм решения данной задачи имеет не менее чем факториальную сложность. Однако такая же факториальная оценка сложности получается и при самом тривиальном, переборном методе решения задачи.
    Итак, при «одинаковых» оценках в реальных условиях, конечно, переборный алгоритм абсолютно неприемлем, а эвристический даёт неплохие практические результаты.

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

Кроме того, в каждой из ЗДО возникают вопросы, схожие с поставленным выше в одной из сносок раздела 2: что такое «в среднем» для некоторого алгоритма? к каким именно объектам в рассматриваемой ЗДО нужно применять два или более сравниваемых алгоритма? Применительно к задачам минимизации НКА эти вопросы можно переформулировать так: необходимо описать некоторую процедуру генерации автоматов и показать, что исследуя именно такие автоматы для нужных задач и применяя к ним именно эти эвристические алгоритмы, можно получить хорошие результаты в реальных прикладных задачах минимизации (например, в подзадачах теории трансляции). Для этого можно, например, описать некоторые «внутренние» свойства автоматов и показать, что «реальные» НКА, встречающиеся в конкретных прикладных задачах (при описании вспомогательных грамматических структур языков программирования, в LR-анализе и др.) «чаще всего» обладают именно этими свойствами. Однако в настоящей статье мы не будем рассматривать вопросы, поставленные в этом абзаце.

В заключение раздела стоит отметить, что автор не считает материал этого раздела чем-то новым (как и материал раздела 2, т.е. описание незавершённого МВГ). Просто, по мнению автора, в современных публикациях, посвящённых алгоритмам для решения ЗДО, неоправданно большое внимание уделяется оценкам сложности этих алгоритмов – в ущерб публикациям каких-либо статистических результатов их работы. Последние же, к сожалению, гораздо чаще удаётся находить не в научных публикациях, а на интернетовских страницах.

1   2   3   4   5   6   7   8   9

Похожие:

Мультиэвристический подход к задачам дискретной оптимизации1 iconСитуационный подход к задачам поиска текстовой информации
Здесь тоже присутствуют идеи такого рода: будет использоваться некий набор экстралингвистических отношений, и эти экстралингвистические...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЭлементы дискретной математики
П. А. Корнилов, Н. И. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие. Ярославль: Изд-во ягпу им. К. Д....
Мультиэвристический подход к задачам дискретной оптимизации1 iconУрок по геометрии в 7-м классе на тему "Некоторые свойства прямоугольных треугольников"
Раздаточный материал: карточки с тестом, листы с чертежами к задачам самостоятельной работы, листы для ответов к задачам самостоятельной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЛингвистические противоречия в терминологической системе дискретной математики
Именно таким путем язык может разрешить определяющее противоречие говорящего и слушающего, которое в терминологической системе дискретной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconСборник упражнений для студентов математического факультета пединститута
В сборник включены упражнения по дискретной математике. Основная цель упражнений – отработка основных понятий дискретной математики,...
Мультиэвристический подход к задачам дискретной оптимизации1 icon"Построение конечно-разностных формул на границе дискретной области счёта"
При численном решении уравнений математической физики важным становится вопрос замены непрерывной области изменения аргумента дискретной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconВ. П. Голубятников известный специалист в области геометрии, топологии и их приложений к задачам математического моделирования и к обратным задачам. Он опубликовал 160 научных работ, в том числе монографию Uniqueness q
«Uniqueness questions in reconstruction of multidimensional objects from tomography-type projection data», изданную в Голландии,...
Мультиэвристический подход к задачам дискретной оптимизации1 iconПрограмма курса Дополнительные главы дискретной математики для групп 318, 319 кафедры математической кибернетики
«Дополнительные главы дискретной математики» (для студентов 3-го курса 2-го потока). В нее включены разделы, относящиеся к конечнозначным...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЛичностно-ориентированный подход к обучению иностранному языку
Личностный подход к обучающимся при организации учебно– воспитательного процесса
Мультиэвристический подход к задачам дискретной оптимизации1 iconМеждународный опыт в области инклюзивного образования: Норвегия
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org