Pievienot darbus Atzīmētie0
Darbs ir veiksmīgi atzīmēts!

Atzīmētie darbi

Skatītie0

Skatītie darbi

Grozs0
Darbs ir sekmīgi pievienots grozam!

Grozs

Reģistrēties

interneta bibliotēka
Atlants.lv bibliotēka

Izdevīgi: šodien akcijas cena!

Parastā cena:
1,99
Ietaupījums:
0,24 (12%)
Cena ar atlaidi*:
1,75
Pirkt
Identifikators:308287
Autors:
Vērtējums:
Publicēts: 10.06.2011.
Valoda: Latviešu
Līmenis: Vidusskolas
Literatūras saraksts: 2 vienības
Atsauces: Nav
SatursAizvērt
Nr. Sadaļas nosaukums  Lpp.
1.  Ievads   
2.  Ceļojošā tirgotāja problēma   
2.1.  Ceļojošā tirgotāja problēmas iedalījums   
2.2.  Algoritmi   
2.3.  Pielietojums   
3.  Secinājumi   
Darba fragmentsAizvērt

Ceļojošā tirgotāja problēmai jau vairākus gadus ir pievērsta matemātiķu un datoru zinātnieku uzmanība, jo to ir viegli formulēt, bet grūti atrisināt. Problēmu vienkārši var noteikt: ja ceļojošais tirgotājs vēlas apmeklēt tieši vienu no m sarakstā esošajām pilsētām (kur ceļošanas izmaksas no pilsētas i uz pilsētu j ir cij) un pēc tam atgriezties savā mājas pilsētā, tad kāds ir vislētākais ceļš, pa kuru ceļotājs var doties.
Ceļojošā tirgotāja problēma pieder pie kombinatorikas optimizācijas problēmu apakšklases NP-pilna. Ja ceļojošā tirgotāja problēmai tiks atrasts efektīvs risināšanas algoritms (t.i., algoritms kas garantē atrast optimālu risinājumu ar polinomu izteiktu soļu skaitu), tad efektīvi algoritmus varētu atrast visai NP-pilns klasei. Pašreiz šāds risinājums ceļojošā tirgotāja problēmai nav atrasts. Vai tas nozīmē ka nav iespējams atrisināt šo problēmu lielu instanci? Daudzas lielas mēroga praktiskas optimizācijas problēmas ir atrisinātas balstoties uz iegūtajām zināšanām. 1994. gadā tika atrisināta ceļojošā tirgotāja problēma, kas modelē iespiedplates caurumu urbšanu iespiedplatei ar 7397 caurumiem (pilsētām). 1998. gadā tika atrisināta problēma ar ASV 13509 lielāko pilsētu apceļošanu.…

Autora komentārsAtvērt
Parādīt vairāk līdzīgos ...

Nosūtīt darbu e-pastā

Tavs vārds:

E-pasta adrese, uz kuru nosūtīt darba saiti:

Sveiks!
{Tavs vārds} iesaka Tev apskatīties interneta bibliotēkas Atlants.lv darbu par tēmu „Ceļojošā tirgotāja problēma”.

Saite uz darbu:
https://www.atlants.lv/w/308287

Sūtīt

E-pasts ir nosūtīts.

Izvēlies autorizēšanās veidu

E-pasts + parole

E-pasts + parole

Norādīta nepareiza e-pasta adrese vai parole!
Ienākt

Aizmirsi paroli?

Draugiem.pase
Facebook
Twitter

Neesi reģistrējies?

Reģistrējies un saņem bez maksas!

Lai saņemtu bezmaksas darbus no Atlants.lv, ir nepieciešams reģistrēties. Tas ir vienkārši un aizņems vien dažas sekundes.

Ja Tu jau esi reģistrējies, vari vienkārši un varēsi saņemt bezmaksas darbus.

Atcelt Reģistrēties