Geum.ru

Б. Ф. Мельников (Тольяттинский государственный университет, B. Melnikov@tltsu ru, bormel@mail ru) Аннотация Внастоящей статье рассматриваются эвристические методы принятия решений в различных задача

Вид материалаЗадача
Подобный материал:
1   2   3   4   5   6   7

Литература

  1. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции, т.1. – М., Мир, 1978.
  2. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ вычислительных алгоритмов. – М., Мир, 1979.
  3. Н.Вирт. Алгоритмы и структуры данных. – М., Мир, 1989.
  4. С.Гудман, С.Хидетниеми. Введение в разработку и анализ алгоритмов. – М., Мир, 1981.
  5. А.Лозовой, Б.Мельников, А.Радионов. Применение генетических алгоритмов и специальных несогласованных ν-фильтров для минимизации корреляционных шумов БФМ сигналов. – В кн.: Тезисы докладов 3 международной научной конференции и выставки «Цифровая обработка сигналов и её применение», М., Инсвязьиздат, 2000.
  6. М.Макаров и др. Теория выбора и принятия решений. – М., Наука, 1982.
  7. Б.Мельников. Эвристики в программировании недетерминированных игр. – «Програмирование» (Известия РАН), 2001, №5, с.63–80.
  8. Б.Мельников, А.Мосеев. Недетерминированные игры и экономика. – В кн.: Сборник материалов 2 международной научно-технической конференции «Математические методы и компьютеры в экономике», Пенза, изд-во ПТИ, 1999.
  9. Б.Мельников, А.Мосеев. Функции риска в краткосрочном прогнозе. – В кн.: Труды 4 научной конференции «Математическое моделирование…», секция математики, Ульяновск, изд-во УлГУ, 2001.
  10. Б.Мельников, А.Пушкин. Варианты системы поддержки принятия торговых решений на рынке FOREX. – В кн.: Сборник материалов 2 международной научно-практической конференции «Развивающиеся интеллектуальные системы…», Новочеркасск, изд-во ЮРГТУ, 2001.
  11. Б.Мельников, А.Радионов. О выборе стратегии в недетерминированных антагонистических играх. – «Програмирование» (Известия РАН), 1998, №5, с.55–62.
  12. Б.Мельников, А.Радионов. Эвристические алгоритмы в специальных задачах дискретной оптимизации. – В кн.: Тезисы докладов международной научной конференции «Дискретный анализ и исследование операций», Новосибирск, изд-во Института математики, 2000.
  13. Б.Мельников, Н.Романов. Ещё раз об эвристиках для задачи коммивояжёра. – В кн.: Теоретические проблемы информатики и ее приложений, вып.4, Саратов, изд-во СГУ, 2001, с.81–92.
  14. Ф.Новиков. Дискретная математика для программистов. – СПб, изд-во «Питер», 2002.
  15. А.Саломаа. Жемчужины теории формальных языков. – М., Мир, 1986.
  16. И.Сигал, А.Иванова. Введение в прикладное дискретное программирование. – М., Физматлит, 2002.
  17. С.Яблонский. Введение в дискретную математику. – М., Наука, 1986.
  18. D.Applegate, R.Bixby, V.Chvátal, W.Cook, Finding cuts in the TSP (A preliminary report), DIMACS Technical Report 95-05, March.
  19. M.Bellmore, G.Nemhauser, The Traveling Salesman Problem: A Survey, Operation Reasearch, Vo.16 (1968) p.p.538–558.
  20. M.Dorigo, L.Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. – IEEE Transactions on Evolutionary Computation, Vo.1, No.1 (1997) 53–66.
  21. T.Jiang, B.Ravikumar. Minimal NFA Problems are Hard. – SIAM J. Comput., Vo.22 (1993).
  22. D.Johnson, L.McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization, in “Local Search in Combinatorial Optimization”, eds E.Aarts, J.Lenstra. – John Wiley Ed., 1997, p.p.215–310.
  23. T.Kameda, P.Weiner. On the State Minimization of Nondeterministic Finite Automata. – IEEE Trans.on Computers, C-19 (1970) 617–627.
  24. Ch.Hageman, A.Musholl. Computing ε-free NFA from Regular Expression in O(n·log2(n)) Time. – Theoret. Inform. Appl. (1999).
  25. K.Hashiguchi. Algorithms for Determining Relative Star Height and Star Height. – Inform. Comput. No.78 (1987) 124–169.
  26. K.Hashiguchi. Algorithms for Determining the Smallest Number of Nonterminals (States) Sufficient for Generating (Accepting) a Regular Language. – ICALP, 1991.
  27. M.Jünger, S.Thienel, G. Reinelt, Provably good solutions for the traveling salesman problem. – Zeitschrift für Operations Research, Vo.40 (1994) 183-217.
  28. B.Melnikov. A new algorithm of the state-minimization for the nondeterministic finite automata. – The Korean Journal of Computational and Applied Mathematics, Vo.6, No.2 (1999) 277–290.
  29. B.Melnikov. Once more about the state-minimization of the nondeterministic finite automata. – The Korean Journal of Computational and Applied Mathematics, Vo.7, No.3 (2000) 655–662.
  30. B.Melnikov, E.Kashlakova. Some grammatical structures of programming languages as simple bracketed languages. – Informatica (Lithuanian Acad. Sci.), Vo.11, No.4 (2000) 441–454.
  31. B.Melnikov, A.Melnikova. Edge-minimization of non-deterministic finite automata. – The Korean Journal of Computational and Applied Mathematics, Vo.8, No.3 (2001) 469–479.
  32. B.Melnikov, A.Melnikova. Some properties of the basis finite automaton. – The Korean Journal of Computational and Applied Mathematics, Vo.9, No.1 (2002) 131–150.
  33. B.Melnikov, N.Sciarini-Guryanova. Possible edges of a finite automaton defining a given regular language. – The Korean Journal of Computational and Applied Mathematics, Vo.9, No.2 (2002) 475–485.

1 Данная статья написана при частичной поддержке гранта РФФИ № 04-01-00863.

2 Аналогичного краткого русского термина, к сожалению, не существует. Название «алгоритмы реального времени» недостаточное (оно не полностью отражает суть), а «постепенно приближающие псевдо-оптимальные алгоритмы реального времени» весьма громоздко.

3 Важно отметить, что с точки зрения теории сложности алгоритмов, ни одна из реализаций МВГ не даёт преимуществ по сравнению с методами, использующими лишь полный перебор.

4 Автор вместо 1-деревьев использует для метрической ЗКВ процесс построения последовательности левых задач, имеющий аналогию с процессом построения последовательности правых задач, изложенным ниже. Однако более подробное описание этого вспомогательного алгоритма не является предметом данной статьи.

5 См., однако, это решение в ещё не опубликованной статье (сданной в печать): n.ru/konkurssite/texts/new-sh-j.pdf.

6 Где, среди прочего, приведено краткое описание других эвристических подходов к решению данной задачи. Стоит отметить, что предлагаемые ранее подходы не могут быть отнесены к «обычным» методам дискретной оптимизации.

7 Примерно 20 (переменных) в задаче минимизации ДНФ, 30 (состояний эквивалентного канонического автомата) в задаче вершинной минимизации конечного автомата, 70 (городов) в случайной ЗКВ, 100 (точек) в задаче построения БФМ-сигнала.

8 Это условие является весьма существенным – алгоритмов, которые бы не использовали данных построений, в литературе не описано; вероятно, таких алгоритмов не существует. Как было отмечено выше, все имеющиеся алгоритмы (описанные, например, в вышеуказанных работах) такие построения используют.

9 Такое дополнительное условие – безотносительно того факта, является ли задача метрической – называется условием симметричности. Также и ЗКВ при этом называется симметричной.

10 Важно отметить, что псевдометрическая ЗКВ симметричной, вообще говоря, не является.

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

12 Здесь уместна следующая аналогия с гораздо более простой задачей; эта аналогия почему-то не встречалась автору в каких-либо публикациях, хотя она очень проста и достаточно очевидна. Поставим вопрос: зачем нужен алгоритм QuickSort сортировки массива, в худшем работающий как алгоритм порядка n2? Ответ прост: потому нужен, что при его применении «нужно» считать сложность в среднем, а не в худшем. Что такое «в среднем» для сортируемых массивов – это, с некоторыми оговорками понятно, но что это понятие означает для ЗКВ и тому подобных ЗДО? Можно ответить, что все эвристические алгоритмы для решения этой задачи, по большому счёту, и предназначены для ответа на этот вопрос.

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

13 Здесь, в отличие от вопроса, поставленного в предыдущей сноске, сам автор проводил статистические подсчёты. Так, на «средних современных» компьютерах (с тактовой частотой около 2 ГГц и оперативной памятью 256 МБ) за реальное время (10 минут или менее) по классическому алгоритму МВГ считаются 100% случайных задач размерности 45 (контр-примеров, случайно сгенерированных компьютером, у автора нет), около 50% случайных задач размерности 60 и менее 1% случайных задач размерности 100. Как было отмечено выше, метрические задачи для решения сложнее – например, при тех же самых ограничениях удаётся решить только около 50% задач размерности 25 и около 10% задач размерности 30.

14 Простейшая из них – организация свопинга. Конечно же, желательно, чтобы его организовал сам автор программы, а не операционная система.

Необходимость применения свопинга можно объяснить, например, следующим несложным подсчётом. Существует процедура генерации старта процесса для решения метрической ЗКВ. (Отметим, что аналогично рассмотренному далее процессу построения последовательности правых задач, эту процедуру можно было бы назвать построением последовательности левых задач – так и было сделано в одной из предыдущих сносок.) И при размерности 130 (это число является размерностью одного из стандартных тестов для метрической ЗКВ, т.н. Churritz-test) получается более 8000 «левых» подзадач для последующего решения. Причём впоследствии, при работе МВГ, это значение увеличивается – см. об этом далее. А если одно значение матрицы коммивояжёра занимает 4 б, то, как несложно посчитать, вся матрица размерности 130 занимает более 66 Кб, т.е. оперативная память объёмом 256 Мб сможет вместить менее 4000 подзадач необходимой размерности.

Конечно же, приведённый подсчёт является приблизительным (поскольку многие подзадачи имеют меньшую размерность), но суть отражает верно.

15 Это псевдо-оптимальное решение было выбрано с помощью действий, описанных в предыдущем пункте.

Стоит ещё отметить, что в этом вопросе не всё так очевидно. Иногда процесс построения ППЗ может быть прерван ранее – для получения оптимального решения некоторой промежуточной задачи, например, методом перебора (при небольшой размерности задачи) или каким-либо иным методом. Этот вопрос связан с материалом раздела 6 (о вспомогательных эвристиках), а также с одной из задач для дальнейшего решения, формулируемой в заключении.

16 Этот очевидный факт в большинстве публикаций особо не отмечен – и два разных алгоритма, т.е. МВГ и алгоритм выбора «разделяющего» элемента, часто неправильно воспринимаются как единое целое.

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

17 Кроме того, изредка использовались и эвристики (и нестандартные алгоритмы) не для ветвления, а для построения границ – однако мы не будем рассматривать этот вопрос.

18 Как уже однажды было сделано выше, приведём некоторую упрощающую аналогию с иной областью математики – вспомним одну классическую задачу теории вероятностей. Двое часов показывают разное время – но у первых значительно больше точность (т.е. значительно меньше дисперсия). Как определить математическое ожидание текущего времени?

Стоит подчеркнуть, что наша задача несколько сложнее – поскольку в задаче о нахождении математического ожидания текущего времени нет никакой информации о нашем предпочтении – т.е. о том, чего именно мы хотим от истинного значения текущего времени.

19 Эта книга посвящена теории принятия решения и не связана напрямую с рассматриваемыми нами ЗДО. Однако все описанные в этой книге алгоритмы принятия решений (при наличии оценок нескольких экспертов-программ) легко связываются с рассматриваемым нами случаем.

20 Можно применить следующую аналогию с некоторыми видами спорта, в которых судьи выставляют оценки спортсменам ([13]). При этой аналогии рассматриваемый нами метод не имеет ничего общего с большинством из таких видов спорта (прыжки с трамплина, гимнастика и пр.) – где оценки судей суммируются. Наш метод похож на применяемый в фигурном катании – где конкретные оценки, с точки зрения математика, не играют никакой роли, а значение имеет лишь место, занимаемое каждым спортсменом с точки зрения каждого судьи. Однако в нашем случае «судьи имеют разные веса» – причём эти веса зависят не только от их «опыта» (хотя и этот фактор тоже имеет значение), но и, главное, от того, является ли спортсмен лидером соревнований или, наоборот, аутсайдером. А именно, для лидера мы больше прислушиваемся к судьям, которые его оценили плохо («выясняем, почему именно это произошло»), а для аутсайдера, наоборот, «пытаемся найти его небольшие плюсы» у судей, которые всё же хоть как-то смогли его оценить.

Важно отметить, что приведённая аналогия часто проявляется и в обычной сравнительной оценке человеком-экспертом некоторых событий. См. по этому поводу обоснования выбора конкретных функций риска в [7] и далее в настоящей работе.

21 Эту задачу также можно рассматривать как одну из ЗДО.

22 С точки зрения оценок эффективности алгоритмов очень важно отметить, что описанные алгоритмы использования специальных методов усреднения путём применения функций риска составляют очень малую часть от общего объёма вычислений. (В любой из рассматриваемых ЗДО – например, в ЗКВ с размерностью 50 и более – эта часть вычислений составляет значительно менее 1%.)

23 В отличие от [7]: там чаще рассматривался отрезок [-1,1]. Однако в подобных случаях мы всегда можем применить нормировку.

24 В добавление к вышесказанному отметим, что вычисления предельных значений также практически не отнимают времени: основное время работы компьютера при выполнении данного алгоритма тратится не на усреднение, а на экспертные вычисления оценок, а также на саму реализацию основного алгоритма – МВГ.

25 Исследовались как экспертные оценки, упомянутые в предыдущем разделе, так и некоторые другие. При этом случаи, когда размерность рассматриваемой матрицы составляла менее трети от размерности исходной (т.е. становилась 24 и менее), не рассматривались.

26 Специально отметим недетерминированность автомата – иначе задача тривиальна. Эта задача может быть решена стандартными алгоритмами – см. [1] и мн.др. Однако на практике часто нежелательно для каждого из рассматриваемых НКА строить эквивалентный канонический автомат – ведь построение последнего только для одного автомата, первоначально заданного, превращает любой алгоритм в экспоненциальный. Поэтому на практике желательно применять альтернативные алгоритмы, включающие самые разные эвристики. Появление в литературе целого цикла работ вроде [24] автор считает хорошим признаком, признаком того, что связанными вопросами занялись и «чистые математики», специалисты по вопросам теории сложности алгоритмов.

27 Как уже дважды было сделано выше, можно провести упрощающую аналогию. В данном случае – между двумя данными задачами и кажущимися на первый взгляд похожими задачами построения эйлеровых и гамильтоновых циклов. См. по этому поводу [14, стр.267].

28 Это делается, например, методом, близким к изложенному в [15], и практически не имеет отношения к статье [24] (цитировавшейся немного выше) и тому подобным работам. Соответствующая задача схожа с задачей звёздно-высотной минимизации (см. раздел 1), точнее – с построением для неё anytime-алгоритма.

29 См. [5]. Очень кратко эти модификации могут быть описаны следующим образом. Были расширены и дополнены традиционные генетические операторы кроссинговера и мутации: изменения были вызваны спецификой рассматриваемых задач. Например, оператор мутации был растянут на несколько поколений, т.е. аппарат мутации из однотактового превратился в многотактовый. Также было введено понятие оптимизирующей мутации.

Однако с момента публикации статьи [5] многие из этих понятий были опубликованы и во многих других работах, под другими наименованиями, у других авторов, часто – применительно к совершенно иным ЗДО, и поэтому просто не могут быть восприняты в настоящее время как нечто новое. Новым автор считает описываемый ниже принцип турнирного самообучения.

30 Мы не будем подробно рассматривать в этой статье сами алгоритмы модификации наборов-геномов.

31 Причём желательно наличие не только оптимального решения (конкретного тура ЗКВ и т.п.), но и информации о времени получения данного решения стандартным МВГ (или какой-либо его модификацией) на некотором компьютере известной конфигурации. При этом мы можем подробно проследить работу различных anytime-алгоритмов (или одного и того же алгоритма с разным набором коэффициентов), исследовав при этом характеристики алгоритмов, приведённые в разделе 4.

32 Важно, что не более, чем двух.

33 Точнее – из применения генетических алгоритмов в задачах самообучения для программирования интеллектуальных игр. Подробнее см. [7], а также другие работы, ссылки на которые имеются в указанной.

34 Т.е. сгенерированную по некоторым правилам. Про подходы к возможным «правилам генерации» конкретных ЗДО см. немного подробнее в разделах 2 и 4 – однако этот вопрос является отдельной, ещё до конца не исследованной темой.

35 См., например, .kpi.kharkov.ua/mahotilo, а также некоторые ссылки с указанного сайта. Автор настоящей статьи в этом случае (т.е. при решении генетическими алгоритмами системы линейных алгебраических уравнений) обычно применяет один шаг градиентного метода после нескольких «генетических» шагов; заметим, что шаг градиентного метода требует значительно больше времени. Число шагов генетическими методами зависит от размерности задачи; например, при размерности сильно разрежённой матрицы системы линейных алгебраических уравнений около 200 число шагов методами ГА примерно равно 10.

Однако данная тема, относящаяся к области ГА, не относится к дискретной оптимизации, и поэтому практически не связана с темой настоящей статьи. Вследствие этого мы не будем приводить здесь более подробную информацию.

36 Кроме уже неоднократно цитировавшейся статьи [7], посвящённой в первую очередь программированию бэкгеммона, имеется также её научно-популярное изложение в издании РФФИ; см. ru. См. также другую научно-популярную публикацию – в журнале “Game.EXE” (М., «Издательский дом Компьютерра»), №9 – 2003, terra.ru.

37 Экспертные оценки перспективности некоторого шага МВГ, данные несколькими разными программами-предикторами, аналогичны оценкам позиций в случае разных показаний кубиков в бэкгеммоне.

38 О желательности совместного самообучения этих параметров было сказано в [7]. Добавим к изложенному там, что такое самообучение, конечно же, удобно проводить раздельно для упомянутых здесь различных классов позиций.

39 О том, что оценка позиции в программировании игр имеет аналог для ЗДО, было сказано выше.

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

41 А согласно классическому описанию МВГ, мы обязаны в первую очередь рассматривать подзадачи с относительно меньшими значениями границ – независимо от их размерности.

42 Стоит отметить, что на практике ещё лучше работает вариант этого алгоритма, когда попеременно вызываются следующие варианты выбора очередной задачи:
  • согласно наименьшей границе,
  • согласно наименьшей размерности,
  • согласно описанной линейной функции двух этих характеристик.

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

При описанном здесь алгоритме попеременного выбора задач из списка по разным критериям возникает весьма интересная практическая задача – о наилучшей организации структур данных для такого выбора. (Такая задача возникает в связи с тем, что размерность указанного списка в реальных задачах весьма велика. Например, при размерности исходного варианта случайной ЗКВ около 75 или метрической ЗКВ около 35 длина этого списка часто превышает 500000 – даже при применении всевозможных «программистских хитростей», о которых уже шла речь выше.) Эта задача не связана с материалом данной статьи – и стоит отметить, что автор пока не имеет для неё красивого решения, поскольку реальное число критериев для попеременного выбора подзадач может быть и более 3.

43 Здесь мы считаем, что при необходимости была применена нормализация.

44 Наиболее подробно этот вопрос был исследован автором применительно к вышеописанной задаче «звёздно-высотной» минимизации НКА. В ней «единицы измерения» для большинства предикторов формулируются в разных единицах, каждая из которых связана со специальными показателями вложенности циклов графа переходов минимизируемого НКА

Стоит ещё отметить, что, конечно, априорное наличие информация об отрезке возможных оценок предикторов весьма желательно – оно позволяет упростить многие вспомогательные алгоритмы.

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

46 Заметим, что можно легко доказать, что данная задача сводится к известной задаче о рюкзаке. Автор применяет алгоритмы, не применяющие такого сведéния.

47 А здесь имеется аналогия с выпуклостью функций риска в реальных задачах – см. подробнее [7].

48 Имеются в виду следующие работы, выполненные под научным руководством автора настоящей статьи. Отметим, что названия работ отражают не только вопросы, подробно рассматривавшиеся в данной статье, но и некоторые близкие к ним задачи искусственного интеллекта и методы их решения.
  • А.Радионов. Моделирование и нестандартные алгоритмы выбора стратегий в недетерминированных антагонистических играх и родственных задачах. Диссертация … кандидата технических наук. Ульяновск, УлГУ, 1999.

А также следующие дипломные работы студентов Ульяновского государственного университета. (6 из нижеперечисленных 11 студентов-дипломников имеют и соответствующие публикации в сборниках трудов студентов и аспирантов УлГУ, однако конкретных ссылок приводить не будем.)
  • М.Бузин. Функции риска в игре “Sokoban” и связанные проблемы искусственного интеллекта. УлГУ, 1995.
  • Д.Медведков. Использование функций риска для псевдо-планарного размещения графа. УлГУ, 1995.
  • И.Боброва. Быстрый алгоритм канонизации недетерминированного конечного автомата. УлГУ, 1997.
  • Ю.Ревва. Использование принципов программирования недетерминированных игр при программировании шахмат. УлГУ, 1998.
  • Д.Верник. Сложность алгоритмов вершинной минимизации недетерминированных конечных автоматов Рабина-Скотта. УлГУ, 1999.
  • А.Мосеев. Некоторые эвристики, альтернативные функциям риска, в программировании недетерминированных игр. УлГУ, 1999.
  • В.Долгов. Специальное описание всех регулярных языков, чьи канонические автоматы содержат не более 3 состояний. УлГУ, 2000.
  • В.Марунин. Сложность алгоритмов дуговой минимизации недетерминированных конечных автоматов. УлГУ, 2000.
  • С.Козлов. Эвристические алгоритмы в задаче минимизации ДНФ. УлГУ, 2001.
  • В.Гумаюнов. Принцип «турнирного» самообучения для генетических алгоритмов. УлГУ, 2003.
  • Е.Скиценко. Эвристические методы построения псевдо-оптимальных регулярных выражений. УлГУ, 2003.

Автор настоящей статьи благодарит своих бывших студентов и аспирантов за сотрудничество и выражает надежду, что результаты хотя бы некоторых из упомянутых здесь работ всё же будут защищены в качестве кандидатских диссертаций.

49 Некоторые соответствующие программы можно скачать на сайте l.narod.ru, либо получить непосредственно у автора по электронной почте: bormel@mail.ru, B.Melnikov@tltsu.ru.

50 См. также некоторые другие работы, ссылки на которые приведёны в библиографии указанных статей.

51 Важно отметить, что эвристики для применения МВГ для распределённых вычислений, конечно же, не ограничиваются описанной здесь. Например, выше уже была упомянута эвристика про попеременный вызов одного из нескольких возможных вариантов выбора очередной задачи – а при распределённых вычислениях эта эвристика превращается в независимую работу нескольких процессов выбора новой задачи.

Добавим ещё к одной из предыдущих сносок, что в 2004 г. под руководством автора данной статьи готовятся защиты двух дипломных работ на эту тему – распределённые вычисления и МВГ.

52 По мнению автора, именно такие алгоритмы и стоит называть искусственным интеллектом в чистом виде!