Outrun more than 2 paths algorithm

Outrun algorithms

8 March 2014

Въведение

Понякога се налага да се надбягат повече от 2 пътя. Например, когато има повече от 2 пътя и трябва всеки да се надбяга с всеки.

Когато се надбягват 2 пътя при напредването на един път се съобразява, кога ще надмине другия. Но когато са повече пътища, то втория път може да надмине третия, а да не надмине първия, който е бил най-вляво. За целта може да се поддържат пътищата винаги подредени така, че да се проверява дали активния път ще надмине първия път в списъка. Ако не го надмине, то няма да надмине и другите в списъка. Ако го надмине, то може да надмине и следващите. Проверява колко ще надмине и застава след тях.

Пример

Примерно имаме 3 поредици
1, 2, 3, 4, 5, 20, 30, 40, 50
25, 35, 100
42, 52, 70, 80, 90
Пътищата са подредени от най-левия към най-десния.

Ресурси

Активен път - Активни пътища - Активен сегмент от път - Активен сегмент за надбягване - Бегач на пътя - Списък на чакащите (на следващите) -

Активен участък

Първо единия път започва. Активен му е първия участък. Ако не изпреварва сегмента на следващия път става активен следващия участък на същия път. Ако изпреварва слеващия

Смяна на активния път

Когато активния път задмине втория път, то е възможно да задмине и други пътища след него. Затова се премества след пътищата, които е задминал, за да се запази подредбата на пътищата по най-ляв ективен сегмент. Вторият път става първи. Намира пътищата които надбягва ако надбягва всички пътища застава последен

				
	lastPath.Next := currentPath;
	currentPath.Next := nil;

ако надбяга един или няколко, но не е последен

				
	prevPath.Next := currentPath;
	currentPath.Next := path;

Това е пълния код,
където marker е активния маркер, който се мести,
а marker2 е следващия след него.
Покриват се случаите, когато
- втория маркер е последен
- когато задминава всички маркери
- когато се вмъква между маркери

				
  // Move marker after the outruned markers
  procedure moveAfterTheLastOutruned();
  begin
    nextMarker := marker2.next;
    if (nextMarker = nil) then begin
      mrker2.Next := marker; // Move after the first(and last) marker
      marker.Next := nil; // cause now the active marker will be last
      exit; // cause it is done
    end

    while nextMarker.Point1.X < marker.Point2.X do begin
      marker2 := nextMarker;
      nextMarker := nextMarker.Next;
      if (nextMarker = nil) then begin
        mrker2.Next := marker; // to move the active marker after the last marker
        marker.Next := nil; // cause now the active marker will be last
        exit; // cause it's done
      end;
    end;

    marker2.Next := marker; // to move it after the last outruned
    marker.Next := nextMarker; // to have not outruned markers after it
  end;

Условия за край

Във всеки момент един от двата пътя догонва другия. Когато един път догонва друг, то може да не успее да го догони. Тогава последния елемент от пътя, който достига до края, му се присвоява следващ елемент, този който догонва. След което останалите елементи от другия път си запазват подредбата. Може да не се проверяват до края елементите. Последния елемент ще си има Nil за следващ елемент. Така приключването на алгоритъма се проверява за достигане на края на пътя, който догонва.

Програмиране

В програмирането надбягващия се алгоритъм може да се изнесе в отделен клас. Който да си има първоначално догонване, проверки. Да си прави всичко. Да си взема стойности за двата списъка. Да вика за проверка. Може да ползва и компаратор. И да му се подават стандартни списъци и да ги надбягва.

Код

					
function TDSClipper.order2(runner1, runner2: TRunMarker): TRunMarker;
var
  prev: TRunMarker;
begin

  if (runner1.Point1.X <= runner2.Point1.X) then begin
    Result := runner1;
  end
  else begin
    Result := runner2;

    prev := runner2;
    runner2 := runner2.Next;

    if (runner2 = nil) then begin
      prev.Next := runner1;
      exit;
    end;

    while runner2.Point1.X < runner1.Point1.X do begin
      prev := runner2;
      runner2 := runner2.Next;
      if (runner2 = nil) then begin
        prev.Next := runner1;
        exit;
      end;
    end;

    prev.Next := runner1;
  end;

  while true do begin
    prev := runner1;
    runner1 := runner1.Next;

    if (runner1 = nil) then begin
      // there is only one element in the first linked list
      prev.Next := runner2;
      exit;
    end;

    while runner1.Point1.X <= runner2.Point1.X do begin
      prev := runner1;
      runner1 := runner1.Next;
      if (runner1 = nil) then begin
        prev.Next := runner2;
        exit;
      end;
    end;

    prev.Next := runner2;

    prev := runner2;
    runner2 := runner2.Next;

    if (runner2 = nil) then begin
      prev.Next := runner1;
      exit;
    end;

    while runner2.Point1.X < runner1.Point1.X do begin
      prev := runner2;
      runner2 := runner2.Next;
      if (runner2 = nil) then begin
        prev.Next := runner1;
        exit;
      end;
    end;

    prev.Next := runner1;
  end;

end;

Back to main menu