Czasopismo | ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA | Rocznik 2014 - zeszyt 2

Poszukiwanie rozwiązań problemu plecakowego z wykorzystaniem algorytmu genetycznego

nr katalogowy: 82511

Problem plecakowy należy do klasy problemów NP -zupełnych. Zagadnienia określane mianem NP -zupełnych stanowią klasę problemów obliczeniowych, w przypadku których nie jest znany żaden algorytm rozwiązujący dowolny z tego rodzaju problemów w czasie wielomianowym. Co interesujące, jak dotychczas nikomu nie udało się jeszcze udowodnić, że taki algorytm rozwiązujący któreś z zagadnień NP -zupełnych w czasie wielomianowym nie istnieje. Problem zagadnień NP -zupełnych jest zatem nadal otwarty i wciąż czeka na swe ostateczne rozwiązanie, stanowiąc tym samym chyba najbardziej doniosłą i zarazem jakże niezwykle intrygującą zagadkę informatyki teoretycznej [1]. Co ciekawe, wszystkie problemy obliczeniowe należące do zbioru zagadnień NP -zupełnych są wzajemnie równoważne w tym sensie, że każdy z nich można przetransformować do dowolnego innego w czasie wielomianowym. W związku z tym, gdyby został znaleziony algorytm rozwiązujący w czasie wielomianowym dowolny z problemów NP -zupełnych, wówczas automatycznie wszystkie pozostałe zagadnienia NP -zupełne byłby także rozwiązywalne w czasie wielomianowym. Niestety, jak już uprzednio wspomniano, nikomu nie udało się jeszcze odnaleźć takiego algorytmu bądź udowodnić, że jego znalezienie nie jest możliwe. Istniejący stan rzeczy powoduje, że na potrzeby praktycznych obliczeń zagadnienia NP -zupełne są rozwiązywane jedynie metodami heurystycznymi. W takim wypadku już z góry godzimy się z faktem, że rozwiązanie optymalne nigdy nie zostanie odnalezione, ponieważ prawdopodobieństwo jego przypadkowego natrafienia w procesie poszukiwań wynosi praktycznie zero (choć teoretycznie nie jest to zdarzenie niemożliwe). Natomiast w praktyce poszukujemy rozwiązań suboptymalnych o możliwie jak najlepszej jakości [2]. Tematyka artykułu dotyczy wykorzystania algorytmu genetycznego w celu poszukiwania rozwiązań zagadnienia plecakowego, które należy do klasy problemów NP -zupełnych. Problem plecakowy Załóżmy, że[...]

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


e-Publikacja (format pdf) - nr 28722 "Procesy otrzymywania gazó..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


PRZEMYSŁ CHEMICZNY - e-zeszyt (pdf) 2003-8-9-1 licencja: Osobista Produkt cyfrowy	55.00 zł

Prenumerata

PRZEMYSŁ CHEMICZNY - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

762.00 zł

PRZEMYSŁ CHEMICZNY - prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEMYSŁ CHEMICZNY - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	1002.00 zł brutto 927.78 zł netto 74.22 zł VAT (stawka VAT 8%)

1002.00 zł

PRZEMYSŁ CHEMICZNY - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEMYSŁ CHEMICZNY - papierowa prenumerata roczna	960.00 zł brutto 888.89 zł netto 71.11 zł VAT (stawka VAT 8%)
PRZEMYSŁ CHEMICZNY - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

1002.00 zł

Zeszyt

2014-2

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma