Zine.net online

Witaj na Zine.net online Zaloguj się | Rejestracja | Pomoc
w Szukaj

dev2dev

Najkrótsza droga w labiryncie (w T-SQL!)

Interesujący problem został przedstawiony na wss.pl. To klasyczny problem labiryntu. Zmieniłem nieco definicję danych wejściowych problemu zastępując tablicę tymczasową tablicą pamięciową.

declare @t table (n int, r char(10)) values
( 1, ' '),
( 2, ' S '),
( 3, 'xxxxxx '),
( 4, ' '),
( 5, ' '),
( 6, ' xxxxxx'),
( 7, ' '),
( 8, ' E'),
( 9, ' '),
(10, ' '),

Rozwiązaniem problemu jest znalezienie najkrótszej drogi pomiędzy dwoma punktami z uwzględnieniem punktów zabronionych (murów). Nie można stosować zmiennych i pętli, można stosować jedynie instrukcje SELECT i CTE.

Rozwiązanie powinno sie dać uzyskać poprzez wygenerowanie wszystkich możliwych ciągów permutacji dwuelementowych bez powtórzeń ze zbioru {1,10} rozpoczynających się od permutacji S(w,k) do permutacji E(w,k) (z wyłączeniem permutacji określających punkty muru) gdzie kolejne permutacje różnią się jednym elementem i różnią się wyłącznie o wartość 1. Wskaźniki permutacji są to wiersz i kolumna macierzy.

Rozwiązanie nie powinno zależeć od istnienia murów. Zawsze można usunąć dowolne punkty ze zbioru możliwych permutacji. Maksymalna ilość dopuszczalnych permutacji (poza punktem startowym) to N x N-1 bez istnienia murów i N x N-M-1 gdzie M jest całkowitą długością murów). Wygenerowanie wszystkich takowych ciągów permutacji dla tablicy 10 x 10 wydaje sie być zadaniem karkołomnym czasowo. W związku z tym postanowiłem działać indukcyjnie – od macierzy mniejszych rozmiarów.

Zbudowałem macierz o rozmiarze 6 x 6:

declare @t table (n int, r char(6))
insert into @t values
(1, '      '),
(2, ' S    '),
(3, 'xxxx  '),
(4, '      '),
(5, '   xxx'),
(6, '     E')

declare @n int = (select DATALENGTH(r) from @t where n =1 )

powstałą przez zredukowanie wierszy i kolumn przy zachowaniu ogólnego wyglądu danych podstawowych. Aby ułatwić sobie generowanie rozwiązań dodałem zmienną @n określającą rozmiar macierzy (jest to jedyna zmienna w rozwiązaniu ale nie jest ona wykorzystywana do przechowywania wyników a jedynie wykorzystywana zamiast stałej).

Moje rozwiązanie będzie sie składało z szeregu wywołań CTE, które będę prezentował kolejno. Na koniec podam kompletne rozwiązanie.

I. Zapytanie (algorytm)

1. Współrzędne punktu startu:

;with start as
(
select n w, CHARINDEX('S',r) k
from @t
where r like '%S%'
)

2. Współrzędne punktu docelowego:

, stop as
(
select n w, CHARINDEX('E',r) k
from @t
where r like '%E%'
)

3. Uzyskanie współrzędnych “cegieł w murze”. CTE wall wyciąga wiersze zawierające znak X, CTE bricks wyciąga “cegły”, CTE brickPos podaje współrzędne położenia “cegły” w murze.

, wall as
(
select n w
from @t
where r like '%X%'

, bricks as
(
select t.n w, 1 as k, SUBSTRING(r,1,1) b, r
from @t t
inner join wall w on w.w = t.n
union all
select b.w, b.k+1, SUBSTRING(b.r,b.k+1,1), r
from bricks b
where b.k < @n
)
, brickPos as
(
select b.w, b.k
from bricks b
where b.b = 'X'
)

4. Utworzenie tabeli wierzy numerów wierszy (allRows) i kolumn (allCols):

, allRows as
(
select 1 as r
union all
select a.r+1 r
from allRows a
where a.r < @n)
, allCols as
(
select 1 as c
union all
select a.c+1 c
from allCols a
where a.c < @n)

5. Utworzenie tabeli możliwych do wykorzystania permutacji. Każdy element tabeli zawiera permutację składającą sie z numeru wiersza i kolumny tabeli danych wejściowych. Z tabeli permutacji usunięty został punkt startowy oraz wszystkie “cegły”.

, points as
(
select r.r w, c.c k
from allRows r, allCols c
except
select b.w, b.k
from brickPos b
except
select s.w, s.k
from start s
)

6. Generowanie ciągów permutacji bez powtórzeń z permutacji zawartych w tabeli generowanej przez CTE points. CTE routes ma jedną kotwicę będącą permutacją określającą punkt startowy. Nie musimy sie martwić o przeszkody na drodze ponieważ permutacje je określające zostały już przez nas wyeliminowane w pkt. 5. CTE routes musi mieć cztery elementy rekursywne określające cztery możliwe do wyboru następne permutacje (odpowiadające czterem kierunkom ruchu).

, routes as
(
select w,k,
cast('('+CAST(w as varchar(2))+','+
CAST(k as varchar(2))+')' as varchar(max)) path,
1 level
from start
-------------
union all
select r.w, r.k+1,
cast(r.path+',('+CAST(r.w as varchar(2))+','+
CAST(r.k+1 as varchar(2))+')' as varchar(max)),
r.level+1
from routes r
inner join points p on p.k = r.k+1 and p.w = r.w
where not(r.k+1 = (select k from stop) and r.w = (select w from stop))
and r.path not like '%('+CAST(r.w as varchar(2))+','+
CAST(r.k+1 as varchar(2))+')%'
---------------
union all
select r.w, r.k-1,
cast(r.path+',('+CAST(r.w as varchar(2))+','+
CAST(r.k-1 as varchar(2))+')' as varchar(max)),
r.level+1
from routes r
inner join points p on p.k = r.k-1 and p.w = r.w
where not(r.k-1 = (select k from stop) and r.w = (select w from stop))
and r.path not like '%('+CAST(r.w as varchar(2))+','+
CAST(r.k-1 as varchar(2))+')%'
---------------
union all
select r.w-1, r.k,
cast(r.path+',('+CAST(r.w-1 as varchar(2))+','+
CAST(r.k as varchar(2))+')' as varchar(max)),
r.level+1
from routes r
inner join points p on p.k = r.k and p.w = r.w-1
where not(r.w-1 = (select w from stop) and r.k = (select k from stop))
and r.path not like '%('+CAST(r.w-1 as varchar(2))+','+CAST(r.k as varchar(2))+')%'
-----------------
union all
select r.w+1, r.k,
cast(r.path+',('+CAST(r.w+1 as varchar(2))+','+
CAST(r.k as varchar(2))+')' as varchar(max)),
r.level+1
from routes r
inner join points p on p.k = r.k and p.w = r.w+1
where not(r.w+1 = (select w from stop) and r.k = (select k from stop))
and r.path not like '%('+CAST(r.w+1 as varchar(2))+','+CAST(r.k as varchar(2))+')%'
)

7. Prezentacja wszystkich permutacji prowadzących od punktu startowego do punktu końcowego (czyli po prostu drgi z punktu startowego do punktu końcowego):

select r.level+1,
r.path+',('+CAST((select w from stop) as varchar(2))+','+
CAST((select k from stop) as varchar(2))+')'
from routes r
where (r.k = (select k-1 from stop) and r.w = (select w from stop)) or
(r.k = (select k+1 from stop) and r.w = (select w from stop)) or
(r.k = (select k from stop) and r.w = (select w+1 from stop)) or
(r.k = (select k from stop) and r.w = (select w-1 from stop))
order by r.level
option (maxrecursion 100)

Dla podanych danych uzyskałem jedną najkrótszą trasę o długości 13:


Co prowadzi do rozwiązania graficznego:


Dla tych danych istnieją również dwie najdłuższe drogi o długości 29:


I jego reprezentacja graficzna dla rozwiązania numer 924:


oraz dla rozwiązania numer 923:


Poszukiwanie najdłuższych tras jest moim zdaniem ciekawsze niż znajdowanie najkrótszych. Przypomina trochę problem wypełnienia płaszczyzny krzywą. I nie jest łatwe do uzyskania metodą “na oko” co jest łatwiejsze w przypadku poszukiwania drogi najkrótszej.

II. Relacje czasowe

Rozwiązania przetestowałem dl dla następujących rozmiarów macierzy:

Rozmiar macierzy

Czas wykonania [sek]

5x5

1

6x6

8

7x7

923

8x8

w momencie pisania tego tekstu 4 godziny i nie było widać końca

Z zestawienia widać, że wzrost nakładów obliczeniowych następuje lawinowo (postaram się wytrwać w poszukiwaniu rozwiązania 8x8, ). Poszukiwanie rozwiązania dla macierzy 10x10 pewnie trwałoby “wieczność”.

III. Kompletne rozwiązanie

declare @t table (n int, r char(6))
insert into @t values
(1, '      '),
(2, ' S    '),
(3, 'xxxx  '),
(4, '      '),
(5, '   xxx'),
(6, '     E')

declare @n int = (select DATALENGTH(r) from @t where n =1 )

;with start as
(
select n w, CHARINDEX('S',r) k
from @t
where r like '%S%'
)
, stop as
(
select n w, CHARINDEX('E',r) k
from @t
where r like '%E%'
)
, wall as
(
select n w
from @t
where r like '%X%'
)
, bricks as
(
select t.n w, 1 as k, SUBSTRING(r,1,1) b, r
from @t t
inner join wall w on w.w = t.n
union all
select b.w, b.k+1, SUBSTRING(b.r,b.k+1,1), r
from bricks b
where b.k < @n
)
, brickPos as
(
select b.w, b.k
from bricks b
where b.b = 'X'
)
, allRows as
(
select 1 as r
union all
select a.r+1 r
from allRows a
where a.r < @n)
, allCols as
(
select 1 as c
union all
select a.c+1 c
from allCols a
where a.c < @n)
, points as
(
select r.r w, c.c k
from allRows r, allCols c
except
select b.w, b.k
from brickPos b
except
select s.w, s.k
from start s
)
, routes as
(
select w,k,
cast('('+CAST(w as varchar(2))+','+
CAST(k as varchar(2))+')' as varchar(max)) path,
1 level
from start
-------------
union all
select r.w, r.k+1,
cast(r.path+',('+CAST(r.w as varchar(2))+','+
CAST(r.k+1 as varchar(2))+')' as varchar(max)),
r.level+1
from routes r
inner join points p on p.k = r.k+1 and p.w = r.w
where not(r.k+1 = (select k from stop) and r.w = (select w from stop))
and r.path not like '%('+CAST(r.w as varchar(2))+','+
CAST(r.k+1 as varchar(2))+')%'
---------------
union all
select r.w, r.k-1,
cast(r.path+',('+CAST(r.w as varchar(2))+','+
CAST(r.k-1 as varchar(2))+')' as varchar(max)),
r.level+1
from routes r
inner join points p on p.k = r.k-1 and p.w = r.w
where not(r.k-1 = (select k from stop) and r.w = (select w from stop))
and r.path not like '%('+CAST(r.w as varchar(2))+','+
CAST(r.k-1 as varchar(2))+')%'
---------------
union all
select r.w-1, r.k,
cast(r.path+',('+CAST(r.w-1 as varchar(2))+','+
CAST(r.k as varchar(2))+')' as varchar(max)),
r.level+1
from routes r
inner join points p on p.k = r.k and p.w = r.w-1
where not(r.w-1 = (select w from stop) and r.k = (select k from stop))
and r.path not like '%('+CAST(r.w-1 as varchar(2))+','+CAST(r.k as varchar(2))+')%'
-----------------
union all
select r.w+1, r.k,
cast(r.path+',('+CAST(r.w+1 as varchar(2))+','+
CAST(r.k as varchar(2))+')' as varchar(max)),
r.level+1
from routes r
inner join points p on p.k = r.k and p.w = r.w+1
where not(r.w+1 = (select w from stop) and r.k = (select k from stop))
and r.path not like '%('+CAST(r.w+1 as varchar(2))+','+CAST(r.k as varchar(2))+')%'
)
select r.level+1,
r.path+',('+CAST((select w from stop) as varchar(2))+','+
CAST((select k from stop) as varchar(2))+')'
from routes r
where (r.k = (select k-1 from stop) and r.w = (select w from stop)) or
(r.k = (select k+1 from stop) and r.w = (select w from stop)) or
(r.k = (select k from stop) and r.w = (select w+1 from stop)) or
(r.k = (select k from stop) and r.w = (select w-1 from stop))
order by r.level
option (maxrecursion 100)

Miłej zabawy w poszukiwaniu właściwej drogi!

Opublikowane 14 maja 2010 20:57 przez marekpow
Filed under: ,

Komentarze:

 

mgrzeg said:

Dzizas! Jestem pod wrazeniem wysilku, podziwiam wytrwalosc i zaciecie, choc przyznaje, nie rozumiem celu :) Ale - szacun!

maja 17, 2010 13:50
 

marekpow said:

Cel jest jeden. Ciągle w górę! A przy okazji fajna rozrywka umysłowa.

maja 17, 2010 14:32
Komentarze anonimowe wyłączone
W oparciu o Community Server (Personal Edition), Telligent Systems