Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

1 Zeszyty Naukowe. Automatyka / Politechnika Śląska

1 2006

1 Dereniowski D.

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: local search algorithm

Sortuj według:

Ogranicz wyniki do:

Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów

100%

Dereniowski D.

2006

tom z. 143

51-56

Przedstawienie rozwiązań problemów kombinatorycznych w postaci permutacji daje podstawy do konstrukcji algorytmów lokalnych poszukiwań. Uporządkowane pokolorowanie grafu można zapisać w postaci permutacji wierzchołków grafu. Podstawowe operacje, prowadzące do generowania sąsiedztwa rozwiązania, to zamiana dwóch elementów lub przesunięcie elementu permutacji. W artykule wskazujemy metodę, pozwalającą na wykonanie takich operacji w czasie O(m), przy założeniu, że dane jest drzewo eliminacji wyjściowej permutacji.

Representing solutions to combinatorial problems as permutations allows us to use local search algorithms for solving them. A vertex ranking of a graph can be represented by a permutation of the vertices of the graph. Basic operations for generating a neighborhood of a current solution are swapping two elements of the permutation or changing a position of an element. We show how to perform such operations in time O(m) assuming that an elimination tree of the current permutation is given.