• Bitonic euclidean traveling-salesman problem The euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane. Figure 15.9(a) shows the solution to a 7-point problem. The general problem is NP-complete, and its solution is therefore believed to require more than polynomial time . J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the left most point, go strictly left to right to the right most point, and then go strictly right to left back to the starting point. Figure 15.9(b) shows the shortest bitonic tour of the same 7 points. In this case, a polynomial-time algorithm is possible. Describe an O(n 2 )- time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same x-coordinate. (Hint:Scan left to right, maintaining optimal possibilities for the two parts of the tour.)

resimleri ekleyemedim boyut büyüktü diye yardımcı olabilirseniz resimleride eklerim.

Şimdiden teşekkürler

soruldu: 22 May '13, 03:04

g%C3%B6ky%C3%BCz%C3%BC's gravatar image

gökyüzü
-1112
cevap kabul oranı: 0%

kapatıldı: 22 May '13, 03:08

CemIkta's gravatar image

CemIkta ♦
19.9k29125190

Bu ödev sorusuna benziyor. Direk kopyala yapıştır ile buraya eklemişsiniz. Bu konu ile uğraşmadan direk olarak buraya yazmışsınız. Uğraşmamışsınız diyorum, zira en azından soruyu türkçeye çevirme zahmetinde bile bulunmamışsınız. Bence önce BTSoru.com u bir inceleyin, siteyi tanıyın ondan sonra soru sorun.

(22 May '13, 03:28) AliRıza Adıyahşi ♦ AliR%C4%B1za%20Ad%C4%B1yah%C5%9Fi's gravatar image

Bu soru 22 May '13, 03:08 CemIkta tarafından "Soru konu dışı ya da uygun değil! Soru BTSoru kurallarina uymuyor! Lütfen Türkce sorular sorunuz!" gerekçesiyle kapatıldı.

Bu soruyu takip et

E-Posta üzerinden:

Üyelik girişi yaptıktan sonra abonelik işlemlerini yapabilirsiniz

RSS üzerinden:

Cevaplar

Cevaplar ve Yorumlar

Yazı Formatlama

  • *italic* ya da _italic_
  • **bold** ya da __bold__
  • link:[text](http://url.com/ "başlık")
  • resim?![alt text](/path/img.jpg "başlık")
  • liste: 1. Foo 2. Bar
  • temel HTML etiketleri de kullanılabilir

Bu sorunun etiketleri:

×2

Soruldu: 22 May '13, 03:04

Görüntüleme: 368 kez

Son güncelleme: 22 May '13, 03:32

powered by BitNami OSQA