„Az utazó ügynök problémája” változatai közötti eltérés
| [ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Egyértelműsítés |
a →A probléma: - nyomtatott áramkör hivatkozásának javítása |
||
12. sor:
===Kapcsolódó problémák===
# Ekvivalens [[gráfelmélet]]i megfogalmazása a problémának: Adott teljes élsúlyozott gráf esetén keressük a legkisebb összsúllyal rendelkező [[Hamilton-kör]]t. Megmutatható, hogy a kiindulási városba való visszatérés megkövetelése nem nehezít a probléma számítási nehézségén, tehát minimális súlyú [[Hamilton-út]] keresése egy adott pontból is [[NP-teljes]].
# A probléma egy másik változata, amikor nem a legkisebb súlyú [[Hamilton-kör]]t keressük, hanem azt, amelyikben a „legnehezebb” él súlya a lehető legkisebb. A logisztikai problémákon túl nagy gyakorlati jelentőséggel bír például a [[Nyomtatott_huzalozású_lemez|nyomtatott
# Az utazóügynök-probléma általánosított változatában „országok” szerepelnek egy vagy több „várossal”, az ügynök minden országból pontosan egy várost köteles meglátogatni, majd visszatérni kiindulási helyére. Behzad és Modarres<ref>{{Cite journal
| last1 = Behzad
| |||