Add Papers Marked0
Paper checked off!

Marked works

Viewed0

Viewed works

Shopping Cart0
Paper added to shopping cart!

Shopping Cart

Register Now

internet library
Atlants.lv library
FAQ
1,99 € Add to cart
Add to Wish List
Want cheaper?
ID number:308287
 
Author:
Evaluation:
Published: 10.06.2011.
Language: Latvian
Level: Secondary school
Literature: 2 units
References: Not used
Table of contents
Nr. Chapter  Page.
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   
Extract

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.…

Author's comment
Load more similar papers

Atlants

Choose Authorization Method

Email & Password

Email & Password

Wrong e-mail adress or password!
Log In

Forgot your password?

Draugiem.pase
Facebook

Not registered yet?

Register and redeem free papers!

To receive free papers from Atlants.com it is necessary to register. It's quick and will only take a few seconds.

If you have already registered, simply to access the free content.

Cancel Register