Jump to content

Мэйгу Гуань

Мэйгу Гуань
китайский Канумейя
Транскрипции
Standard Mandarin
Hanyu PinyinGuǎn Méigǔ
Wade–GilesKuan Mei-ku
Yale RomanizationGwan Mei-gu
IPA[kwàn měɪ.kù]

Мэйгу Гуан ( китайский : 管梅谷 , также романизированный как Мэй-Ко Кван или Мэй-ку Куан , родился в 1934 году в Шанхае ) — китайский математик и один из ведущих специалистов страны по математическому программированию . [1] Он известен своими исследованиями проблемы проверки маршрутов и был президентом Шаньдунского педагогического университета .

Вклад в исследования

[ редактировать ]
Пример задачи проверки маршрута Гуана (черные ребра и веса) и ее оптимальное решение (удвоение красных ребер для получения эйлерова мультиграфа )

Гуань известен тем, что сформулировал задачу проверки маршрута . [1] Эта задача является обобщением задачи Эйлера об обходе , в которой входными данными является граф, взвешенный по ребрам , и цель состоит в том, чтобы найти замкнутый обход минимального общего веса, который посещает каждое ребро графа хотя бы один раз. Его приложения включают в себя задачи транспортного планирования, такие как планирование маршрутов для парка снегоочистителей, которые будут расчищать все улицы города за минимальное общее время. [2]

Гуань работал преподавателем в Шаньдунском педагогическом университете во время « Большого скачка» 1958–1960 годов, во время которого китайских математиков поощряли работать над практическими задачами. Он опубликовал свою работу по проблеме проверки маршрутов в 1960 году, а его статья была переведена на английский язык в 1962 году. [1] Она привлекла внимание Джека Эдмондса , который дал проблеме альтернативное название — «проблема китайского почтальона» в честь Гуаня. [3] и доказал, что эту задачу можно решить оптимально за полиномиальное время . [1]

Одним из более поздних достижений Гуана было доказательство того, что, напротив, задача о ветреном почтальоне NP -полна ; это обобщенная версия задачи проверки маршрута, в которой стоимость прохождения ребра зависит от направления, в котором оно пересекается. [4]

Академическая карьера

[ редактировать ]

Гуань закончил учебу в 1957 году в Восточно-Китайском педагогическом университете в Шанхае и в том же году поступил на факультет Шаньдунского педагогического университета. [5] Он занимал должность президента Шаньдунского педагогического университета с 1984 по 1990 год. Затем он стал директором департамента исследования операций Фуданьского университета с 1990 по 1995 год, после чего перешёл в бизнес-школу Королевского Мельбурнского технологического института в Австралии . [1]

Избранные публикации

[ редактировать ]
  • Кван, Мей-ко (1960), «Графическое программирование с использованием нечетных или четных точек», Acta Mathematica Sinica (на китайском языке), 10 : 263–266, MR   0162630. Переведено на китайский язык Mathematics 1 , Американское математическое общество, 1962, стр. 273–277.
  • Гуань, Мэйгу, Чжэн, Хэндинг (1983), ( на Линейное программирование китайском языке), Shandong Science and Technology Press .
  • Гуань, Мейгу (1984), «О проблеме ветреного почтальона», Discrete Applied Mathematics , 9 (1): 41–46, doi : 10.1016/0166-218X(84)90089-1 , MR   0754427 .
  • Гуань, Мэйгу (1989), «Теория графов в Китае», Теория графов и ее приложения: Восток и Запад (Цзинань, 1986) , Анналы Нью-Йоркской академии наук, том. 576, Нью-Йорк: Нью-Йоркская академия наук, стр. 203–218, doi : 10.1111/j.1749-6632.1989.tb16400.x , MR   1110817 , S2CID   86165306 .
  1. ^ Jump up to: а б с д и Гретшель, Мартин ; Юань, Я-сян (2012), «Эйлер, Мэй-Ко Кван, Кенигсберг и китайский почтальон» (PDF) , Истории оптимизации: 21-й Международный симпозиум по математическому программированию, Берлин, 19–24 августа 2012 г., Documenta Mathematica , Экстра: 43–50, МР   2991468 .
  2. ^ Ву, Маркус (23 февраля 2015 г.), «Математика, лежащая в основе уборки всего этого проклятого снега с вашей улицы» , Wired .
  3. ^ Гретшель и Юань (2012) . Некоторые источники благодарны Алану Дж. Голдману за то, что он предложил это имя Эдмондсу; см., например Питерс, Вреда; Блэк, Пол Э., ред. (2 сентября 2014 г.), «Проблема китайского почтальона» , Словарь алгоритмов и структур данных , Национальный институт стандартов и технологий , получено 26 апреля 2016 г.
  4. ^ Гуань (1984) .
  5. ^ Гретшель, Мартин (2006), «Лекция 03M2: Производство печатных плат: некоторые проблемы», Пекинский блочный курс «Комбинаторная оптимизация в работе» (PDF) , Институт вычислительной математики и научных/инженерных вычислений Китайской академии наук .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 8f66efadc62403d3e80586723ef872d5__1693395360
URL1:https://arc.ask3.ru/arc/aa/8f/d5/8f66efadc62403d3e80586723ef872d5.html
Заголовок, (Title) документа по адресу, URL1:
Meigu Guan - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)