Аннотация:В работе Алексея Ефимова рассматривается задача построения деревьев Штейнера в случае манхэттенской метрики. Исследованы свойства деревьев Штейнера в данной метрике и проведено сравнение с соответствующими свойствами в евклидовой метрике. Проведен сравнительный анализ основных алгоритмов построения стягивающих деревьев, близких по сложности к деревьям Штейнера. На основе анализа примеров, для которых данные алгоритмы дают наиболее сильное отличие по сложности от деревьев Штейнера, предложено 2 алгоритма построения стягивающих деревьев, дающие на всех примерах, кроме примера, называемого «лепестком», более хорошие результаты, чем известные алгоритмы. Наиболее интересным представляется второй алгоритм, названный автором «трезубцем», который побеждает известные алгоритмы на всех примерах, где эти алгоритмы работают плохо. Приведены оценки сложности предложенных алгоритмов, но они довольно грубые и могут быть снижены при более тонком подсчете.