Krokodilos Δημοσ. 16 Δεκεμβρίου 2008 Δημοσ. 16 Δεκεμβρίου 2008 Ξερει κανείς που μπορω να βρω καμια πληρη αποδειξη για το οτι μια εκδοχη του προβληματος TSP(travelling salesman problem) στην οποια θελουμε να βρουμε λυση κατω απο μια συγκεκριμενη τιμη(αξιας/αποστασης κλπ), ειναι NP-Complete? Εψαξα στο GOOGLE αλλα δεν βρηκα πληρη αποδειξη. Αν δεν υπαρχει καμια ελευθερη δημοσιευση στο ιντερνετ(γινεται?) περι αυτου, ξερει κανείς να το αποδειξει μηπως?
Dr.Fuzzy Δημοσ. 16 Δεκεμβρίου 2008 Δημοσ. 16 Δεκεμβρίου 2008 Ξερει κανείς που μπορω να βρω καμια πληρη αποδειξη για το οτι μια εκδοχη του προβληματος TSP(travelling salesman problem) στην οποια θελουμε να βρουμε λυση κατω απο μια συγκεκριμενη τιμη(αξιας/αποστασης κλπ), ειναι NP-Complete? Εψαξα στο GOOGLE αλλα δεν βρηκα πληρη αποδειξη. Αν δεν υπαρχει καμια ελευθερη δημοσιευση στο ιντερνετ(γινεται?) περι αυτου, ξερει κανείς να το αποδειξει μηπως? Ειναι σχετικα γνωστο αυτο που θες. Πολυ συντομα, αρκει να δειξεις οτι το TSP ανηκει στο NP και μετα να αναγαγεις το μη-κατευθυνομενο hamiltonian cycle προβλημα στο TSP. Αν θες πληρη αποδειξη μπορεις για παραδειγμα να δεις εδω: http://www.cs.mun.ca/~kol/courses/6743-f07/lec10.pdf
Krokodilos Δημοσ. 16 Δεκεμβρίου 2008 Μέλος Δημοσ. 16 Δεκεμβρίου 2008 Ειναι σχετικα γνωστο αυτο που θες. Πολυ συντομα, αρκει να δειξεις οτι το TSP ανηκει στο NP και μετα να αναγαγεις το μη-κατευθυνομενο hamiltonian cycle προβλημα στο TSP. Αν θες πληρη αποδειξη μπορεις για παραδειγμα να δεις εδω: http://www.cs.mun.ca/~kol/courses/6743-f07/lec10.pdf Thanks.
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.