петък, 2 декември 2011 г.

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

  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. Нека ti  и tf са началния и крайния момент на процеса който моделираме, като е възможно t= безкрайност. Time = { ti,  tf}
  2. Нека T = {T1, T2, ... Tn} – е множество от пътуващи търговци
  3. Нека C = {C1, C2, ... Cc} – множеството от всички продукти който търговците T продават, тук може да кажем, че всеки търговец не е задължително да предлага всички продукти.
  4. Нека V = {V1, V2, ... Vv} – е множество от градове, който се посещават от търговците T.

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

  1. Fi(ti, Time ) = {Ci1, Ci2, ... Cim} – продуктите, който i-я търговец доставя в момента Time.
  2. Q(ti, Cj ,Time) – количеството на j-я продукт, който има i-я търговец в момента Time.
  3. P(ti, Cj ,Time)  - цената на j-я продукт, който i – я търговец от T има в момента Time.
  4. L(ti, Cj ,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.
Така в рамките на даден интервал от време може пътищата да бъдат затворени и преминаването по директния път между двата града да не е възможно, затова ще въведем една друга функция, която да казва предполагаемо време когато затворения път(ако е затворен) ще бъде на разположение.
  1. O(Vk, Vk', Time) – времето, което се чака до отварянето на пътя между градовете Vk и Vk' от момента Time, ако пътя в момента е отворен то времето за чакане е 0 иначе ако не е сигурно кога ще бъде отворен пътя, то времето е  = безкрайност.
  2.  R(Ti, Vk, Time) – стойноста на печалба на Ti  в града Vk, това определяме по следния начин:
R(Ti, Vk, Time) = Сумата на печалбата от всеки продукт който предлага търговеца, като за всеки продукт печалбата е равна на количеството на стоката по нейната цена, т.е
R(Ti, Vk, Time) = Сума по всички стоки(Q(ti, Cj ,Time) * P(ti, Cj ,Time)). Всичко това правим с уговорка, че нуждите на даден град надвишават количеството, което дадения търговец носи.
  1. N(Ti, Vk, Time) – времето, което търговеца Ti прекарва в града Vk след момента Time.
  2. S (Ti, Cj, Vk, Time) – {0, 1} – дали цената на j-я продукт , предлагана от i-я търговец в града Vk е конкурентно способна(приемлива).




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

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

Прехода 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 т.е няма път по който ядрото може да премине.

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

Прехода r2:


l5
l4
W4

Където W4  = „Time >  pr2 Xcuα

Прехода r3:


l7
l5
W5


Като W5 = „Time >  Xcuα


Прехода r4:


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

Като:
W6 = „Time > T + tx“ като tx е Ti - T
W7 = отрицанието на предиката W6.

Прехода r5:


l12
l13
l8
W8
W9
l12
W9
W8
l14
W8
W9





Като:
W8 = c(l12, Time) = 0  v  Xcuαi >  Xcui

където
-         c(l, t) е броя на преходите в състояние l, в момента t.
-         Xcuαi  е текущата характеристика на i-тото ядро „алфа“ което се намира в състояние l12.

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

Ядрата α1,  α2, ...  αt с начални характеристики „Ti“ влизат в състояние l1 в момента Time = t и след това веднага преминават в състояние l3 . Там те приемат нови характеристики μ(Ti, Time) {<cj , 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  е уникален).

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

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

Ядрата  αi не приемат нови характеристики в  l3 но в  lте приемат характеристика:
-         „Vk, Time + D(Vk, Vk') “ където Vk' е връх който Ti (търговеца) ще посети.

След преминаването им от  l4 в  l5 ядрото α приема характеристика:
-         „Time + N( pr1 X0α ,  pr1 Xcuα , Time) “

А в състояние  l7 характеристика:
-         R(pr1 X0α ,  pr1 Xcuα , Time) - E(pr1 Xcu-2α ,  pr1 Xcu-1α , Time)

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

Когато ядро αi влезе в състояние l9 то приема като текуща характеристика името на върха където се намира в текущия момент т.е μ(Ti, Time).
В състояние  l8 тези ядра приемат характеристика стойността на изминатия път от ядрото в мрежата сподер критерия „максимална печалба“.

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

Трябва да отбележим че:
-         В рамките на един такт всички ядра, който могат да преминат по някой преход го прават
-         t0  (елементарно време) е времето свързано с престоя или прехода на търговеца (и може да е например 1 минута)
-         Преходите се активират всеки момент относно някакво фиксирано време.
-         Продължителността на прехода е t0
-         Капацитета на всички дъги и състояния е „безкрайност“ с изключение на
c(l2) = c(l6) = c(l10) = c(l11) = 1
-         приоритетите на всички състояния и преходи са равни с изключение на  l8 l14 и l12 .
-         Трябва да поставим все пак някакво ограничение на броя на ядрата за да може мрежата да функционира нормално.



Няма коментари:

Публикуване на коментар