Cтраница 4
Удалим из С2 любую дугу, вес которой не меньше с2, и так будем продолжать до тех пор, пока не получим орграф 6гт 1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фт в Ст ( с весом ст) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Ст 1 следует, что в Сг1 не существует никакого гамильтонова цикла, не использующего по крайней мере одну дугу с весом, большим или равным ст. Таким образом, алгоритм нахождения гамильтонова цикла в орграфе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном орграфе С может быть найден с помощью построения полного орграфа &1 с тем же самым множеством вершин, что и в С, дугам которого, соответствующим дугам из О, приписаны единичные веса, а остальным дугам - бесконечные веса. Если решение минимаксной задачи коммивояжера для Ог имеет конечный вес ( на самом деле равный единице), то в графе С может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе О не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот. [46]
При решении задачи полиномиальной чебышевской аппроксимации методом Ремеза на каждом шаге удерживалось ровно п 1 точек ( множества сг. Этого достаточно вследствие полного альтернанса в задаче аппроксимации. Общая минимаксная задача может и не обладать таким свойством, поэтому ниже приходится вводить дополнительные точки, гарантирующие сходимость. [47]
В монографии излагаются некоторые новые результаты по теории мигошакса и аппроксимации функций в основной в области численных методов ( в частности, методов выравнивания максимумов и экстремального базиса), приводится несколько схем с ускоренной сходимостью. Основное внимание уделяется разработке методов, более эффективных с точки зрения реализации на ЭВМ. Рассматривается целочисленная минимаксная задача. Приводятся программы ( на языке АЛГОЛ-бО) решения ряда задач, возникающих в теории нинимакса. Каждая программа ( процедура) сопровождается контрольным примером и некоторыми рекомендациями по практическому ее использованию. [48]