Hva er problemet med en handelsreisende?

Q: Hva er problemet med en handelsreisende?

A: The Traveling Salesman Problem (TSP) er et klassisk algoritmisk problem innen datavitenskap og operasjonsforskning. Det fokuserer på optimalisering, der bedre løsninger ofte betyr billigere, kortere eller raskere løsninger.

Q: Hvordan uttrykkes TSP?

A: TSP uttrykkes enklest som en graf som beskriver plasseringen av et sett med noder.

Spørsmål: Hvem definerte først TSP?

A: TSP ble definert på 1800-tallet av den irske matematikeren W. R. Hamilton og den britiske matematikeren Thomas Kirkman.

Q: Hvem studerte det videre på 1930-tallet?

A: I løpet av 1930-tallet studerte matematikerne Karl Menger i Wien og Harvard det videre.

Q: Hva introduserte Hassler Whitney like etter?

A: Hassler Whitney ved Princeton University introduserte navnet "traveling salesman problem" kort tid etter definisjonen.

Q: Hva betyr "bedre løsning" i denne sammenhengen?

A: I denne sammenhengen betyr bedre løsning ofte en løsning som er billigere, kortere eller raskere.

Q: Hvilken algoritme ble ansett som åpenbar av Menger da han studerte TSP?

A: Menger vurderte en åpenbar brute-force-algoritme da han studerte TSP og observerte at bruk av nærmeste nabo heuristikk ikke alltid gir optimale resultater.