Ранние ссылки для дискретной оптимизации

9

(Извинения, если это неуместно или слишком широко. Я открыт для предложений о том, как это переформулировать.)

Я заинтересован в отслеживании "древней" истории алгоритмов максимального потока и алгоритмов дискретной оптимизации в целом. Форд-Фулкерсон мой соломенный стартовый пункт. Каковы были значительные успехи до этого? Как далеко мы можем зайти, оставаясь при этом разумным аргументом, что кто-то работал над max-flow? Как насчет графовых алгоритмов? Как насчет дискретной оптимизации в целом?

Я также был бы счастлив получить ссылки на места, где это обсуждается.

ds.algorithms graph-algorithms ho.history-overview dan_x
источник

Ответы:

14

Обычно Шрайвер предоставляет хороший источник истории. Вы можете посмотреть на следующие книги и статью.

  • Александр Шрайвер. Комбинаторная оптимизация: многогранники и эффективность. Springer 2003.
  • Александр Шрайвер. Теория линейного и целочисленного программирования. Wiley 1998.
  • Александр Шрайвер. Об истории транспортировки и проблемах максимального потока. Математическое программирование 91 (3), 2002, 437-445. http://dx.doi.org/10.1007/s101070100259
  • Александр Шрайвер. К истории комбинаторной оптимизации (до 1960 г.). Справочник по дискретной оптимизации, Elsevier, 2005. http://homepages.cwi.nl/~lex/files/histco.pdf
Ёсио Окамото
источник
1
+1 для Шрайвера. Я добавил четвертый рекомендованный источник, который указывает на ранние работы Фробениуса [1912] и Кенига [1915] о двустороннем сопоставлении, Борувки [1926] о минимальных остовных деревьях, Менгера [1927] о его так называемой «nи снова [1930] о проблеме коммивояжера и Толстого [1930] о проблеме транспортировки.
Джефф
@ Jɛ ff E: Большое спасибо за добавление.
Ёсио Окамото
Спасибо. Последнее, из истории комбинаторной оптимизации, это именно то, что я искал.
dan_x
7

Большинство людей цитируют статью Эйлера 1741 года "Мосты Кенигсберга" как самый старый алгоритм графа. К сожалению, Эйлер на самом деле не описывает свой алгоритм подробно, а лишь приводит нерешительный пример:

«Когда будет определено, что такое путешествие может быть совершено, нужно еще найти способ его организации. Для этого я использую следующее правило: пусть мысленно удаляются те пары мостов, которые ведут из одной области в другую, тем самым значительно сокращая количество мостов; тогда легко построить необходимый маршрут через оставшиеся мосты. и мосты, которые были удалены, не изменят существенно найденный маршрут, как станет ясно после небольшого размышления. Поэтому я не думаю, что стоит приводить какие-либо дополнительные подробности, касающиеся определения маршрутов. »

Первое полное доказательство того, что все даже связные графы имеют эйлеровы туры, очевидно, принадлежит Хейрхольцеру более века спустя.

  • Леонард Эйлер. Решение проблем с геометрией situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8: 128–140, 1741. Представлено в Санкт-Петербургской академии 26 августа 1735 г. Перепечатано в Опере «Омния» 1 (7): 1–10.

  • Карл Хирхольцер. Über die Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. Mathematische Annalen 6: 30–32, 1873.

Jeffε
источник