Max Home IndustryДа — запах. Диофантовы уравнения — это просто полиномиальные уравнения, в которых в качестве коэффициентов и решений используются только целые числа. Их очень сложно решить, и зачастую они очень важны.
Мы знаем, что не существует общего решения — это было доказано Матиясевичем в 1970 году, который также показал, что не существует решения десятой проблемы Гильберта.
Например, найдите целые числа a, b и c, которые удовлетворяют:
а2 + Ь2 — с2 = 0
В этом случае a, b и c — это просто пифагоровы тройки, такие как 3, 4, 5, то есть стороны прямоугольного треугольника. Столь же хорошо известен тот факт, что то же уравнение, но со степенью больше двух, не имеет решений, потому что это последняя теорема Ферма, доказанная Уайлсом в 1994 году.
Поскольку пространство решений состоит из дискретного набора целых чисел, кажется довольно очевидным попробовать некоторые методы поиска ИИ для решения общего уравнения, и люди пробовали такие вещи, как генетический алгоритм, который представляет потенциальные решения в виде генов и порождает новые решения, выбирая разведение. пары по фитнесу.
Теперь у нас есть другой подход от команды из Университета Мумбаи — алгоритм оптимизации муравьиной колонии. Это работает, позволяя «муравью» исследовать пространство решения и оставлять за собой след феромона, по которому другие могут следовать. Идея состоит в том, что феромон откладывается в зависимости от местоположения муравья, а также испаряется, что позволяет исследовать новые области пространства.
Что отличает поиск диофантова решения, так это то, что у вас вполне может быть набор целых чисел, которые близки к решению, но соседние целочисленные решения превышают или недооценивают и поэтому не обеспечивают решения. То, что некоторые, казалось бы, хорошие места в пространстве поиска на самом деле очень плохие.
В этом случае муравьи выпускаются в пространство поиска в случайных начальных точках на размерной сетке m, где m — количество неизвестных. Качество местоположения определяется тем, насколько близко оно подходит к решению уравнения. Это используется для того, чтобы дать муравью количество феромона, которое он случайным образом распределяет между соседними локациями. Со временем концентрация феромона уменьшается по закону, имитирующему испарение. Конечно, муравьи движутся к концентрации феромона.
Что удивительно в этой процедуре, так это то, что она не только работает, но и, кажется, работает лучше, чем генетический алгоритм — иногда намного.
Так что же такого особенного в поиске целочисленных решений, благодаря которому оптимизация колоний муравьев работает? Возможно, это простой факт, что рядом с решением есть много очень хороших приближенных решений — подумайте об изменении одной из m переменных в решении на 1. Это делает задачу более подходящей для такого рода дискретного метода «восхождения на холм».
Какой бы ни была причина, я сомневаюсь, что многие математики подумают, что «обоняние» решения в этом смысле имеет много красоты или элегантности.