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 82511 "Poszukiwanie rozwiązań pr..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - e-zeszyt (pdf) 2014-2 licencja: Osobista Produkt cyfrowy	35.00 zł

Prenumerata

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

420.00 zł

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - papierowa prenumerata roczna	528.00 zł brutto 488.89 zł netto 39.11 zł VAT (stawka VAT 8%)
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

570.00 zł

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	636.00 zł brutto 588.89 zł netto 47.11 zł VAT (stawka VAT 8%)

636.00 zł

Zeszyt

2014-2

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma