Ist das "Problem des Handlungsreisenden" noch ein Problem?

[A. S. (rava)]

Klar, das TSP ist NP-hart. Brute-Force-Methoden versagen bei Problemen, 
die ein paar Duzend Knoten haben. Aber, ganz provokativ gefragt: 
bereitet das in der Praxis noch jemandem Kopfzerbrechen?

Wir haben ganz brauchbare Heuristiken, die - je nach Aufgabe - ganz gute 
Lösungen liefern, zum Teil in der Logistik oder bei der Pfadplanung für 
Roboter.

Gibt es Beispiele für praktische Probleme, für die die Expertenwelt 
sagt "ja also da wäre es schon toll, genauere Approximationen zu haben"? 
Gibt es also Probleme, die z.B. selbst für die Heuristiken zu groß oder 
zu exotisch sind?

Keine Frage: Das globale Optimum für große Probleme zu finden, wird 
schwierig. Aber verbessert noch irgendwer die bekannten Approximationen?

[Cyblord -. (cyblord)]

"SAT Solving" und Co. sind durchaus Gegenstand aktueller Forschung. Da 
gibt es immer was zu verbessern.

[Ben B. (Firma: Funkenflug Industries) (stromkraft)]

> Ist das "Problem des Handlungsreisenden" noch ein Problem?
Ja.

[Frank M. (ukw) (Moderator)]

Ben B. schrieb:
> Ist das "Problem des Handlungsreisenden" noch ein Problem?
>
> Ja.

Nein, die benutzen doch mittlerweile MS-Teams!

SCNR ;-)

[A. S. (rava)]

Cyblord -. schrieb:
> "SAT Solving" und Co. sind durchaus Gegenstand aktueller
> Forschung. Da
> gibt es immer was zu verbessern.

sorry, ich sprach von TSP Probleminstanzen. Werde mal versuchen, das in 
meiner ursprünglichen Frage klarer zu machen.

edit: edit geht nicht mehr -.-

[Cyblord -. (cyblord)]

A. S. schrieb:
> Cyblord -. schrieb:
>> "SAT Solving" und Co. sind durchaus Gegenstand aktueller
>> Forschung. Da
>> gibt es immer was zu verbessern.
>
> sorry, ich sprach von TSP Probleminstanzen. Werde mal versuchen, das in
> meiner ursprünglichen Frage klarer zu machen.

Ich weiß. Aber sowohl TSP als auch SAT sind eben NP harte Probleme und 
für SAT weiß ich aus eigener Erfahrung dass dort recht intensiv 
geforscht wird.
Dann würde ich vermuten für TSP ist es wohl nicht anders.

[Hans H. (loetkolben)]

Dank der von unseren Politikern bald verhängten Bewegungseinschränkung 
von 15km um den Wohnort ist das kein praktisches Problem mehr.
SCNR

[Richard H. (richard_h27)]

Hans H. schrieb:
> Dank der von unseren Politikern bald verhängten Bewegungseinschränkung
> von 15km um den Wohnort ist das kein praktisches Problem mehr.

Die Handlungsreisenden machen jetzt alle Homeoffice.

[Purzel H. (hacky)]

> Ist das "Problem des Handlungsreisenden" noch ein Problem?

Bei uns hat der Handelsreisende eine goldene Kreditkarte. die loest das 
Problem fuer uns.

[Ben B. (Firma: Funkenflug Industries) (stromkraft)]

> Bei uns hat der Handelsreisende eine goldene Kreditkarte.
> die loest das Problem fuer uns.
Soso, und wer löst dann hinterher das Problem mit
der Entsorgung des Handelsreisenden?