Алгоритм - ускоренный поиск
Cтраница 2
Интересно отметить, что уже на этом шаге сказывается преимущество алгоритма ускоренного поиска. Если каждой точке ставить в соответствие не ф, а стоимость достижения, то в первой строке списка ( 2) оказываются три точки, имеющие минимальную стоимость достижения. При использовании же алгоритма ускоренного поиска наиболее перспективной оказывается только одна точка ( 4 3), движение к которой приближает нас к точке В и, как оказывается в этом частном примере, выделяет дугу оптимального пути. [16]
Конечно, рассмотренный пример является чисто иллюстративным и столь решительное преимущество алгоритма ускоренного поиска в нем обусловлено во многом тем, что перспективная оценка RXi у в условиях этого примера совпадает с фактической стоимость. [17]
Отыскиваем на сетке первый по оптимальности путь от А до В по алгоритму ускоренного поиска без учета расстановки НС. [18]
Нетрудно заметить, что предложенный способ преобразования расчетной сети не меняет главного содержания алгоритма ускоренного поиска, который построен на введении перспективной оценки достижения конечной точки В. Однако он позволяет сначала выполнить все операции по учету перспективной оценки на сети, что делает последующий поиск оптимальной трассы на ЭВМ технологически более последовательным. [19]
 |
Схема к количественному сопоставлению основного алгоритма и алгоритма ускоренного поиска. [20] |
Обозначим через П и Пу множества путей, подлежащих продолжению при основном алгоритме и алгоритме ускоренного поиска соответственно, через М и Му - множества концевых точек этих: путей. [21]
Методы отыскания оптимальной трассы трубопровода с отводами с учетом расстановки насосных станций основываются на использовании алгоритма ускоренного поиска оптимального пути Ли. В них в качестве критериев оптимальности рассматриваются приведенные затраты КС Э ( здесь К - объем капитальных вложений; С - нормативный коэффициент эффективности капитальных вложений; Э - ежегодные эксплуатационные расходы); протяженность трубопровода; трудовые затраты; сроки строительства; обеспечение максимума надежности трубопровода. [22]
Поиск оптимальной трассы среди всех трасс в случае, когда показатель качества представляет собой монотонную функцию пути, можно вести при помощи алгоритма ускоренного поиска, осуществляя одновременно движение т путей, характеризующихся при каждом шаге 2т координатами. [23]
Интересно опять сопоставить содержание списков ( 1) и ( 2) в случае основного алгоритма ( см. § 1) и алгоритма ускоренного поиска. [24]
Если критерий оптимальности является аддитивным или представляет собой монотонную функцию пути, для отыскания кратных по оптимальности трасс может быть использован как основной алгоритм Ли, так и алгоритм ускоренного поиска. [25]
Учет расстановки насосных станций одновременно с выбором оптимальной трассы значительно усложняет задачу поиска, поскольку стоимость любого допустимого пути на сетке существенным образом зависит от того, как этот путь будет продолжен до конечной точки трассы. Поэтому использовать алгоритм ускоренного поиска, который предполагает, что при каждой очередной надстройке стоимость получившегося пути не зависит от решений, принимаемых на последующих шагах, становится затруднительно. В связи с этим возникла необходимость в разработке соответствующих методов поиска трассы с учетом расстановки насосных станций. Одним из них является метод кратных по оптимальности трасс. [26]
Это предъявляет высокие требования к памяти ЭВМ и поэтому при поиске трассы с отводами еще более, нежели для трассы между двумя точками, желательно уметь находить оценку снизу стоимости достройки 2то - мерного пути, с тем чтобы основной алгоритм заменить алгоритмом ускоренного поиска. [27]
Интересно отметить, что уже на этом шаге сказывается преимущество алгоритма ускоренного поиска. Если каждой точке ставить в соответствие не ф, а стоимость достижения, то в первой строке списка ( 2) оказываются три точки, имеющие минимальную стоимость достижения. При использовании же алгоритма ускоренного поиска наиболее перспективной оказывается только одна точка ( 4 3), движение к которой приближает нас к точке В и, как оказывается в этом частном примере, выделяет дугу оптимального пути. [28]
Страницы: 1 2