Wczesne referencje do dyskretnej optymalizacji

9

(Przepraszamy, jeśli jest to źle umieszczone lub zbyt szerokie. Jestem otwarty na sugestie, jak to przeformułować).

Interesuje mnie prześledzenie „starożytnej” historii algorytmów maksymalnego przepływu i ogólnie dyskretnych algorytmów optymalizacji. Ford-Fulkerson jest moim słomkowym punktem wyjścia. Jakie były wcześniej znaczące postępy? Jak daleko możemy się cofnąć, wciąż będąc w stanie uzasadnić, że ktoś pracował nad maksymalnym przepływem? A co z algorytmami graficznymi? Co powiesz na ogólną optymalizację dyskretną?

Z przyjemnością otrzymam również odniesienia do miejsc, w których jest to omawiane.

ds.algorithms graph-algorithms ho.history-overview dan_x
źródło

Odpowiedzi:

14

Zazwyczaj Schrijver stanowi dobre źródło historii. Możesz spojrzeć na następujące książki i artykuł.

  • Alexander Schrijver. Optymalizacja kombinatoryczna: wielościany i wydajność. Springer 2003.
  • Alexander Schrijver. Teoria programowania liniowego i liczb całkowitych. Wiley 1998.
  • Alexander Schrijver. Na temat historii transportu i problemów z maksymalnym przepływem. Programowanie matematyczne 91 (3), 2002, 437–445. http://dx.doi.org/10.1007/s101070100259
  • Alexander Schrijver. O historii optymalizacji kombinatorycznej (do 1960 r.). Handbook of Discrete Optimization, Elsevier, 2005. http://homepages.cwi.nl/~lex/files/histco.pdf
Yoshio Okamoto
źródło
1
+1 dla Schrijver. Dodałem czwarte zalecane źródło, które wskazuje na wczesne prace Frobeniusa [1912] i Kőniga [1915] na temat dwustronnego dopasowywania, Boruvka [1926] na temat minimalnego drzewa rozpinającego, Menger [1927] na jego tak zwanym „n-arc tw”i ponownie [1930] na problem traveing sprzedawca i Tolstoi [1930] na problem transportu.
Jeffε
@ Jɛ ff E: Dziękuję bardzo za dodanie.
Yoshio Okamoto,
Dziękuję Ci. Ten ostatni, dotyczący historii optymalizacji kombinatorycznej, właśnie tego szukałem.
dan_x,
7

Większość ludzi podaje najstarszy algorytm graficzny Eulera z 1741 r. „Mosty z Królewca”. Niestety Euler tak naprawdę nie opisuje szczegółowo swojego algorytmu, ale podaje tylko pół-serce przykład:

„Gdy zostanie ustalone, że taka podróż może się odbyć, wciąż trzeba znaleźć sposób jej zorganizowania. W tym celu stosuję następującą zasadę: pozwól, aby te pary mostów, które prowadzą z jednego obszaru do drugiego, zostały mentalnie usunięte, tym samym znacznie zmniejszając liczbę mostów; wówczas łatwo jest zbudować wymaganą trasę przez pozostałe mosty. a mosty, które zostały usunięte, nie zmienią znacząco znalezionej trasy, co stanie się jasne po chwili namysłu. Nie uważam zatem, aby warto było podawać dalsze szczegóły dotyczące wyszukiwania tras. ”

Pierwszy kompletny dowód na to, że wszystkie połączone wykresy mają trasy Eulera, najwyraźniej wynika z faktu, że Heirholzer przeszło sto lat później.

  • Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8: 128–140, 1741. Przedstawiony Akademii Akademii w Petersburgu 26 sierpnia 1735 r. Przedruk w Operze Omnia 1 (7): 1–10.

  • Carl Hierholzer. Über die Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. Mathematische Annalen 6: 30–32, 1873.

Jeffε
źródło