Referências iniciais para otimização discreta

9

(Desculpas se isso for extraviado ou muito amplo. Estou aberto a sugestões sobre como reformulá-lo.)

Estou interessado em rastrear a história "antiga" dos algoritmos de fluxo máximo e algoritmos de otimização discretos em geral. Ford-Fulkerson é meu homem de palha de um ponto de partida. Quais foram os avanços significativos antes disso? Até que ponto podemos voltar enquanto ainda somos capazes de argumentar razoavelmente que alguém estava trabalhando no fluxo máximo? E os algoritmos de grafos? Que tal otimização discreta em geral?

Eu também ficaria feliz em obter referências a lugares onde isso é discutido.

ds.algorithms graph-algorithms ho.history-overview dan_x
fonte

Respostas:

14

Normalmente, Schrijver fornece uma boa fonte para a história. Você pode ver os seguintes livros e um artigo.

  • Alexander Schrijver. Otimização Combinatória: Poliedros e Eficiência. Springer 2003.
  • Alexander Schrijver. Teoria da Programação Linear e Inteira. Wiley 1998.
  • Alexander Schrijver. Sobre a história dos problemas de transporte e vazão máxima. Mathematics Programming 91 (3), 2002, 437-445. http://dx.doi.org/10.1007/s101070100259
  • Alexander Schrijver. Sobre a história da otimização combinatória (até 1960). Manual de Otimização Discreta, Elsevier, 2005. http://homepages.cwi.nl/~lex/files/histco.pdf
Yoshio Okamoto
fonte
11
n
@ Jɛ ff E: Muito obrigado pela adição.
Yoshio Okamoto
Obrigado. O último, sobre o histórico de otimização combinatória, é exatamente o que eu estava procurando.
dan_x 12/12
7

A maioria das pessoas cita o artigo de Bridges of Königsburg, de 1741, como o algoritmo gráfico mais antigo. Infelizmente, Euler na verdade não descreve seu algoritmo em detalhes, mas apenas fornece um exemplo tímido:

“Quando se determina que essa jornada pode ser feita, ainda é preciso descobrir como ela deve ser organizada. Para isso, uso a seguinte regra: deixe que os pares de pontes que levam de uma área para outra sejam mentalmente removidos, reduzindo consideravelmente o número de pontes; é uma tarefa fácil construir a rota necessária pelas pontes restantes. e as pontes removidas não alterarão significativamente a rota encontrada, como ficará claro depois de um pouco de reflexão. Portanto, não creio que valha a pena dar mais detalhes sobre a localização das rotas. "

A primeira prova completa de que todos os gráficos conectados têm visitas eulerianas é aparentemente devida a Heirholzer mais de um século depois.

  • Leonhard Euler. Solução de problemas ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8: 128–140, 1741. Apresentado à Academia de São Petersburgo em 26 de agosto de 1735. Reproduzido em Opera Omnia 1 (7): 1–10.

  • Carl Hierholzer. Sobre o Möglichkeit, um dos Linienzug Ohne Wiederholung e outro Unterbrechnung zu umfahren. Mathematische Annalen 6: 30–32, 1873.

Jeffε
fonte