prezentacja wyklad 10

background image

Hetmani – cd.

2

Czterech hetmanów

:

- dla uproszczenia zostan

ą

pokazane kolejne kroki dla zagadnienia

ustawienia czterech hetmanów na planszy 4x4.

Rozwi

ą

zanie

:

Istniej

ą

dwa rozwi

ą

zania tego zadania:

[2,4,1,3]

H

H

H

H

[3,1,4,2]

H

H

H

H

3

Przegl

ą

d zupełny

:

- najpierw generujemy rozwi

ą

zanie (zast

ę

pujemy wszystkie zmienne

stałymi) a nast

ę

pnie testujemy, czy spełnia ono ograniczenia

- w tym konkretnym przypadku musimy wygenerowa

ć

4! = 24

permutacje zbioru {1,2,3,4} i ka

ż

d

ą

z nich sprawdzi

ć

3 4 2 4 2 3

4 3 4 2 3 2

2 3 4

1

3 4 1 4 1 3

4 3 4 1 3 1

1 3 4

2

2 4 1 4 1 2

4 2 4 1 2 1

1 2 4

3

2 3 1 3 1 2

3 2 3 1 2 1

1 2 3

4

[ ]

[2,4,1,3] [3,1,4,2]

4

Metoda nawrotów (standard backtracking)

:

- kolejni hetmani do listy dodawani pojedynczo i na bie

żą

co

sprawdzamy, czy ograniczenia s

ą

spełnione

2 4 2 3

3

2 3 4

1

1 3

3

1 3 4

2

2 4

2

1 2 4

3

2 3 1 3

2

1 2 3

4

[ ]

[2,4,1,3] [3,1,4,2]

background image

5

Forward checking

:

- kolejni hetmani do listy dodawani pojedynczo i na bie

żą

co

sprawdzamy, czy ograniczenia s

ą

spełnione (standard backtracking)

oraz uaktualniamy domeny hetmanów, usuwaj

ą

c z nich warto

ś

ci

niedozwolone (propagacja ogranicze

ń

) i sprawdzamy, czy która

ś

z domen nie jest pusta

2

3 4

1

1

3

4

2

4

2

1

3

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

6

H

1

H

H

2: BT do 1

H

H

3

4: BT do 0

H

H

H

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

H

H

X

X

X

X

X

X

X

X

X

X

X

X

H

H

X

X

X

X

X

X

X

X

X

X

X

X

H

X

2

3 4

1

1

3

4

2

4

2

1

3

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

7

5

H

H

H

6

H

H

H

7

H

H

H

H

8: [2,4,1,3]

BT do 0

H

H

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

X

X

X

X

X

X

H

X

H

X

X

X

X

X

X

X

X

X

X

H

X

H

X

H

X

X

X

X

X

X

X

X

X

X

H

X

H

X

H

2

3 4

1

1

3

4

2

4

2

1

3

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

8

9

H

H

H

10

H

11

H

H

12: [3,1,4,2]

BT do 0

H

H

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

H

X

H

X

X

X

X

X

X

X

X

X

H

X

X

H

X

H

2

3 4

1

1

3

4

2

4

2

1

3

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

background image

9

H

13

H

H

H

14

H

15: BT do 13

H

H

H

H

16: BT do 0

H

H

H

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

2

3 4

1

1

3

4

2

4

2

1

3

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

10

Looking Ahead + Forward checking

:

- kolejni hetmani do listy dodawani pojedynczo i na bie

żą

co:

sprawdzamy, czy ograniczenia s

ą

spełnione (standard backtracking),

uaktualniamy domeny hetmanów i sprawdzamy czy s

ą

niepuste

(forward checking), oraz sprawdzamy, czy domeny hetmanów
nieustawionych nie zawieraj

ą

wył

ą

cznie ustawie

ń

niebezpiecznych

3 4

1

1

3

4

2

4

2

1

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

11

H

1

H

H

2: BT do 1

H

H

3: BT do 0

4

H

H

H

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

H

H

X

X

X

X

X

X

X

X

X

X

X

X

H

H

X

X

X

X

X

X

X

X

X

X

X

X

H

X

3 4

1

1

3

4

2

4

2

1

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

H

H

X

X

X

X

X

X

X

X

X

X

X

X

A

A

H

X

X

X

X

X

X

X

X

X

12

5

H

H

H

6

H

H

H

H

8

H

H

7: [2,4,1,3]

BT do 0

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

X

X

X

X

X

X

H

X

H

X

X

X

X

X

X

X

X

X

X

H

X

H

X

H

X

X

X

X

X

X

X

X

X

X

H

X

H

X

H

3 4

1

1

3

4

2

4

2

1

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

H

X

X

X

X

X

X

X

X

X

X

H

X

H

X

X

X

X

X

X

X

X

X

X

H

X

H

X

H

X

X

X

X

X

X

X

X

X

X

H

X

H

X

H

H

X

X

X

X

X

X

X

X

X

background image

13

9

H

H

H

10

H

H

H

12

H

H

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

H

X

H

X

X

X

X

X

X

X

X

X

H

X

X

H

X

H

3 4

1

1

3

4

2

4

2

1

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

H

X

X

X

X

X

X

X

X

X

H

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

H

X

11: [3,1,4,2]

BT do 0

H

X

X

X

X

X

X

X

X

X

H

X

X

H

X

H

14

H

13: BT do 12

H

H

H

14: BT do 0

H

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

X

H

X

X

X

X

X

X

X

X

X

H

X

X

X

X

3 4

1

1

3

4

2

4

2

1

3

1 2

4

[ ]

[2,4,1,3] [3,1,4,2]

H

X

X

X

X

X

X

X

X

X

H

X

X

X

A

A


Wyszukiwarka

Podobne podstrony:
ZZL prezentacja wyklad 10
prezentacje, zarzadzanie - wyklad 10, KULTURA ORGANIZACYJNA
Prezentacja do wykladu 10 2cel
Strategie marketingowe prezentacje wykład
wyklad 10 MNE
wyklad 10
Wyklady 10 12c PRCz
Prezentacja wykłady I IV
Prezentacja 20 10
wyklad 10
Wyklad 10 Wypalenie zawodowe i jego konsekwencje
Wykład 10 dodatek
Wykład 8 10

więcej podobnych podstron