Putnik

PUTNIK

Traveling Salesman problemini duymuşsunuzdur. Eğer duymuşsanız o problemin NP-hard olduğunu bilirsiniz çünkü iyi bir çözüm bulmak zordur.Pekala, bu soru ünlü problemin az rastlanan bir versiyonudur! Az rastlanması temel olarak 'çözülebilmesi'nden gelir.

Postacımız N tane şehri her birini tam olarak sadece bir kez dolaşmakla görevlidir.Şehirler 1,2,3...N olarak adlandırılır. Elimizde her şehirden birbirine giden yolların ne kadar sürdüğünü belirten bir tablo vardır. Postacı, mükemmel bir insan olduğundan, elindeki tablodan yola çıkarak öyle bir yol haritası oluşturmak ister ki toplam şehirleri dolaşma süresi minimum olsun.

Fakat herşey bu kadar kolay değildir. Postacının bir takıntısı vardır. O da şudur, her hangi bir K. şehir için kendinden önce gelen K-1 tane şehrin hepsini ya K'ya gitmeden önce dolaşmış, yada aynı şekilde hepsini K'ya gittikten sonra dolaşıcak olmalıdır.Başka bir deyişle, eğer K'dan küçük numaralı bir şehri K'ya gitmeden önce dolaşmışsa, K'ya gitmeden önce 1...K-1 şehirlerinin hepsini dolaşmış olması gerekmektedir.

Bu şartlara uyarak, postacının istediği şehirden başladığı ve istediği şehirde bitirdiği, bütün şehirleri dolaşmış olduğu minimum süreyi bulunuz.

GİRDİ

ilk satırda N (2 ≤ N ≤ 1500)

alt satırda NxN'lik bir tablo, i'inci satırdaki şehir ile j'inci sütundaki şehir arasındaki süreyi gösterir.

ÇIKTI

Tek satırda Minimum süre

ÖRNEKLER

girdi

3

0 5 2

5 0 4

2 4 0

çıktı

7

girdi

4

0 15 7 8

15 0 16 9

7 16 0 12

8 9 12 0

çıktı

31

Birinci girdideki çözümün şehir sıralaması : 2,1,3 veya 3,1,2

İkinci girdideki çözümün şehir sıralaması : 3, 1, 2, 4 veya 4, 2, 1, 3.

ÇÖZÜM

Postacının takıntısını giderecek tüm sıralamalara şu yolla ulaşabiliriz. İlk olarak 1. şehir sıralamaya eklenir sonra 2. şehir sıralamanın sağına veya soluna konulur, bu işlem N. şehire kadar devam eder ve bu yolla elde edilen her sıralama Postacının takıntısına uygundur.Artık soru dinamik programlama ile çözülebilir.Elde ettiğimiz sıralamaları listenin sağındaki ve solundaki şehir ile adlandıracağız.Bu iki şehiri bilmemiz demek bir sonraki eklenecek şehri bilmemiz demektir.Neden ? Çünkü o sıralamaya en son eklediğimiz şehir o sıranın ya solunda ya da sağında bulunmak zorundadır.Böylece ekliyceğimiz şehirin numarası onun bir fazlası olacaktır.Bu noktada ekleyeceğimiz şehir için sağa veya sola ekleme olmak üzere iki ihtimal vardır,Önceki bulduğumuz dinamik değerler ile, sağına veya soluna koyduğumuzda oluşucak minimum süreleri yeni dinamik değerler olarak bulabiliriz.Böyle ilerleyerek bütün şehirleri dolaştığımız en kısa süreyi dinamik dizi üzerinden buluruz.

O(N 2 ).

Soru: http://www.hsin.hr/coci/contest2_tasks.pdf

Girdi-Cikti: http://www.hsin.hr/coci/contest2_testdata.zip

İngilizce Çözüm: http://www.hsin.hr/coci/contest2_solutions.zip