Обсуждение:Задача Штейнера о минимальном дереве

Задача vs. Проблема

Господа, я не очень понял, зачем было переименовывать проблему Штейнера в задачу Штейнера. Проблема Штейнера является устоявшимся оборотом, обозначающим как раз то, что обсуждается в данной статье. Возможно, вы что-то имели ввиду. Жду ваших разъяснений. Alexeytuzhilin 19:41, 7 июля 2010 (UTC)Alexeytuzhilin

"Задача" чаще употребляется. Вот например согласно Google Books: "Проблема Штейнера" - 13 хитов, "Задача Штейнера" - 63 хита. -- X7q 19:52, 7 июля 2010 (UTC)

Минимальное(?) дерево Штейнера

Хорошо, давайте увеличивать рейтинг задачи Штейнера, это не особенно существенно. Но вот решения проблемы Штейнера всегда назывались МИНИМИЛЬНЫМИ деревьями Штейнера (в английском варианте - Steiner Minimal Trees, а также принято сокращение SMT). Так что, пожалуйста, верните исконное название! Alexeytuzhilin 20:03, 7 июля 2010 (UTC)Alexeytuzhilin

• Не согласен. Чаще (в том числе на английском) оно просто называется деревом Штейнера (Steiner tree - см. например, MathWorld или англовики). И вообще, уточнение минимальное нужно только, если существуют какие-то неминимальные деревья, чего в данном случае не наблюдается. Maxal 20:19, 7 июля 2010 (UTC)
• Статистика гугла: "дерево Штейнера" - 267 хита, "минимальное дерево Штейнера" - 65 хитов (то есть, уточнение минимальное используется лишь где-то в четверти случаев). Maxal 20:26, 7 июля 2010 (UTC)

Позвольте привести классиков, занимавшихся этой проблемой E. N. Gilbert and H. O. Pollak Steiner Minimal Trees http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJMAP000016000001000001000001&idtype=cvips&gifs=yes&ref=no (это - их знаменитый обзор, породивший огромную литературу по проблеме Штейнера).

D. Z. Du, F. K. Hwang, G. D. Song and G. Y. Ting Steiner minimal trees on sets of four points http://www.springerlink.com/content/y4x53g7w26487114/ (взято в качестве примера; посмотрите другие работы Du и Hwang - везде увидите Steiner Minimal Trees).

Prof. Dr. Dietmar Cieslik - Homepage http://stubber.math-inf.uni-greifswald.de/biomathematik/cieslik/ перейдите, например, в The Steiner Ratio - a report. (pdf, 85 p.) (там прямо в оглавлении увидите Steiner Minimal Trees). Дитмар Цислик - наш друг - крупнейший специалист в мире по проблеме Штейнера (в особенности, по отношению Штейнера).

Все эти ребята - классики проблемы Штейнера. Они являются безусловными хранителями терминологии теории, посвященной минимальным сетям (ну про меня и Иванова А.О. я не говорю).

Кстати, сайт http://en.wikipedia.org/wiki/Steiner_tree_problem мне, мягко говоря, не особенно нравится, хотя я вставил туда ссылки на наши с Ивановым работы. Например, там содержится явное вранье (пока еще руки не дошли его исправить): отношение Штейнера для плоскости до сих пор не вычислено (я об этом собираюсь писать в русской страничке, а затем и в английской). И утверждение The Steiner Ratio Conjecture of Gilbert-Pollak May Still Be Open http://www.springerlink.com/content/xgk728231g1r8273/ на самом деле было сделано нами с Ивановым за 5 лет до данной статьи (как раз после наших широких обсуждений вылезла в свет эта проблема; только мы об этом не писали, так как занимались попыткой залатать дыры).

А что касается просто деревьев Штейнера, так они обычно используются для обозначения возможной топологии минимального дерева, т.е. просто структуры самих графов, без учета того, где расположены вершины в их минимальных реализациях, т.е. в самих минимальных деревьях Штейнера. Alexeytuzhilin 21:10, 7 июля 2010 (UTC)

• Добавление своих статей — это ВП:Конфликт интересов. Я бы рекомендовал откатить это добавление. Насчет прилагательного "минимальное" — я не буду возражать, если вы определите сначала понятие просто "дерева Штейнера", а потом уже "минимального дерева Штейнера". Maxal 21:56, 7 июля 2010 (UTC)

Насчет дерева Штейнера

Как не парадоксально, но понятие ДЕРЕВА ШТЕЙНЕРА возникает ПОЗЖЕ понятия МИНИМАЛЬНОГО ДЕРЕВА ШТЕЙНЕРА. Это связано с тем, что про дерево Штейнера часто говорят как про топологию минимального дерева Штейнера, или про его тип, или про его структуру. Таким образом, если дать СНАЧАЛА определение дерева Штейнера, то получится примерно так: определим дерево Штейнера, которое, как вы узнаете где-то там внизу, возникает естественно в знаменитой классической проблеме. Честно говоря, мне кажется это неестественным, однако, если очень нужно, я, конечно же, могу дать определение дерева Штейнера перед минимальным деревом Штейнера.

Кстати, в интернете путаница с терминологией (замена минимального дерева Штейнера на дерево Штейнера) возникла, судя по всему, из-за многочисленных публикаций на обсуждаемую тему (и более многочисленных их цитирований), выполненных очень талантливыми разносторонними людьми, которые, однако, занимались данной проблемой не особенно долго (обсуждение понятия СПЕЦИАЛИСТ см. ниже). Так что к рассуждениям про «хиты» как про критерий истины стоит относиться достаточно осторожно.

Alexeytuzhilin 04:50, 8 июля 2010 (UTC)

Насчет интересов

Там, где автор или редактор текста должен оставить в стороне цели Википедии (создании энциклопедии с нейтральным и проверяемым содержанием) для того, чтобы поддержать сторонний интерес, имеет место конфликт интересов.

В обсуждаемом нами случае 1) я добавил ссылки не на СТАТЬИ, и на МОНОГРАФИИ, цитируемые специалистами по проблеме Штейнера; 2) страничка Steiner tree problem обсуждает задачу, которой я и мой соавтор А.О.Иванов занимаемся 20 лет; на эту тему мы написали 5 книг и более 50 статей; 3) страничка Steiner tree problem ОЧЕНЬ НЕПОЛНО отражает известные результаты специалистов в этой задаче (не только моих, но и других, скажем цитированных мной выше); 4) кстати, чтобы понять, кто является СПЕЦИАЛИСТОМ, можно посмотреть на списки публикаций того или иного претендента на специалиста, посвященных данной проблеме (например http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/h/Hwang:Frank_K=.html для Frank Hwang); замечу, что практически ничего из результатов этого автора, да и многого другого (см. например обзор Cieslik http://www.springer.com/computer/theoretical+computer+science/book/978-0-7923-7015-4) на странице Steiner tree problem не представлено;

Таким образом, если основной целью Википедии является энциклопедическая публикация, отражающая современное состояние накопленного человечеством знания, то добавленная мной ссылка на наши с Ивановым монографии, цитируемые разными известными авторами, на страничку, посвященную проблеме, которой мы занимаемся 20 лет и которой посвящены добавленные наши публикации, явно служит прежде всего упомянутой цели, а не противоречащим ей сторонним интересам (кстати, наши интересы как раз и состоят в распространении проверенных фактов). Более того, из вышесказанного вытекает необходимость серьезной доработки странички Steiner tree problem, которой я и собирался заняться.

Alexeytuzhilin 04:50, 8 июля 2010 (UTC)

Дорогие Помощники!

Большое спасибо всем, кто заинтересован в развитии этой странички и кто способствует ее улучшению! Особая благодарность первым энтузиастам X7q и Maxal!

Чтобы наша совместная работа была конструктивной, приведу некоторые задачи, которые я пока-что не смог решить, но их решение привело бы к существенному совершенствованию этой странички.

(1) Общее пожелание - для каждой ссылки найти реальное упоминание и кратко его процитировать. Мне удалось найти в интернете текст Fermat P. de (1643), Ed. H.Tannery, ed., "Oeuvres", vol. 1, Paris 1891, Supplement: Paris 1922, и в нем, на странице 153, точную формулировку (на латинском) «задачи Штейнера для трех точек». Конечно, ссылка была найдена в одной из статей, однако обнаружить в интернете "Oeuvres" было непростым делом. Кроме того, изначально я знал ссылку без указания страницы, и пытался, просматривая весь текст "Oeuvres", выловить оттуда постановку задачи. К сожалению, эта задача не проиллюстрирована рисунком. Наконец я нашел в одной из статей в интернете ссылку с указанием страницы, и тогда мне удалось локализовать нужный фрагмент. После я процитировал этот фрагмент, и даже сам перевел его (с помощью Лингво) с латинского, стараясь быть как можно ближе к тексту (латинский я никогда специально не изучал). Замечу, что цитаты на английском языке мне были известны, но хотелось иметь оригинал. Как видно, работа по установлению точности ссылок достаточно сложна. Я уверен, что многие из Вас, намного лучше меня владеющие возможностями интернета (скажем, поисковых систем) смогли бы сделать аналогичную работу эффективней (на установление упомянутой выше ссылки у меня ушло полдня). В рамках этой общей задачи возникают конкретные ее подзадачи.

(1.1) Я нашел ссылку на письма Торричелли, но не на G. Loria, G. Vassura (1919), Opere de Evangelista Torriceli, vol. 1, и в этих письмах мне не удается локализовать приведенное решение задачи Ферма.

(1.2) С Кавалери, Симпсоном и Хайненом я пока-что не разбирался.

(1.3) У Хайнена я не нашел биографической ссылки.

(1.4) Кто-то помог мне с Бертраном, однако тот ли это Бертран? Было бы хорошо найти точную ссылку на соответствующую его работу (в духе того, как было описано в пункте (1)) и добавить ее на страничку.

(1.5) Большое спасибо за pdf-ссылку на Ярника и Кесслера! С биографиями у них также туго (у Ярника - лучше, однако не в русской Википедии; у Кесслеоа я ее совсем не нашел).

(1.6) Конечно же, про Куранта и Роббинса известно в интернете много, но у меня пока-что руки не дошли.

(2) В исторической справке наверняка отсутствуют еще многие фигуры (возникшие до Ярника и Кесслера). Например, Гаусс в его переписке с Шумахером (задача Штейнера для 4-х точек - Гамбург, Бремен, Ганновер, Брауншвайг). Возможно, отсутствует Вивиани (на некоторых сайтах его упоминают как одного из участников решения задачи Ферма, хотя, насколько я знаю, у него есть другая знаменитая задача - про сумму расстояний от точки внутри правильного треугольника до его сторон; и вроде бы этим пользовался Торричелли в своем решении; в общем, нужно разбираться).

(3) Конечно же, хотелось бы дать ссылки на тех авторов, у которых по крупицам был собран исторический обзор.

Alexeytuzhilin 03:43, 9 июля 2010 (UTC)

Почему Штейнер?

Почему Штейнер? Согласно правилам немецкого языка Steiner читается как Штайнер. Jumpow 09:22, 26 января 2014 (UTC)Jumpow

Посмотрите конец статьи Немецко-русская практическая транскрипция. Так было принято до 1974 года. Поэтому же и Эйнштейн, а не Айнштайн. Sergey539 11:16, 26 января 2014 (UTC)

Разделить

В современной версии статьи смешиваются две разные задачи в геометрии и теории графов. По-моему, их лучше разделить. ⰕⰑⰞⰀ·Ⱁⰱⱄ 18:46, 26 августа 2023 (UTC)