Анализ эвристических алгоритмов в решении задач маршрутизации данных

Для выживания в условиях независимого рынка фирмы желают использовать весь запас общедоступных инструментов, позволяющих приобрести конкурентоспособное преимущество перед прочими компаниями. Одним из подобных инструментов представляется оптимизация накладных затрат, что разрешает при том же объеме используемых ресурсов повысить прибыль. Для транспортных компаний значительная оптимизация затрат может быть достигнута в том числе и за счет построения действенных маршрутов для транспортных средств. Именно по этой причине эффективным алгоритмам решения задачи маршрутизации транспорта (ЗМТ, VRP – vehicle routing problem) уделено столь пристальное внимание со стороны исследователей. Под задачами транспортной маршрутизации имеют в виду широкий класс популярных комбинаторных задач оптимизации. Главной целью в данных задачах представляется создание набора маршрутов для транспортных средств (ТС), что обслуживают множество географически распределенных потребителей с установленным спросом. ЗМТ является обобщением задачи известной как задача коммивояжера, и соответственно, так же как и задача коммивояжера, относится к классу NP-трудных задач. Таким образом, для решения задач большой размерности использование точных алгоритмов в разумное время затруднено. взамен них применяют разные метаэвристические и эвристические алгоритмы, умеющие быстро отыскать хорошие решения без гарантии оптимальности и, как правило, без оценки погрешности.

Эвристический алгоритм —это алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным, либо оптимальным, однако достаточный для решения назначенной задачи. Разрешает ускорить решение задачи в тех случаях, когда не может быть найдено точное решение. Эвристический алгоритм — это алгоритм решения задачи, безошибочность которого для всех вероятных случаев не доказана, однако про который известно, что он даёт довольно хорошее решение в большинстве случаев. В действительности может даже быть известно (то есть доказано), что формально эвристический алгоритм неверен. Но его всё равно возможно применять, если при этом он даёт неправильный итог исключительно в отдельных, довольно редких и отлично выделяемых случаях, либо же даёт неточный, однако всё-таки подходящий итог.

Проще говоря, эвристика — это пусть и не абсолютно математически обоснованный, однако при этом все же практически полезный алгоритм. Важно понимать, что в отличие от корректного алгоритма решениязадачи эвристика обладает нижеследующим особенностями: -Она не гарантирует установление наилучшего решения. -Она не гарантирует установление решения, даже если оно бесспорно существует. -Она сможет дать неправильное решение в определенных случаях. Эвристические алгоритмы широко применяются для решения задач, имеющих высокую вычислительную сложность, то есть взамен целого перебора вариантов, занимающего значительное время, а временами технически невозможного, используется существенно более быстрый, однако плохо обоснованный теоретически алгоритм. В областях искусственного интеллекта, таких как определение образов, эвристические алгоритмы широко применяются еще и по причине неимения общего решения назначенной задачи. всевозможные эвристические подходы используются в антивирусных программах, компьютерных играх и т. Например, играющие в шахматы программы, проводят середину игры, основываясь, в основном, на эвристических алгоритмах (в дебюте возможно применение базы данных, в эндшпиле — таблицы Налимова, но в миттельшпиле зачастую число вероятных ходов исключает полный перебор, а точных алгоритмов верной игры длительное время не существовало).