Представяне на задачата за търговския пътник

1. Представяне на проблема

l  Формулиране:

Търговски пътник трябва да обходи N града, като тръгне от един град, приет за начален, и се върне в него, без да преминава два пъти през един и същ град и цената на транспортните разходи да е минимална. Да се определи маршрутът на търговския пътник, ако са известни пътните разходи между градовете, (когато такъв път съществува).

l  Едно възможно рещение:

Алгоритъмът на пълното изброяване за решаване на тази задача образува всички възможни маршрута ,(N-1)! на брой, оценява стойността на всеки и избира маршрутът с минимална стойност. Схематично(чрез псевдокод), алгоритъмът на пълното изброяване  е представен на следващите редове.

Алгоритъм

{

    - Въвеждане на входните данни

   Suma = max      // max  е някакво голямо число (може да е сума на всички                                                //  пътища)

   for (I = 1; I <= (N-1)!; I++)

  {

    - Образуване на поредната пермутация Pi от N -1 града.

    - Изчисляване сумата  Si на маршрута Pi.

      If ( Si < Suma)

      {

               Path=Pi;

               Suma=Si;

      }

  }

}

Входните данни за алгоритъма са:

Масив CENA :

                                      1             2         …                      N

1
2
…			Cij
N

Cij -  цена на маршрута между I-я  и  J-я  градове (Ако има такъв).

StartPoint -  номер на началния град

Резултатите са:

Suma – сумарна цена на маршрута

Масив Path:

StartPoint

….....

StartPoint

Асимптотичната оценка на този алгоритъм е  O(N!), което даже за малки стойности на N е неприемливо.

 Все още за науката не е известен „хубав“ алгоритъм, който да намира така наречения хамилтонов път. Проблема се смята за NP –  пълен.

l  Евристическо решение:

Съществуват различни идеи за евристическо решение на тази задача. Едно от решенията използва “метод на частните цели”, който се състои в следното:  Когато търговският пътник се намира в град I, се търси непосетен до този момент град J, с минимална цена на транспортните разходи до него спрямо другите, непосетени  до този момент градове, имащи връзка с I. Чрез този подход се получава неоптимално решение, а близко до оптималното, което може да се види от  следващата фигура.

Примерен граф на задачата за търговския пътник

Маршрутът  143251 е получен с евристически алгоритъм с начален град  - 1. (Той се оказва и оптимален за този граф)

Псевдокодът на евристическия алгоритъм е следния:

   { 

        - Въвеждане на входни данни.

        Suma=0;

        Br=0;

        Path[Br] = StartPoint;

        While (Br < N-1)

         {

              I=Path[Br];

              Избира се следващ град J, за който C[I,j] е минимално спрямо цената от I до останалите непосетени до момента градове.

              Suma = Suma + Cena[I,j];

              Br=Br+1;

              Path[Br]=J;

       }

       Suma=Suma+Cena(Path[Br], StartPoint);

   } /* край */

Асимптотичната оценката  на този алгоритъм е O(N*N), тъй като основният цикъл се повтаря N-1 пъти, а  във всеки цикъл има около N на брой операции.

II. Представяне на задачата за търговския пътник с Обобщени мрежи.

      Обобщените мрежи се използват за моделиране на реални процеси и проблеми, с тях ще се опитаме да представим и проблема на търговския пътник.

Нека първо въведем някой означения който ще използваме:

1. Нека t_i  и t_f са началния и крайния момент на процеса който моделираме, като е възможно t_f  = безкрайност. Time = { t_i,  t_f}
2. Нека T = {T1, T2, ... Tn} – е множество от пътуващи търговци
3. Нека C = {C1, C2, ... Cc} – множеството от всички продукти който търговците T продават, тук може да кажем, че всеки търговец не е задължително да предлага всички продукти.
4. Нека V = {V1, V2, ... Vv} – е множество от градове, който се посещават от търговците T.

            Сега ще дефинираме, някой функции, който ще използваме, в мрежата и на базата на който търговеца прави избор за своя маршрут между градовете.

1. Fi(t_i, Time ) = {Ci1, Ci2, ... Cim} – продуктите, който i-я търговец доставя в момента Time.
2. Q(t_i, C_{j ,}Time) – количеството на j-я продукт, който има i-я търговец в момента Time.
3. P(t_i, C_{j ,}Time)  - цената на j-я продукт, който i – я търговец от T има в момента Time.
4. L(t_i, C_{j ,}Time) – срок на годност на j-я продукт, който i-я търговец от множеството T има  в момента Time
5. M(Vk _,Time) = където Kkj > 0 е количеството продукти, който в града Vk, са необходими в момента Time.
6. D(Vk, Vk') – времето, което е необходимо за преминаване от върха Vk до съседния му връх Vk', като не е необходимо да имаме равенство в двете посоки на маршрута (Vk, Vk').
7. E(Vk, Vk', Time) – цената за пренос от връх Vk до неговия съседен Vk' в момента Time.
8. G(Vk, Vk' Time) – {0, 1} възможността за пренос от Vk до неговия съсед Vk' в момента Time.

Така в рамките на даден интервал от време може пътищата да бъдат затворени и преминаването по директния път между двата града да не е възможно, затова ще въведем една друга функция, която да казва предполагаемо време когато затворения път(ако е затворен) ще бъде на разположение.

9. O(Vk, Vk', Time) – времето, което се чака до отварянето на пътя между градовете Vk и Vk' от момента Time, ако пътя в момента е отворен то времето за чакане е 0 иначе ако не е сигурно кога ще бъде отворен пътя, то времето е  = безкрайност.
10.  R(Ti, Vk, Time) – стойноста на печалба на Ti  в града Vk, това определяме по следния начин:

R(Ti, Vk, Time) = Сумата на печалбата от всеки продукт който предлага търговеца, като за всеки продукт печалбата е равна на количеството на стоката по нейната цена, т.е

R(Ti, Vk, Time) = Сума по всички стоки(Q(t_i, C_{j ,}Time) * P(t_i, C_{j ,}Time)). Всичко това правим с уговорка, че нуждите на даден град надвишават количеството, което дадения търговец носи.

11. N(Ti, Vk, Time) – времето, което търговеца Ti прекарва в града Vk след момента Time.
12. S (Ti, Cj, Vk, Time) – {0, 1} – дали цената на j-я продукт , предлагана от i-я търговец в града Vk е конкурентно способна(приемлива).

Сега трябва представим така посочената мрежа.

Имаме две входни позиции - това са състоянията l₁  и  l2 ядрата, който се движат по мрежата започват именно от тези две начални състояния. Всяко ядро описва поведението на един търговец, който се стреми да изкара най-голяма печалба продавайки стоката си.

Сега да дадем описание на някой от основните преходи r_i  ,

Прехода r1:

	l3	l4	l6	l14
l1	True	False	False	False
l2	False	False	True	False
l3	W1	W2	False	W3
l9	W1	W2	False	W3
l11	False	False	True	False

Където имаме следната стойност на предикатите Wi.

W1 – има поне един допълнителен път (повече от един), през който ядрото може да премине

W2 – има път по който ядрото може да премине

W3 – противоположно на W2 т.е няма път по който ядрото може да премине.

r₁ e началния преход за мрежата, като той проверява дали има път по който даден търговец може да продължи движението си, в зависимост от условита го пренасочва в различни състояния.

Прехода r2:

	l5
l4	W4

Където W4  = „Time >  pr₂ X_cu^α“

Прехода r3:

	l7
l5	W5

Като W5 = „Time >  X_cu^α“

Прехода r4:

	l8	l9	l10	l11
l7	W6	W7	False	False
l6	False	False	W6	W7

Като:

W6 = „Time > T + t_x“ като t_x е Ti - T

W7 = отрицанието на предиката W6.

Прехода r5:

	l12	l13
l8	W8	W9
l12	W9	W8
l14	W8	W9

Като:

W8 = c(l12, Time) = 0  v  X_cu^{αi >}  X_cuⁱ

където

-         c(l, t) е броя на преходите в състояние l, в момента t.

-         X_cu^αi  е текущата характеристика на i-тото ядро „алфа“ което се намира в състояние l12.

W9 = отрицанието на предиката W8.

Ядрата α1,  α2, ...  αt с начални характеристики „Ti“ влизат в състояние l1 в момента Time = t и след това веднага преминават в състояние l3 . Там те приемат нови характеристики μ(Ti, Time) {<c_{j , Q(Ti, Cj, Time), P(Ti, Cj, Time), L(Ti, Cj, Time), S(Ti, Cj, Vk, Time) > като Cj е от  Fi(Ti, Time)}}

Където μ(Ti, Time) е за върха Vk където търговеца Ti се намира.

Едновременно с този преход ядрото β влиза в състояние l2.с начална характеристика:

 β = {Vk, M(Vk, Time), { като Vk' е от множеството от съседите на върха Vk}}

Ядрата α се разделята на в състояние  l3  (ако Ti има възможност за движение) и в състояние  l4 (Ако пътя за движение на търговеца Ti  е уникален).

В състояние  l4  някой от ядрата трябва да бъдат генерирани който имат по един линеен предчественик. Всички ядра, който имат еднакви(равни) начални характеристики „Ti“ са различни представяния на ядрото  α_i и няма конкурентна ситуация между тях.

В този модел съществува конкуренция спрямо цената на даден предлаган продукт, ако цената на даден търговец е неконкурентно способна спрямо  на друг то този град не му носи никаква печалба и той не трябва да ходи там. Така когато в началото ядрата получат характеристика за даден град те преценяват дали да преминат в този град(т.е дали тяхната цена е добра или не).

Ядрата  α_i не приемат нови характеристики в  l3 но в  l4  те приемат характеристика:

-         „Vk, Time + D(Vk, Vk') “ където Vk' е връх който Ti (търговеца) ще посети.

След преминаването им от  l4 в  l5 ядрото α приема характеристика:

-         „Time + N( pr₁ X₀^α ,  pr₁ X_cu^α , Time) “

А в състояние  l7 характеристика:

-         R(pr₁ X₀^α ,  pr₁ X_cu^α , Time) - E(pr₁ X_cu-2^α ,  pr₁ X_cu-1^α , Time)

Което е и неговата печалба.

Когато ядро α_i влезе в състояние l₉ то приема като текуща характеристика името на върха където се намира в текущия момент т.е μ(Ti, Time).

В състояние  l8 тези ядра приемат характеристика стойността на изминатия път от ядрото в мрежата сподер критерия „максимална печалба“.

Накрая ядрото α_i с максимална печалба e търсеното в задачата. Така определихме възможната максимална печалба.

Трябва да отбележим че:

-         В рамките на един такт всички ядра, който могат да преминат по някой преход го прават

-         t⁰  (елементарно време) е времето свързано с престоя или прехода на търговеца (и може да е например 1 минута)

-         Преходите се активират всеки момент относно някакво фиксирано време.

-         Продължителността на прехода е t⁰

-         Капацитета на всички дъги и състояния е „безкрайност“ с изключение на

c(l2) = c(l6) = c(l10) = c(l11) = 1

-         приоритетите на всички състояния и преходи са равни с изключение на  l8 l14 и l12 .

-         Трябва да поставим все пак някакво ограничение на броя на ядрата за да може мрежата да функционира нормално.