algorytm.org

Problemy optymalizacyjne i decyzyjne

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Problemy optymalizacyjne i decyzyjne
Ocena użytkowników:***** / 16
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 22:12

Problem decyzyjny Pi- zbiór parametrów, które nie muszą mieć nadanych wartości oraz pytanie, na które odpowiedź brzmi "tak" lub "nie". Ustalając wartości parametrów danego problemu Pi otrzymujemy instancję (konkretny problem), oznaczając ją przez I.
Problem decyzyjny Pi- zbiór instancji DPi oraz jego podzbiór, który zawiera wszystkie instancje, na które odpowiedź brzmi "tak".
Problem optymalizacyjny- wymaga ekstremalizacji funkcji celu związanej z danym problemem kombinatorycznym. Dla każdego problemu optymalizacyjnego istnieje odpowiadający mu problem decyzyjny, ale nie jest na odwrót.
Problem przeszukiwania Pi definiuje się przez podanie :
  1. zbioru instancji DPi
  2. zbioru rozwiązań ZPi(I) dla każdej instancji I należącej do DPi
Algorytm A rozwiązuje problem przeszukiwania Pi, jeśli dla każdej instancji I należącej do DPi odpowiedź brzmi "nie" jeśli zbiór ZPi(I) jest pusty a w przeciwnym razie algorytm znajduje jedno rozwiązanie należące do ZPi(I).
Przykład: problem sortowania:
Instancja I - dla danego ciągu liczb naturalnych znaleźć ciąg uporządkowany rosnąco.

Poprawiony: 15 sierpnia 2005 23:54
Dodaj komentarz