Řešič Concorde TSP - Concorde TSP Solver - Wikipedia

The Řešič Concorde TSP je program pro řešení problém obchodního cestujícího. Napsal to David Applegate, Robert E. Bixby, Vašek Chvátal, a William J. Cook, v ANSI C. a je volně k dispozici pro akademické použití.

Concorde byl aplikován na problémy genové mapování,[1] predikce funkce proteinu,[2] směrování vozidel,[3] převod bitmapových obrázků na spojité perokresby,[4] plánování pohybu lodí pro seismické průzkumy,[5] a při studiu škálovacích vlastností kombinačních optimalizačních problémů.[6]

Podle Mulder & Wunsch (2003) „Concorde„ je obecně považován za nejrychlejšího řešení TSP, pro velké instance, které v současné době existuje. “ V roce 2001 Concorde vyhrál 5000 gulden cena od CMG pro řešení problému směrování vozidel, který společnost představovala v roce 1996.[7]

Poznámky

  1. ^ Hitte a kol. (2003).
  2. ^ Johnson & Liu (2006).
  3. ^ Applegate a kol. (2002).
  4. ^ Bosch & Herman (2004).
  5. ^ Gutin a kol. (2005)
  6. ^ Aldous & Percus (2003).
  7. ^ Směrování vozidel Whizzkids '96, z webu Concorde, vyvoláno 26. srpna 2008.

Reference

  • Aldous, David; Percus, Allon G. (2003), „Škálování a univerzálnost v kombinatorické optimalizaci spojité délky“, Proc. Natl. Acad. Sci. USA, 100 (20): 11211–11215, arXiv:cond-mat / 0301035, Bibcode:2003PNAS..10011211A, doi:10.1073 / pnas.1635191100, PMC  208736, PMID  14504403.
  • Applegate, David; Cook, William; Dash, Sanjeeb; Rohe, André (2002), „Řešení problému směrování vozidla min-max“, INFORMS Journal o práci na počítači, 14 (2): 132–143, doi:10.1287 / ijoc.14.2.132.118.
  • Bosch, Robert; Herman, Adrianne (2004), „Kontinuální perokresby prostřednictvím problému obchodního cestujícího“ (PDF), Dopisy o operačním výzkumu, 32 (4): 302–303, doi:10.1016 / j.orl.2003.10.001.
  • Gutin, Gregory; Jakubowicz, Helmut; Ronen, Shuki; Zverovitch, Alexei (2005), „Seismický problém s nádobou“ (PDF), Komunikace v DQM, 8: 13–20.
  • Hitte, C .; Lorentzen, T. D .; Guyon, R .; Kim, L .; Cadieu, E .; Parker, H. G .; Quignon, P .; Lowe, J. K .; et al. (2003), „Srovnání MultiMap a TSP / CONCORDE pro konstrukci radiačních hybridních map“, Journal of Heredity, 94 (1): 9–13, doi:10.1093 / jhered / esg012, PMID  12692156.
  • Johnson, Olin; Liu, Jing (2006), „Přístup obchodního cestujícího pro predikci proteinových funkcí“, Zdrojový kód pro biologii a medicínu, 1: 3, doi:10.1186/1751-0473-1-3, PMC  1636333, PMID  17147783.
  • Mulder, Samuel A .; Wunsch, Donald C., II (2003), „Řešení problému cestujícího obchodního cestujícího milionem měst rozdělením a dobýváním shluků pomocí adaptivních rezonančních neuronových sítí“, Neuronové sítě, 16 (5–6): 827–832, doi:10.1016 / S0893-6080 (03) 00130-8, PMID  12850040.

externí odkazy