[Teoria Grafów] Dowód na NP trudność Problemu Komiwojażera

KStudniarek · Post autor: **KStudniarek** » 11 paź 2013, o 09:47

Cześć,

Jestem studentem informatyki na WPPT Politechniki Wrocławskiej i właśnie zaczynam pisać swoją pracę inżynierską. Temat mam dość wdzięczny bo: "Porównanie wybranych heurystyk i algorytmu aproksymacyjnego na podstawie problemów NP trudnych". Właśnie zbieram wszystkie materiały i tutaj pytanie do was:

Czy ktoś kiedykolwiek trafił na sensowny dowód NP trudności problemu Komiwojażera i w jakiej książce (nie tylko książce) można go znaleźć?

Pozdrawiam,
Krzysztof Studniarek

bartek118 · Post autor: **bartek118** » 11 paź 2013, o 10:00

Tutaj masz dowód podobnego problemu: _ ... is_NP-hard

A problem komiwojażera bez problemu można do niego sprowadzić w czasie wielomianowym.