Cтраница 2
Он также состоит из треугольников. Такая схема генетического поиска применяется для решения комбинаторных оптимизационных задач, связанных с расположением ребер графа на плоскости. [16]
Предположим, что рассматривается некоторое множество исходных моделей и исследуется определенная оптимизационная задача, процесс решения которой понимается как оптимальная аппроксимация исходной задачи из некоторого базового класса. Тогда можно сказать, что на множестве исходных задач задана модель решения поставленной оптимизационной задачи, если указан некий принцип или правило, согласно которому произвольной матрице или графу ставится в соответствие некоторое подмножество альтернатив. Определение принципа выбора оптимальных альтернатив приводит к переборной задаче, формализуемой в виде комбинаторной оптимизационной задачи на графах. [17]
Задачи решают приближенно либо из-за невозможности получить точное решение с конечной сложностью, либо исходя из соображений повышения эффективности вычислительных затрат. К первому классу относится большинство задач математики, науки и техники ( много примеров читатель найдет в гл. Наиболее известными исключениями являются комбинаторные и некоторые алгебраические задачи. Примерами задач из этого второго класса могут служить задача решения больших линейных систем с разреженными матрицами и ряд трудных ( например, NP-полных) комбинаторных оптимизационных задач. На самом деле наша модель охватывает алгебраическую сложность как частный случай ( см. по этому поводу примеры 3.2, 3.3 и § 4 гл. [18]